2012年9月20日星期四

Julia 初體驗の立法會選舉勝算 DIY

我慣用 C++ 與 Matlab/Octave,偶爾也用 Python 及 R。近年眼見不少有趣語言出現,我尤為喜歡 Ruby, D(兩者其實都不算新), ScalaChapel,可是除了 Ruby 我依然計劃會抽時間學之外,其餘都只得三十秒熱度。直至最近偶然碰到 Julia,覺得應該先與她(實在無法說「它」呀)把臂同遊。

C++ 的發明人 Bjarne Stroustrup 將 C++ 形容為 "a general purpose programming language with a bias towards systems programming"。依此說法,Julia 大概就是 "a general purpose programming language with a bias towards scientific computing" 了。若不計 Julia 語法上對矩陣的直接支援,我想一般 programmers 應該不會將她聯想成 domain-specific language 吧。

我昨天才下載 Julia,約會了一日,她給我的第一印象,是她絕對有潛力成為 Matlab 殺手或 R 殺手。無論是語法的簡潔程度、data structures 的數量、語法上對 functional programming, generic programming 及 parallel computing 的支援,抑或程式的執行速度,Julia 都明顯超越對手,網上不少 Matlab 與 R 用家亦對她頗為讚賞。她也借用了 Ruby, Python, Matlab 與 C/C++ 語法當中一些優良部份,我學習時倍感親切。

Julia 今年一月才出 1.0 版本,算係有女初長成,距離亭亭玉立還有一段日子,現在仍有不少未成熟的地方,不過已經夠足我做練習用。前文提過,計算立法會選舉各競選名單的勝算,可用多項式分佈的常態逼近當成投票的分佈。利用蒙地卡羅模擬實驗,就可以計算出各名單的勝算。文友電鋸於選舉前已經做過類似的計算,此處只是當成我第一次的 Julia 編程練習。

先說明計算細節。設 $\mathbf{p} = (p_1,\ldots,p_n)^\top = $ 民調所得各名單的支持度 ($\sum_i p_i = 1$),而 $n$ 是樣本數,譬如 NOW 新聞台於九月七日報道(調查時窗為九月二至六日)的結果為

$$\mathbf{p}=\frac{1}{101} (4, 7, 5, 7, 1, 2, 16, 9, 3, 3, 8, 4, 1, 8, 1, 12)^\top,\ n=503.$$
(由於 NOW 新聞台四捨五入,以上向量內各數字的總和為 101 而非 100。)我們的做法,是模擬多次投票實驗。每次實驗,均由 n=503 位選民,每人隨機投一張名單一票。投票的概率由 $\mathbf{p}$ 決定。換句話說,每一名選民都會有 $p_1=\frac4{101}$ 的機會投票予第一張名單、$p_2=\frac7{101}$ 的機會予第二張名單,餘此類推。當 503 人都投完票,就可以按比例代表制查出名單上各人是否當選,查核完畢,就完成了一次實驗。重覆同樣實驗許多次 ──  譬如 1,000,000 次,就完成了整個模擬過程。整個過程當中,若排在七號名單第二順位的余若薇當選了300,000 次,她當選的概率就估計為 300,000/1,000,000 = 0.3,其他人的當選概率也用同一方式估計。

n = 503 位選民每人按 $\mathbf{p}$ 的概率來投票,即是說各名單得票 $(X_1,\ldots,X_m)$ (今屆新界西有 m=16 張競選名單)的分佈為 $\textrm{Multinomial}(n, \mathbf{p})$。多項式分佈的常態逼近公式,可參考本網誌前文,當中用到的正交矩陣 Q 的構作方法,則見我另一篇網誌。總括來說,設

$$
\begin{eqnarray}
v &=& \frac12 \left(
\begin{bmatrix}0\\ \vdots\\0\\1\end{bmatrix} -
\begin{bmatrix}\sqrt{p_1}\\ \vdots\\\sqrt{p_m}\end{bmatrix}
\right),\\
M &=&
\begin{bmatrix}\sqrt{\frac{p_1}n}\\ &\ddots\\&&\sqrt{\frac{p_m}n}\end{bmatrix}
\left(I_m - 2\frac{vv^\top}{\|v\|^2}\right).
\end{eqnarray}
$$若每次投票實驗,我們皆能夠生成 $m-1$ 個服從標準常態分佈的隨機數字 $Z_1, \ldots, Z_{m-1}$(重申,m 是競選名單數目,n 為投票人數),則每次實驗各名單的得票率可模擬為:

$$
\begin{bmatrix}\frac{X_1}n\\ \vdots\\ \frac{X_m}n\end{bmatrix}\approx \mathbf{p} + M\begin{bmatrix} Z_1\\ \vdots\\ Z_{m-1}\\ 0\end{bmatrix}.
$$
生成得票率之後,將它正規化為 $m$ 倍:
$$\mathbf{f} = (f_1, \ldots, f_m)^\top = m\left(\frac{X_1}n, \ldots, \frac{X_m}n\right)^\top,$$
之後就可以點票。正規化後的黑爾數額為 1(原本黑爾數額為 1/m,乘以 m 倍就變成 1)。每個 $f_k$ 都是一個實數,其整數部份 $\lfloor f_k\rfloor$ 代表第 k 張名單因超過黑爾數額而取得的議席數目,小數部份 $r_k = f_k - \lfloor f_k\rfloor$ 代表餘額。比較各餘額的大小,就知道餘下 $m - \sum_k \lfloor f_k\rfloor$ 個議席落入誰家。最後程式如下:
 

我和 Julia 還不是很熟。上面有些迴圈,相信可以用比較 functional programming 的方式寫得精簡一些。

按上述 NOW 新聞台的調查結果,由 Julia 所計算,十六張名單中各候選人(是候選人,不是候選名單)的當選概率依次為:
  1. 郭家麒 (1.0)
  2. 譚耀宗 (1.0)
  3. 李卓人 (0.999993)
  4. 田北辰 (0.99991)
  5. 李永達 (0.99954)
  6. 梁耀忠 (0.999528)
  7. 陳偉業 (0.996816)
  8. 麥美娟 (0.996756)
  9. 陳樹英 (0.918242)
  10. 余若薇 (0.821678)
  11. 陳恒鑌 (0.716208)
  12. 梁志祥 (0.716037)
  13. 陳一華 (0.338804)
  14. 何君堯 (0.338146)
  15. 龍瑞卿 (0.066209)
  16. 曾健成 (0.065039)
  17. 譚駿賢 (0.004338)
  18. 麥業成 (0.002589)
  19. 陳強 (0.002561)
  20. 張慧晶 (0.000565)
... 等等。一百萬次實驗,在我的電腦上需時共廿九秒。至於何謂有「極高機會」當選,何謂「較高機會」、「機會均等」、「機會較低」,就見仁見智了。

若只想知道那九位候選人有最高機會當選,那其實毋須搞甚麼模擬實驗,因為以上當選概率的高低名次,基本上與民調得出的支持度的高低排列相同。因此,模擬實驗結果中勝算最高的九位候選人,就是民調結果中支持度最高那九位。這類勝算計算的目的,其實並非要找出最有機會當選的是誰,而是要反映這些勝算較高的候選人,與其他候選人的差距。

這個方法也有它的毛病,當中最嚴重的,是它沒有考慮政黨配票的情形。以上例來說,民建聯梁志祥與陳恒鑌的支持度一直低企,約四、五個巴仙左右,可是到了選舉日,他們的得票率比起民調結果大幅上升,相反,譚耀宗的得票率就比民調結果低許多(變成約 8%)。要考慮配票,就要考慮各政黨互相鬥法,結果可能要計算隨機博奕下的 Nash equilibrium。除了較複雜之外,均衡點是否存在,是否唯一,亦造成很大的技術困難。

2012年9月17日星期一

Fate/Legco: 機器學習與選舉工程

有兩夫婦與一位鄰居遇到海難,三人各乘一艘只可載一人的充氣快艇逃生。大海茫茫,暴風雨迫近。他們估計所餘燃料只夠二人逃走,究竟誰要犧牲?最後三人相持不下,全數沒頂,這是誰的責任?
前言
剛過去的立法會選舉,民主黨於新界西全軍覆沒。另一邊廂,公民黨的兩人競選名單成為新界西票王,獲 72185 票之多,扣除首席所需的基本票額之後,餘額卻不夠令名單中排次位的余若薇連任。有人指摘公民黨策略錯誤,既分薄了民主黨票源,又平白浪費選票。

本文將運用機器學習 (machine learning) 技巧,說明根據過往經驗,今屆各次滾動民意調查當中,即使民主黨的支持度處於最高峯 (14%) 的時候,其形勢也有很大隱憂。多數時候,民調結果更顯示民主黨有全滅危險。民主黨要保住一席的話,只要棄車保帥就可以,因此它遭全滅,完全是它自身策略錯誤所至。

過往最常見的選舉分析方法,是從滾動調查所得的政黨支持度,按多項式分佈的常態逼近 (normal approximation to multinomial distribution) 來計算勝機。一般期刊文章,若要以票站調查結果來模擬比例代表制之下的選舉結果,就是用多項式分佈。這樣做的最大好處,在於可以隨時更新評估結果。原則上,此方法更可以納入整體形勢,而不是對每張名單都只按它自己的支持度來計算勝機。然而,遠在選舉提名期尚未結束,政黨連有甚麼對手都未清楚之時,這個方法就不適用。

本文將提出一種靜態的研究方法,它只依賴過往的選舉結果,並不需要(但也可以用)最新的民意調查結果。它無法動態地考慮通盤選舉形勢,但它可以於選舉提名期間,就用來評估分拆或分併競選名單的風險。作者將估計勝算的問題聯繫到數據科學中的「分類問題」(classification problem)。解決問題的方法稱為 logistic regression,以今日的標準來看,只是統計學與數據科學 (data science) 的初等技巧,但足以應付眼前的新界西個案。

基本須知
本文假設讀者知道何謂比例代表制,亦明白本地立法會選舉比例代表制所用的最大餘額法當中,黑爾數額 (Hare quota) 的意思。從某個角度而言,黑爾數額是一張擁有多名候選人的競選名單當中,每名候選人所能消耗的票數上限。與此相關的是特羅普數額 (Droop quota),它是保證一名候選人當選所需的票數下限。近年網上多了談及 Droop quota 的文章(例一例二),可是為求完整,以下亦會稍作說明。

以今年新界西選區為例,各黨派一起競爭 9 個議席。問題:無論其他名單得票若干,民主黨的李永達名單,至少要有幾多得票率,方可保證任何情況下當選?

答案是 $\frac1{10}$。理由:設 9 位當選者的得票率為 $p_1, p_2, ..., p_9$。若李永達取得 $\frac1{10}$ 的票仍不夠當選,那即是說每名當選者的得票率 $p_i$,必然較 $\frac1{10}$ 為高,故此

$$
\begin{align*}
&\phantom{=}李永達與\ 9\ 位當選者的總得票率\\
&= \frac1{10} + p_1 + \ldots + p_9\\
&> \frac1{10} + \underbrace{\frac1{10} + \ldots + \frac1{10}}_{9 個}
\quad(因為每個\ p_i\ 都大過 \frac1{10})\\
&= 1.
\end{align*}
$$
亦即是說,李永達與 9 位當選者的得票率總和,竟然大於 1,這顯然是不可能的。同一道理,若選區有 n 個議席,只要排於名單首位的某君取得
$$d_1(n)=\frac1{n+1}$$ 的票,不管其他對手取得幾多票,此君亦鐵定當選,否則就會出現「部份候選人的得票率總和竟然大於 1」這件邏輯上不可能發生的事。上面這個 $d_1$,就是一般文章所講的 Droop quota,也就是保證排於名單首位的候選人取得一席所需的安全線

機器學習:得票率與選舉結果的關係
Droop quota 只是一條安全線,它是當選的充份條件 (sufficient condition) 而非必要條件 (necessary condition)。候選人越過它,則鐵定當選,但不越過也有可能當選。以今屆立法會選舉新界西的結果為例(下表,綠色當選,紅色落選),十六張名單爭奪 n=9 個議席,安全線為 $d_1(9) =  \frac1{9+1} = 0.1$。從表中可見,九名當選者之中,只有郭家麒一人越過安全線(即是得票率 $\ge 0.1$)。



現實中,經常有候選人未達安全線但仍當選。當然,得票率愈接近安全線,候選人就愈篤定,反之風險愈高,如何量度這個風險?

我們可以憑歷屆選舉結果,評估得票率與當選機會之間的關係,但首先要就選區議席數目調整得票率。舉例說,對一個有 9 個議席的選區(安全線 $d_1(9)=0.1$),若一張名單的得票率為 v = 0.08,應該有不錯的勝算。然而,換了是一個只得 4 個議席的選區(安全線 $d_1(4) = 0.2$),0.08 的得票率就未免離安全線太遠。因此,若一張名單的得票率為 v 而選區議席數目為 n,我們會考慮以下這個「規範得票率」:

$$
\textrm{normalized proportion of votes}\ v' = \frac{v}{d_1(n)} =(n+1)v.
$$v' 愈接近 1,即代表該選舉名單愈接近安全線。搜集從 1998 年起四屆立法會的選舉數據,可將歷屆各參選名單的規範得票率與選舉結果圖列如下。(由於 $v'\ge1$ 就必然當選,故下圖並不包括 $v'\ge 1$ 的例子。)
圖一:1998-2008 年立法會選舉各候選名單的規範得票率
從圖中可見,過往當 v' 介乎 0.5 至 0.8 的時候,當選與落選的例子混雜。這引出以下問題:若某候選名單估計會有某規範得票率 v'(譬如 v'=0.75),那麼,根據過去經驗,我們認為該名單的首席候選人會否當選?

這就是機器學習理論所謂的「分類問題」。換句話來說,我們希望憑規範得票率 v' 的數值,就可以將候選名單歸入「當選」或「落選」其中一類。當然,從上圖可知,當選與落選名單的規範得票率之間,並無一條清晰界線。因此,機器學習理論的做法,是將過往的選舉結果稱合 (fit) 到一條概率曲線之上,如下圖。譬如圖中顯示,若某名單的 v'=0.75,我們即相信該名單有 0.83 的機會當選。顧名思義,一般分類問題的目的,是為了替目標對像分類,不過我們這裏的着眼點,是評估一張競選名單的當選機會,而不是賭它會不會當選,因此我們不會說「v'=0.75 時,我們相信該名單會當選」,而只會說它有 0.83 的勝算
圖二:用概率曲線稱合 1998-2008 年的規範得票率
如何稱合概率曲線?答案是用 logistic regression。Logistic regression 是統計學與機器學習理論之中的初等方法。詳情相信大部份讀者沒有興趣知道,故此處不贅。上圖是作者利用歷屆立法會選舉結果,從統計軟件 R 計算所得,稱合的勝算曲線為:
$$f(v') = \frac{1}{1+\exp(7.899974-12.664143v')}. $$
方法利弊
從規範得票率的歷史數據來學習當選機會,有利有弊。如文首所說,它最大的好處,是只依靠歷史數據,完全不需理會現狀,甚至遠在上屆選舉剛剛結束,今屆選舉提名期尚未開始之時,即可找出稱合的勝算曲線。

然而這也是它最大的毛病。我們固然可以於民意調查開始之後,將政黨的最新支持度當成得票率,再從勝算曲線讀出當選機會,這樣做卻忽略了對手的選情。這好比打麻雀只盯着自己摸回來的牌,而不顧其他三家一樣,並非善用情報的方法。

此外,由於這個方法只依賴歷史數據,但各政黨的排陣、支持度與選區議席數目皆因時而異,故此歷史經驗未必適用。事實上,今屆有選區(新界西與新界東)議席增加為九個,就前所未見,不過以前已經試過一區有八個議席,所以這還不算是大問題。最嚴重的,是現況完全超出過去經驗的時候,稱合所得的曲線就會變成廢物。例如根據 1998-2008 年的數據,若我們想稱合一張名單會取得第二席的勝算曲線,就會遇着這樣的情況,不過本文重點是取得第一席的概率,故詳情此處不贅。

換句話說,儘管 logistic regression 背後有堅實的統計學基礎,但歷屆選舉並非處於同樣條件的統計事件,因此我們實際上並非用 logistic regression 來解決一個統計問題,而僅僅是把它當成一種插值法,用來將曲線稱合到數據當中。這也算是沒辦法之中的辦法,卻也是讀者必須留意的一點。

圖表詮釋
今屆民主黨於新界西用李永達、陳樹英兩張名單參選。去屆該黨於新界西取得 23.25% 的選票。今屆安全線為 $d_1(9)=0.1$,若該黨得票率與上屆相若,則已超過兩張名單越過安全線所需,所以,毋須任何麻煩的分析,只要民主黨能夠令支持者比較平均地投票給兩張名單,就幾乎可以保證全取兩席。

只不過,「得票率與上屆相若」 這個假設,於民意調查甫一開始時,就已經站不住腳。



以上七次滾動調查結果,以最尾一次最利民主黨。暫且假設這個結果可信。根據此結果,民主黨的支持度有 14%。原則上同黨各名單的支持度是不可相加的,原因是選民可能「投人」而不是「投黨」,不投李永達,也未必會改投陳樹英,更何況有些人本來投的就是遊離票。只不過以舊鑑新總要有個標準,因此本文仍假設選民乃按黨派投票,而同一黨的支持票是可以於各名單之間轉移。這樣,我們應如何看待民主黨這 14% 的支持度?

記民主黨的得票率為 $v_\max$,並設李永達名單的得票率為 v,因此它的規範得票率為 $\frac{v}{d_1(9)} = 10v$,而陳樹英名單的規範得票率為 $10(v_\max-v)$。故此,根據歷屆數據,李、陳兩張名單的勝算分別為 $f(10v)$ 與 $f\left(10(v_\max-v)\right)$。若民主黨新界西的總得票率真的如調查所得,即 $v_\max=0.14$,那麼李、陳兩者的勝算曲線有如下圖,其中藍線代表李永達,黑色虛曲線代表陳樹英,橫軸為李永達的得票率(不論是李永達的曲線還是陳樹英的曲線)。例如九月七日的民調顯示李永達的支持度為 0.08,圖中顯示了這個情況之下,陳樹英的勝算為黑色曲虛線的高度,亦即 0.43,而李永達的勝算為藍色曲線的高度,即 0.9。

從這幅圖也可推出兩人皆勝或兩人皆輸的機會率。當李永達的支持度為 0.08,陳樹英的支持度就是 0.14 - 0.08 = 0.06,比李永達低。若陳樹英當選,由於李永達得票比她多,因此亦必然當選。換句話說,當陳樹英的得票比李永達低的時候,她的勝算實際上就是兩者皆勝的機會率,而李永達的落選機會率就是兩人皆輸的機會率。同一道理,可知圖中紅色部份的高度,代表兩人全滅的機會率,綠區高度代表兩人全勝的機會率,而黃區高度代表兩人中只得一人當選的機會率。以李永達的得票率為 0.08 為例,兩人全勝的機會率為 0.43(圖中深綠色直線長度),兩人全滅的風險為 0.1(赤色直線長度),而李勝陳敗的機會率為 0.47(暗黃直線長度)。
圖三:從九月七日民調所得的民主黨勝算曲線
分析
政黨派兩張(實際上等於一人的)名單參選,目標不外以下兩者:
  1. (全攻型)務求全取兩席。
  2. (防守型)確保一席,並伺機提高另一張名單的勝算,情況轉壞則棄車保帥。
九月七日的民調指民主黨所享的支持度為 14%。若此支持度不變,而民主黨務求兩張名單皆勝,就要靠配票來提高全勝的機會率。下圖顯示,若要將全勝的機會保持於五成以上,李永達的得票率就必須維持於 (0.062, 0.078) 這個範圍之內,得票率的誤差不能大於 0.016(圖中綠色橫線長度),亦即所有支持票的 (0.016/0.14) × 100% = 11.4%;以去屆該區的總投票人數 398292 人來估計,即誤差不能大於 6373 票。靠配票令兩張名單得票相差不多於六千幾票,換了是民建聯應該能輕易辦到。民主黨的支持者並非鐵票部隊,但是上述這個準確度照計尚算寬鬆。

吊詭的是,要提高全勝機會,亦自然會提高全滅的風險,原因是綠區的頂峯即是紅區的尖端。最有全勝把握的時候,也是全滅風險最大之時。圖四之中,若民主黨要將全勝機會保持在五成以上,全滅的風險就會介乎 0.12 至 0.27 之間。0.27 的全滅概率,或 1 - 0.27 = 0.73 的全勝機會算不算高,我不知政黨怎麼想,我自己就覺得「唔湯唔水」,有點微妙,不過也不是去到要令人非常警惕的地步。故此,若民主黨要採取全攻型策略而不棄保,也是合理的。

只是,這背後隱藏了一個假設,就是民主黨的支持率真的如民調所說,有 14%。
圖四:總得票率 0.14,全勝機會 0.5 或以上
民意調查當然並非毫無誤差。九月七日的調查,樣本數為 503,而民主黨的支持度為 0.14。若以常用的 95% 信賴區間來計算,民主黨支持度的誤差可達 $1.96\sqrt{\frac{0.14(1-0.14)}{503}} = 0.03$ 之多。換句話說,即使民主黨實際的支持度為 0.14 - 0.03 = 0.11,也不是甚麼奇怪的事。


事實上,前述 NOW 新聞台的多次民意調查,都顯示民主黨的支持度低迷,只得 11% 左右,直到最後兩次民調,才忽然上升至 14%。如此情況下,究竟我們應該相信之前的結果,認為後來兩次有統計誤差,抑或相信民意真的變強,實在見仁見智。然而,問題是,即使民主黨的支持度真的變強了,民調的誤差也沒有 3% 那麼大,我們仍不能排除 14% 這個數字有誤差,而民主黨的真正問題,是即使它的支持度只下降少許,勝算也會大幅改變

前面提過,若李、陳兩張名單的總得票率為 $v_\max$,李永達的得票率為 $v$,則陳樹英的得票為 $v_\max-v$。因此,若李永達的得票率不變,但民主黨的總得票率 $v_\max$ 下降一個單位,陳樹英的勝算曲線就會向左移動一個單位。下圖顯示了民主黨的總得票率為 0.14, 0.13, 0.12 及 0.11 時的情況。圖中可見,若李永達的得票率為 0.08,而民主黨的總得票率由 0.14 跌至 0.13,則全勝機會會由 0.4 以上大降至 0.2 以下;若總得票率降至 0.11,而李永達的得票率並無改變,則民主黨的全勝機會更是近乎零。
圖五:民主黨的全勝機會,對總得票率十分敏感
就算民主黨的真正得票率只下降 0.01,配票也會變得異常困難。見圖六。當 $v_\max = 0.13$,全勝機會最多也不到六成。若要將全勝機會維持於五成或以上,配票的準確度就要在 0.006 之內,或支持票的 (0.006/0.13) × 100% = 4.6%;以去屆投票人數來計算,即是 2400 票左右。換了是民建聯,恐怕也未必做得到。何況選舉當日的票站調查結果以及配票都會有誤差,若對配票準確度的要求太高,配票策略很容易泡湯。困難之餘,全滅的風險亦變得相當大,介乎 0.33 與 0.41 之間。為追求不到六成的全勝機會而冒上超過三分之一的全滅風險,實在不是明智的做法。
圖六:民主黨的勝算曲線 ($v_\max=0.13$)
要減低全滅的風險又如何?見圖七。若要將風險局限於兩成以下,全勝的機會就頂多得 0.34,並不值得期待。

由此可見,即使民主黨的支持度只下跌 0.01,守勢已比攻勢來得現實和明智。
圖七:民主黨的勝算曲線 ($v_\max=0.13$)
若支持度下降到 95% 信賴區間的下限 0.11 的話,情況就更嚴重了。見圖八。兩條曲線圍成一個紅色的死亡大三角,民主黨全勝的機會頂多只有三成,全滅風險卻可以高達七成。若如上例般,想將全滅風險保持於兩成以下,則全勝機會最多只剩 4%。若這樣的情況下仍希冀全勝,簡直異想天開,棄車保帥才是唯一合理策略。
圖八:民主黨的勝算曲線 ($v_\max=0.11$)
討論
以上各種情形顯示,若民主黨的支持度真的達到如選前最後兩次民意調所指的 14%,它不棄車保帥,還算合理。今次選舉,結果民主黨的得票率只有 11.77%。如果我們據此指摘民主黨之前過份樂觀的話,只是事後孔明。然而,按九月七日的民調結果,只要民主黨的總得票率下降 0.01,全攻型策略已經變成不夠現實。鑑於民主黨的全勝機會對總體得票率太過敏感,而民意調查結果及配票也會出現誤差,因此,除非主事人懷着 wishful thinking,或者於九月七日民調結果公布後,認為自己有可靠方法提高總得票率,否則,為免全滅,民主黨當時是應該棄車保帥的。

(至於誰是車,誰是帥,就很難說。我自己就比較希望棄李保陳,但這是另話。)

既然選舉結果已經揭盅,我們難免要事後孔明一番。民主黨於新界西最後得票率為 0.1177,李永達為 0.0658。憑過往經驗,這個情況的勝算有幾高?見下圖。
圖九:事後孔明圖 ($v_\max=0.1177, v=0.0658$)
Fate/Legco
有人指摘余若薇參選分薄了民主黨票源,連累民主黨全滅。余若薇分薄了民主黨票源固然是事實,然而,根據上述分析結果,按當時形勢,民主黨是應該棄車保帥的。它最後得票 11.77%,九月七日的民調結果則為 14%,兩者都夠一張名單越過安全線。要避免全滅,保持原有的一席,技術上十分容易,但它沒有這樣做。因此,今次全滅完全是民主黨自己的責任,與人無尤。

然而,亦有人說,若余若薇不參選(或者不落力競選第二席,而只是保郭家麒當選),則民主黨可全取兩席。故此,就算李永達落選的責任不在余若薇,她仍是連累了陳樹英丟了另一席。

我不能同意這種論調。誠然,若余若薇不參選,就算支持余若薇的票並不完全流向民主黨,添給陳樹英的部份應該也足夠令她當選。事後看來,要將余若薇的票過給李永達與陳樹英,令民主黨取得兩席,亦比將陳樹英的票過給李永達與余若薇,令他們連任容易。然而,說余若薇連累陳樹英,講到這個議席彷彿本來就屬於陳樹英一樣,是十分奇怪的。若問余若薇為何不退選,為何不反過來問,何以陳樹英不退選?候選人參選,是為了提供一個選擇給選民;選民投票,是為了選出能夠代表他們的議員。議席並非議員的私有物,民主派的候選人,對選民來說,更非隨便一個也可以代表他們,個個一樣的替代品。即使議席是議員的私有物,余若薇本來就有一個議席,她有何義務要將議席拱手相讓給本來並無議席的陳樹英?

有兩夫婦與一位鄰居遇到海難,三人各乘一艘只載一人的充氣快艇逃生。大海茫茫,暴風雨迫近。他們估計所餘燃料只夠二人逃走,究竟誰要犧牲?最後三人相持不下,全數沒頂,這是誰的責任?

有人指摘該名鄰居不肯自我犧牲,成全兩夫婦。你話呢?

參考網頁
伸延閱讀

2012年9月15日星期六

Normal approximation of multinomial distribution

How to simulate relative frequency outcomes of a multinomial experiment using normally distributed random numbers? The answer is surprisingly simple, but for some curious reason, the answer is seldom mentioned on the internet.

Let $\mathbf{X} = (X_1, \ldots, X_m) \stackrel{\textrm{i.i.d.}}{\sim} \textrm{Multinomial}(n, \mathbf{p})$, where $\mathbf{p}=(p_1,\ldots,p_m)$ is a probability vector whose entries sum to 1. In other words, we are talking about $n$ independent trials of a multinomial experiement, in which the probability of getting outcome $i\in\{1, 2, \ldots, m\}$ in each trial is $p_i$, and $X_i$ is the frequency count for outcome $i$ after all $n$ trials are completed. We have the following:

Theorem. Let $u = (\sqrt{p_1},\ldots,\sqrt{p_m})$ and $Q$ be a real orthogonal matrix whose last column is $u$. Suppose $Z_1, \ldots, Z_{m-1}$ be i.i.d. standard normal random variables. Then
$$
\mathbf{X}^\ast = \left(
\frac{X_i-np_i}{\sqrt{np_i}}
\right)_{1\le i\le m}
\stackrel{d}{\longrightarrow}\quad Q \begin{bmatrix} Z_1\\ \vdots\\ Z_{m-1}\\ 0\end{bmatrix}
$$as $n\rightarrow\infty$.

Proof. See sec. 11.1 of Hans-Otto Georgii (2007), Stochastics: Introduction to Probability and Statistics, Walter de Gruyter, Berlin.

*****************************
Note that the denominator of the $i$-th entry of $\mathbf{X}^\ast$ in the above theorem is $\sqrt{np_i}$, not the usual $\sqrt{np_i(1-p_i)}$ we see in the normal approximation formula to binomial distribution. We will immediately see that the binomial case is just a special case of the above general formula. Let $m=2$ and write $\mathbf{p}=(p,q)^\top$. Take $Q$ as $\begin{pmatrix}\sqrt{q} & \sqrt{p}\\ -\sqrt{p} & \sqrt{q}\end{pmatrix}$. So, the above theorem says that
$$
\begin{bmatrix} \frac{X_1-np}{\sqrt{np}}\\ \frac{X_2-nq}{\sqrt{nq}}\end{bmatrix}\stackrel{d}{\longrightarrow}
\begin{pmatrix}\sqrt{q} & \sqrt{p}\\ -\sqrt{p} & \sqrt{q}\end{pmatrix}
\begin{bmatrix} z\\ 0\end{bmatrix}= \begin{bmatrix} \sqrt{q}\,Z\\ -\sqrt{p}\,Z\end{bmatrix}.
$$Hence, by Continuous Mapping Theorem, we can divide both sides entrywise by $(\sqrt{q}, -\sqrt{p})^\top$ and get
$$
\begin{bmatrix} \frac{X_1-np}{\sqrt{npq}}\\ \frac{nq-X_2}{\sqrt{npq}}\end{bmatrix}

\stackrel{d}{\longrightarrow}
\begin{bmatrix} Z\\ Z\end{bmatrix}.$$
Since $X_1+X_2= n$, we have $nq-X_2=X_1-np$. Hence the above convergence reduces to the familiar normal approximation formula to binomial distribution.

The theorem requires the use of a real orthogonal matrix $Q$ whose last column is $u$. How to construct such a matrix? See my previous blog entry.

By the theorem, the covariance matrix of the approximating distribution is given by $Q\ \mathrm{diag}(1,\ldots,1,0)\ Q^\top = I-uu^\top$. This matrix is, of course, degenerate because the $X_i$'s are not independent of each other (as $\sum_{i=1}^m X_i=n$).

2012年9月13日星期四

大佬

電影《野獸刑警》其中一幕,江湖大佬 Roy 因事著草,本來做細嘅釘華自作主張,搞埋D Roy 一直都唔老黎嘅生意,而成班o靚都改口叫佢做大佬。後來 Roy 著完草返來,上門搵釘華,一邊講返以前點樣帶佢出身,一邊教訓佢,想佢認錯。

Roy:如果你夠膽同我講,以後唔認我做大佬?我等你。
釘華:(感動大喊)大佬!
(忽然,㩒釘華一手將牛肉刀劈進 Roy 頸中。)
(Roy 倒地,一命嗚呼。)
釘華:大佬,你以後都係大佬,你以後都係我大佬!邊個係大佬有乜關係!我又係大佬,你又係大佬!我上咗來呀,點可以落返來呀

李慧琼:你話係咪呀,劉江華,大佬!

2012年9月9日星期日

A handy completion of orthogonal matrix from a column vector

Given a vector $u=(u_1,u_2,\ldots,u_n)^\top$, we seek to construct an orthogonal matrix $Q$ whose last column points to the direction of $u$.

Provided that $u_n$ is not close to $\|u\|$, the Householder reflection $Q = I - 2\frac{vv^\top}{\|v\|^2}$ will do, where
$$
v = u - \|u\|\begin{bmatrix}0\\ \vdots\\0\\1\end{bmatrix}.
$$
Update: When $u_n\approx\|u\|$, how stable is this construction? Clearly, if $u=\pm(0,\ldots,0,1)^\top$, we can set $Q=\mathrm{diag}(1,\ldots,1,\pm1)$, but what if $u_n$ is much larger than other $u_i$s?

積薄而為厚,聚少而為多

投票是很奇妙的事,明明每人手中一票中都無法左右選舉結果,集合起來卻可以非常有力。「反國民教育」運動 ── 姑勿論閣下立場 ── 已經戲劇性地顯露「積少成多」這個道理的驚人效果。此運動尚且要民間逐小推動,相比之下,現在立法會選舉已有政府好好安排,想投邊個就邊個,想投白票就白票,咁鬼着數,如此就手,今次香港人又會否浪費?星期日晚自有分曉。