排隊與等公車

最近為了賺博班的學費，
開始到某間當地的公司當小intern，
因為跟學校的方向不太一樣，
所以上下班需要轉車，
不過上班前兩天我很快就發現，
轉往公司的那班公車發車頻率好像不高，
所以就實驗幾次用走的，
實驗結果發現上下班的時間有明顯的改善。
(如果是寫paper這時候就要附圖表比較方法改良前後的差異 XD)

但是身為一位準博班生，
而且又是主攻通訊網路，
我決定更進一步用數學分析把問題一般化，
用一點基本的排隊理論(Queuing Theory)跟隨機程序(Stochastic Processing)，
導出等公車的期望值與發車間距的關係，
最後對這類等公車問題提出少少決策上的建議。

以下開始會扯到一堆數學，
不過套句之前大學教我演算法的教授說的：
「讀資工系只要會高中數學就夠了。」
沒錯，我會盡量不要用正規的表示方法(或我稱為write-only representation)，
(write-only等於not readable......in case you don't get my haha point XD)
畢竟又不是要丟journal XD......

剛開始寫paper的時候老師都有教，
introduction就是說明主題解釋問題在哪方面會讓人覺得有趣，
接下來我們就開始進行problem formulation這個動作。(這個動作這個動作～)

我們的問題是，如果我吃飽撐著每天都跑去等公車，
等了無限多次之後，等車時間的平均會是多少？
換句話說，我想求等待時間的期望值。
(樣本趨近無限大時的平均就是期望值，這是高中數學沒錯吧？)

下一步就是要決定公車到站跟我到站的model，
(model不是穿少少漂漂走秀那種，是分佈模式，
為了不要超出高中數學的範疇，就想像成是符合某種機率分佈吧。)
在Queuing裡面，最重要最基本最簡單的一個分佈就是Poisson Distribution了，
因為他是如此的神奇如此的好用，
重點是在不過度簡化問題的條件下也能做出很逼近的預測，
所以我們就假設公車到站跟我到站各是一個Poisson Distribution random variable，
假設公車發車間距是t分鐘，我到站的頻率則不需要知道。
(為了不要超出高中數學的範疇，數學老師都會說，背起來就對了，你長大就會懂了。)
(至於如果高中數學沒教過Poisson Distribution......等我哪天閒著再解釋吧......)

很好，我們的問題越來越明瞭啦！
因為我現在假設我每天到站的時間是Poisson distribution，
所以我要求的就是，
把無限多天等待時間加起來求期望值！
因為Poisson process三大特性之一就是stationary increment，
所以我什麼時間到，上一班車多久之前開走，都不重要，
我要知道的只是，我離下一班車到站的平均時間會是多少。

聽起來感覺好像比較make sense了，
但是無限多天我不會求啊......zz
高中數學老師又說了，
無限多天不會求，就把範圍切一切切很細，然後再加起來。
因此我們問題就可以再簡化為，
先假設我們只等n次，
假設下一班車是在時間t來，
那這n次到達時間S跟下班車到達時間t的差，期望值是多少：

因為時間t跟n是獨立，
所以可以先拿出來乘，得到nt，......(1)
剩下要求n次到達時間S的期望值，
根據定義，Poisson process的每次event(也就是每次到站時間)是uniform distribution，
所以我們一次S的期望值，就是求在0~t中間取一個uniform random variable的期望值，
使用高中數學，得到t/2，
取n個的期望值，得到nt/2，......(2)
(1)-(2)=nt/2。......(3)

下一步就是使用高中數學，從0加到無限大，
也就是sum((nt/2)*P(n), n=0..infinity)，......(4)
P(n)是Poisson distribution，在時間0~t之間出現n次的機率，
換句話說就是我們等公車等了無限多天以後，
剛剛好有n天是在時間0~t這段時間來等的機率，
至於其他天，不重要，因為從0加到無限大就會考慮進來了。

最後，簡化式(4)，
t/2與n獨立，拉到sum外面，
變成(t/2)*sum(n*P(n), n=0,,infinity)，......(5)
裡面那項，
複習一下高中數學random variable的值域*對應出現的機率，就是期望值，
所以就是Poisson distribution的期望值，
根據定義，也就是Poisson distribution的inter-arrival rate(lambda)乘以觀察的時間t，
在我們的例子，公車間距是t，所以rate是1/t，乘上時間t，就是1，
換句話說，意思就是，如果公車的間距是t，
然後我們每天吃飽撐著在那邊等t時間這麼長，
那觀察無限多天以後，平均我們每次可以看到1班公車開過去。

整理一下結論，式(5)的後項是1，所以就剩下t/2！
也就是說，假設公車班距是t，
那我們每次等車時間的期望值就會是t/2。

這個結論告訴我們什麼呢？
如果我們走路或是有其他交通方式能在t/2時間內到達目的地，
在最短時間的考量下，
最好就是不要等車，
這也符合我的實驗結果，
我要轉車的公車班距約是20分鐘，
但是我只要十分鐘就能從中點站走到公司(或從公司走回中點站)，
所以鐵了心用走的幾乎每次都會比公車早到。

不過為了算出t/2這個漂亮的答案，
所以我把問題簡化很多了，
在現實生活中，等車時間也會受到交通狀況的影響，
在這種情況下，inter-arrival rate並不見得是常數，
如果加上前班車大塞車，後班車有可能要站站樂清掉一堆乘客，
導致與前班車班距拉長(dispersion expansion)與後班車班距拉短(dispersion compression)，
那問題就又更複雜了，
而且在這裡我們假設公車到站跟我到站是互相獨立，
所以才能用superposition來算，
簡單來說，這就是排隊"理論"與"現實"等公車的差異，
但是我們也看到，
即便是簡化這麼多條件之後，
Poisson process仍然得出一個很接近現實生活的期望值，
這件事告訴我們，
等公車的時候.....................................
就好好等公車不要想東想西的人家還以為你是瘋子 lol......

窮留學生要繼續做工去了......
如果你求知慾強烈想要了解所有理論基礎，
入門可以參考WiKi--Poisson distribution
進階則建議參考Stochastic Process相關書籍，
就是千萬別來問我！！
我只會算這題而已......XD