2009年2月27日星期五

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有關係。這......

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

因為

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

2009年2月20日星期五

漫談

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

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

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

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

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

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

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

僅供參考

2009年2月8日星期日

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

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

此外,最近發現Erlang還是個程式語言。關於這個語言,目前國內有一本書,如果有人要學這個語言,可以參考看看:
(又是那傳說中的唯一一本,跟Ruby on Rails很像..."碼上就會:Rails敏捷開發網站")

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

此文章中提到,Erlang最早是用在電信產業當中(滿合理的,queueing本身是從Telecom來的),用Erlang具有這些優點:
  • 寫出來的程式,移到多核心的環境中執行,速度會自然變快(甚至有可能達到線性加速,n個核心就提升n倍)。
  • 可以寫出容錯的系統,電腦當機之後會重新啟動。
  • 可以寫出「程式碼熱抽換」的系統,可以一邊執行一邊升級,不用先暫停服務。
  • 寫出來的程式不可思議地精簡。
詳細的內容請參考 iThome!

2009年2月7日星期六

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(先到先服務)

2009年2月5日星期四

排隊理論學習心得

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2009年2月3日星期二

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)。

2009年2月2日星期一

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.

詳情請參考原網站。

2009年2月1日星期日

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提到的問題,或許!正是這個道理:

萬宗歸一,理一分殊。