Poisson Process

卜瓦松過程。蒲松過程。

深奧、真是深奧。

重新複習Poisson Process一下，這個隨機程序在Queueing Theory裡面相當重要，Poisson Process的定義大概是這樣：如果隨機變數X(t) 是計算從0到t的次數，則此隨機程序的分布情形為Poisson Distribution，則成為Poisson Process。換句話說，Poisson Process是一個counting process。

有兩個觀點來解釋Poisson Process。

FIRST

視為Binomial Distribution的特例之一。假設在(0,t)之間切割很多slot，在這些slot當中任意放置一點(稱為success，每個slot僅能有一個success)，其放置的機率為p，則在n個slot中發生k個success的機率為Binomial Distribution。

當增加slot的數目，也就是n增加；同時減少發生success的機率，也就是p下降，最後可以得到Poisson Distribution的情形，這樣將構成Poisson Process。意思是說：Poisson Process可以視為是很多很多Bernoulli Trial的集合結果。

這個結果有點像是推導Poisson Random Variable的時候所看到的。

SECOND

視為是一個Counting Process，這個觀點比較常在書上看到(通常是推導Poisson Process的章節)。

先計算從時間0到時間t的arrival數量，

有假設條件：

1. 在Δt=0中的機率=1-λΔt+o(Δt)
2. 在Δt=1中的機率=λΔt+o(Δt)：意思是機率和時間成正比，時間越長，發生的機會越大。
3. 在Δt>=2中的機率=o(Δt)：意思是兩個時間以上發生的機會是零，因為已經發生過了，換句話說，在同一時間當中發生兩次以上機會是零。

其中o(Δt)是當Δt→0的時候，o(Δt)除以Δt是0

另外假設：arrival的數量是不會在區間重覆的，也就是statistically independent，具備stationary increment。意思是不同區間的累計是獨立互不相關。

經過推導之後會發現，這個程序是Poisson Process。

********************************
補充：可以參考"Poisson 分配、指數分配與排隊理論(作者：翁秉仁)"這篇文章。

有感覺嗎？Poisson Process到底是什麼感覺。

神啊，告訴我什麼是Poisson的感覺阿？過了很久還是不了解啊！另外，Poisson Process還跟Exponential Dirtribution有關係。這......

該是放下的時候嗎？這是最後一步了。

因為

面對它‧接受它‧處理它‧放下它

漫談

太久沒寫了，主要是因為忙著賴桑的東西(web building)，因而沒有多餘時間在這方面研究。過幾天看看一些東西再補充吧！這裡是要"胡說八道"一些東西。

這個BLOG的目的已經寫了，希望將學習排隊理論的心得分享給大家，大家就看看吧！也許會有錯誤。我想說的是：重點不在正不正確，如果你發現我寫的有問題，那恭禧你，你學到了；如果你不知道，那也恭喜你，你會錯的跟我一樣，意思是會有答案，遲早會有人發現的。這才是我建置這個BLOG的主要原因，沒是丟那麼多垃圾到BLOG要幹嘛！Google遲早要一直擴建...擴建...，然後大家都到Google上班好了...成立Google世界政府算了

扯遠了。古人說的三不朽：立德、立功、立言(好的文章要引經據典...，古人不一定是對的啊)，立德和立功，立德交給偉人去做好了，立功交給有錢人去做吧！我們不偉大又不有錢，所以平時講講話就好了，也許哪天會有用(真扯...一堆人光說不做咧！)，所以我就在這個BLOG上寫寫文章，希望也許哪天變成中文的：排隊理論入口網站。

這有可能是真的，因為現在景氣那麼不好，希望繼續壞下去，人類史上能遇到這種經濟大崩盤還真不容易！不是做學術來模擬就知道結果的，如果能在歷史上留有證據，金融災難不失為是一件壞事。

世界越糟，我們才能了解到什麼是人性，人性自私，同時人性也憐憫。沒有遇過壞人，你不會知道要珍惜和好人相處，人類總是在相互比較，現在不好，因為以前很好，現在很好，因為以前經歷過更差的。金融風暴如果是場災難，也許人性才能有發揚的機會，趁機替所有的人上了一課，然後呢？但我們能做什麼。

排隊理論跟景氣有什麼關係？還記得排隊早在上帝時代就有了，動物為了排隊上諾亞方舟，需要計算優先權和時間，預估趕不趕得上大洪水，別以為上船很容易，這是需要時間和服務品質(QoS)的。

同樣的場景，你有沒有發覺最近都在促銷，促銷的同時也在排隊咧，還排的很長很長。大家為了搶便宜，這就會造成排隊的現象。因此，排隊理論將是22世紀的顯學之一(意思是2100年以後景氣還會慘囉...)，資源有限的情形之下，排隊會無所不在的發生(Ubiquitous Queueing)，為了以後著想，絕對有必要提早研究Queueing Theory！

僅供參考

Erlang=人+隨機變數+程式語言

偉大的Erlang不只是個人(A.K.Erlang)，也是個連續的隨機變數。

此外，最近發現Erlang還是個程式語言。關於這個語言，目前國內有一本書，如果有人要學這個語言，可以參考看看：

• 中文書名是「Erlang程式設計」，作者：蔡學鏞，基峯資訊出版。
• 原文是「Programming Erlang: Software for a Concurrent World」，作者是Joe Armstrong，由The Pragmatic Programmers出版。

(又是那傳說中的唯一一本，跟Ruby on Rails很像..."碼上就會：Rails敏捷開發網站")

另外，關於這個Erlang程式語言的資訊，可以參考 iThome的文章「Erlang：世界是平行的！」，這篇文章是蔡學鏞寫的。

此文章中提到，Erlang最早是用在電信產業當中(滿合理的，queueing本身是從Telecom來的)，用Erlang具有這些優點：

• 寫出來的程式，移到多核心的環境中執行，速度會自然變快（甚至有可能達到線性加速，n個核心就提升n倍）。
• 可以寫出容錯的系統，電腦當機之後會重新啟動。
• 可以寫出「程式碼熱抽換」的系統，可以一邊執行一邊升級，不用先暫停服務。
• 寫出來的程式不可思議地精簡。

詳細的內容請參考 iThome！

Single Server Queues (M/M/1)

討論M/M/1的情形，還記得Kendall's notation嗎？(請Google我的blog)

這種Queue的條件為

• Interarrival times = exponential distribution (pdf)
• Service times = exponential distribution (pdf)
• Server=1個
• System capacity=無限大(不會drop掉)
• Queue discipline=FCFS(先到先服務)

排隊理論學習心得

K了一陣子的Queueing Theory，心得是：不知所云。

難怪google結果中，有人提到：『今天整天都在看Queueing的書，腦袋快爆掉啦！』如果從學習平面上來看，排隊理論大概是位於右半平面(困難複雜、簡單複雜)。

　　　困難
　　　　↑
簡單←－|－→複雜
　　　　↓
　　　簡單

以下是紀錄(天氣：2009-02-04下午，晴時多雲，天氣涼爽宜人。)

對話錄
t5319019:老師，請問學習Queueing Theory有沒有什麼快速方法？實在讀不懂...

ycwang:這個...好像也沒有。很難。就只能一直看一直看。

t5319019:那有沒有像指南或學習地圖的方式，可以指引我們。(我想走捷徑阿！)

ycwang:好像也沒有。以前上課也是一直看，這種東西真的很枯燥。就只能多看幾次！

t5318019:好吧！再多看幾次看看會不會好一點。

ycwang:其實這和以前訓練有關，我們學的數學大多是實數、虛數、函數的觀念。但像這個(Queueing Theory)用的數學則是偏向另一方面的，用的是機率那一套的數學，所以我們就比較不熟悉，因此就比較難理解！

t5318019:嗯嗯。(對阿！真的真的。心有戚戚焉...原來是這個原故)
.
.

t5318019:那學習方式來說：我的想法有兩種。一個是先看理論，看懂再去實作模擬。另一個是先做模擬，不管理論部分，先兜出我要的model。請問老師哪一種方式比較好？

ycwang:你可以兩邊平行做，因為有時候理論很難看下去，就去做模擬看看。模擬做了之後，有時候會不了解，沒關係，這時候你再去看理論，你就會懂了。這是很奇妙的過程，有時候就突然懂了。
.
.
.

驚醒夢中人！原來是基礎訓練不足，導致後續的發展困難，這讓我想到「教育」的重要。

記得在台北科技大學的那段日子(明明就還在這間學校裡，已經7年了！之前聽說有學長待9年：五專+二技+碩士，天啊，那你都吃什麼？)

國文課的老師說到：『我們這群念科技大學的人，其實不比那些念普通大學的人差，為什麼呢？

因為受的教育不一樣，從高職到科技大學，念的東西本來就不一樣，怎麼能以普通大學的水準來比較程度呢！

教育跟種菜一樣，給他什麼肥料，就長什麼樣子出來，這群學生哪曉得吃的是什麼東西。(就算是毒藥也不知道，因為不知道毒藥是什麼)』

因為學校和老師就給你吃這些東西，等到你發現吃的東西不對的時候，你早就已經畢業了。

Birth-Death Processes

Birth-Death Processes應該翻成「生死過程」嗎？這是第一個疑問，怪...(所以就用原文吧)

Birth-Death Processes是CTMC中的一個特殊類型，這個Process主要是用來求解一些簡單的Queueing Model，用來計算穩態解(Steady-state)。

所謂的Birth是指arrival(到達)，而Death是指departure(離開)。

因為是Markov Chain也就是Discrete State Space，因此在Birth-Death Processes中，有state-0、state-1、state-2、state-3...到state-n(如果是finite的Markov Chain)。

Queueing Theory 100th Anniversary 排隊理論一百周年

如果說1909的Agner Krarup Erlang所發表paper是Queueing Theory之始，那麼今年2009來說，就是Queueing Theory的一百周年了！

訂定今年為" 排隊理論年"，用以紀念排隊理論一百周年，藉此好好回顧與展望Queueing Theory！

• 其實世界萬物一切始於Queue(排隊)，聖經中已經告訴我們了，能上若亞方舟(Noah's Ark)的都是排隊來的，生於排隊，死於排隊，排隊之偉大，不是一般人能懂的！
• Queueing Theory的中文問題，依據Google發現(不能說"有人說"，學術是很嚴謹的...!?)，翻譯名詞有很多種：排隊理論、排隊論、等候理論、等候線理論、佇列理論。哪個是比較適當的？根據調查，「排隊理論」是最親近凡人的名詞，凡人都有排過隊，「排隊」兩字是大家都能聯想到的，也是最能引起眾人的共鳴，太好啊！

另外，目前已經有紀念排隊理論一百周年的活動，大家可以Google看看喔！

已知網站http://www.erlang100.dk/，100 years of queueing - The Erlang Centennial

網站內容：

Call for papers:

In 1909 A.K. Erlang published the paper "The theory of probabilities and telephone conversations" (Nyt Tidsskrift for Matematik B, Vol. 20. pp. 33-39), which may be considered to be the first publication in queueing theory.

To celebrate the centennial of queueing theory, a conference "100 years of queueing -- The Erlang Centennial" will be organized in Copenhagen, on April 1-3, 2009. The number of participants is restricted.

The journal Queueing Systems shall devote a special issue to the papers that will be presented at this conference.

The editors of the special issue are Søren Asmussen and Onno Boxma.

詳情請參考原網站。

Philosophy哲學-知識論(Epistemology)

春節假期快結束了，談談排隊理論之外的東西吧！
前幾天和建德兄Jasper提到一個問題，談論到Queueing Theory的緣起，
目前我正在學Queueing Theory(這算是論文的工具)，
之所以會學QueueingTheory是因為我的老師，
第一次聽到QueueingTheory也是從老師的談話中得知，
重點是：

誰曉得排隊也有理論啊！

如果說我的老師從他的老師得知排隊理論，而他的老師從他的老師的老師......依此推論，那麼，第一個提出排隊理論的會是？

根據Google結果，第一個提出Queueing Theory的是Agner Krarup Erlang(1909年的paper)，另外第一個使用Queueing System這個名詞的是David George Kendall(1951年的paper)。

而第一個提出Queueing Theory的人，是怎麼知道的？

這是個哲學問題。

在哲學領域當中，有一項是：知識論(Epistemology)，下面引述Wikipedia的Epistemology條目，

Epistemology (from Greek επιστήμη - episteme, "knowledge" + λόγος, "logos") or theory of knowledge is the branch of philosophy concerned with the nature and scope (limitations) of knowledge. It addresses the questions:

• "What is knowledge?"
• "How is knowledge acquired?"
• "What do people know?"
• "How do we know what we know?"

這正是建德兄Jasper提到的問題，或許！正是這個道理：

萬宗歸一，理一分殊。