MergedFile

Size: px

Start display at page:

Download "MergedFile"

称颜
5 years ago
Views:

1 電腦程式賭徒破產問題之平均回合數探討投稿類別 : 數學類篇名 : 電腦程式賭徒破產問題之平均回合數探討作者 : 林冠璋北大高中二年六班指導老師 : 黃冠閔老師沈昌懋老師

2 壹前言一研究動機延續我之前小論文電腦程式賭徒破產問題中隱藏的數學原理中玩家贏的機率之研究, 兩玩家輪擲一不公正銅板, 每回合皆以擲出正反面來決定勝負, 再次令我感興趣的是平均要幾回合賭局才會結束呢? ( 即有一方的籌碼歸零 ), 因此我重新撰寫程式語言 C 來模擬不公平的賭局, 透過觀察實驗的數據, 開始研究此問題, 使用矩陣對角化的方式, 試圖找尋與推導其平均回合數之通式並驗證通式之準確性二研究目的關於本研究目的為撰寫電腦程式語言 C 來模擬數學問題, 利用矩陣對角化的觀點切入 : ( 一 ) 探究兩位玩家籌碼共有 m 元且每回合得勝之機率分別為 p 與之情況下, 其中 p, p ( 即不公平 ), 推導平均回合數之通式 ( 二 ) 利用數學軟體 Mahemaica 運算的協助來驗證其所推導出的通式之準確性三研究設備與器材紙筆電腦電腦程式語言 C Excel 數學軟體 Mahemaica 四研究架構圖

3 貳正文一名詞定義 ( 一 ) 破產 : 玩家的籌碼歸零 ( 二 ) A i : 進行回合後, 玩家 A 在有 i 元的機率二研究過程 ( 一 ) 賭徒破產問題 (gamblers rui problem) 兩玩家 A 與 B 輪擲一不公正銅板, 此銅板出現正面之機率為 p, 出現反面的機率為, 每回合皆以擲硬幣的方式來決定勝利與失敗若為正面, 則玩家 A 獲勝 ; 若為反面, 則玩家 B 獲勝, 每回合中失敗的一方必須給獲勝的一方一塊錢, 遊戲將不斷重複進行直到有一方破產今玩家 A 有 m 元, 玩家 B 有元, 則一場賭局中平均會進行幾回合? ( 二 ) 運用電腦程式語言 C 呈現賭徒破產問題我們利用程式語言 C 撰寫賭徒破產問題, 以下為程式流程圖 ( 圖一 ): 圖一: 賭徒破產問題之程式流程圖

計算平均值之程式碼這裡我舉一個例子, 設定兩玩家的籌碼總和為 8 元, 測試次數為次, 每次測試中, 模擬的局數為局, 程式碼會將每次結果之 A 贏的機率玩家 B 贏的機率與平均回合數顯示結果於電腦銀幕上並將前次等平均之結果寫入文字 TXT 檔中 ( 如圖三 ) 圖五 : 顯示結果於電腦銀幕上的程式碼與跑出的結果

4 程式運行中, 當測試次數 ( 變數 ) 模擬的局數 ( 變數 ) 尚未達到最大值時, 主要是使用已經宣告好的變數 a ( 即玩家 A 的籌碼 ) 與變數 b( 即玩家 B 的籌碼 ) 來當是否繼續執行程式的依據, 其中 rad( )%3 的值可能為與, 若值等於, 則玩家 A 獲得元, 玩家 B 失去元 ; 若值為或時, 則反之, 其實就是在模擬機率分別為與之情況, 用變數 roud 來存取回合數 ( 如 3 3 圖二 ) 每一局中, 當經過數回合後, 有一玩家的籌碼歸零時賭局就會結束, 再利用陣列 R 來存取 roud( 如圖二 ), 最後計算次測試後的平均回合數之平均值圖二 : 變數 roud 來存取回合數與利用陣列 R 計算平均值之程式碼這裡我舉一個例子, 設定兩玩家的籌碼總和為 8 元, 測試次數為次, 每次測試中, 模擬的局數為局, 程式碼會將每次結果之 A 贏的機率玩家 B 贏的機率與平均回合數顯示結果於電腦銀幕上並將前次等平均之結果寫入文字 TXT 檔中 ( 如圖三 ) 圖五 : 顯示結果於電腦銀幕上的程式碼與跑出的結果寫入文字 TXT 檔之示意圖我嘗試代入以下的籌碼數, 機率與平均回合數皆為前次的平均值, 整理製成 ( 表一 ) 如下 : 玩家 A 的籌碼玩家 B 的籌碼平均回合數接著以下的研究, 我會來探究平均回合數之一般通式, 並驗證通式之準確性 3

5 ( 三 ) 探究平均回合數之一般通式假設賭局中兩人每回合輪擲一不公正銅板, 出現正面之機率為 p, 反面之機率為, 其中 p, p ( 即不公平 ), 令玩家 A 與 B 一開始分別有 m 元與元, 其中 m, m ; 若出現正面, 玩家 B 給玩家 A 一元 ; 出現反面, 則反之, 直到某一方破產為止, 以下討論將推導平均回合數之一般通式承上述之題意, 我有初始條件 A ( m), A ( i), i m, 如果玩家 A 持有元或 m 元時, 再一回合後變成元或 m 的機率分別為與 p, 即在這兩種情況下賭局就會結束, 因此根據期望值的定義, 可得到平均回合數之列式如下 : A () p A ( m ) ( 式 ) 接下來為了得到 ( 式 ) 中 A () 與 A ( m ) 之值, 先利用簡單的二元樹狀圖之概念來觀察 A () i 之間的關係如右 : 第 - A ( ) i A ( ) i 第回 p A () i 可推得當, A () i 之遞迴關係式並將之列式如下 : A() A () A ( i) p A ( i ) A ( i ), i, 3,, m A( m ) p A ( m ) 再來利用矩陣, 將 A () i 之遞迴關係式, 寫成一個 m 階方陣 P, 運算形式如下 : A A p A m p A m A m p A m, 初始條件為 A A m A m 將上式進行遞迴疊代次後可以得 A A m P A m ( 式 ) 在 ( 式 ) 中, 由於計算方陣 P 的高階次方是一件很繁複的計算, 為了由繁化簡, 我必須引入大學線性代數之矩陣對角化之觀念, 將此方陣 P 先進行矩陣對角化, 設方陣 P 之任一個非零 4

6 特徵向量為 ( m ) 的矩陣 u x x xm 先令為方陣 P 的特徵值, 考慮展開一式 m, 其中 Im 為 m 階單位方陣, P I u 為 ( m ) 的零矩陣, 上式乘開後, 比較等式的左右兩邊, 可得遞迴關係式如下 : px x x,,,, m 且 x 將上式進行化簡, 可得 m 個二階齊次線性遞迴方程式且包含邊界條件 x 如下 : xm xm p x x x,,,, m 且 x ( 式 3) xm 接下來透過裂項的方式, 可先將 ( 式 3) 變形成為其中 x r x r x r x,,,, m 且 x r與 r為常數, 整理 ( 式 4) 並與 ( 式 3) 做係數比較可得 r r ( 式 4) xm 與 r r p, 由根與係數關係得知 r 和 r 為二次方程式之兩根如右 : r 而 ( 式 5) 即為 ( 式 3) 的特徵方程式 p r ( 式 5) 若 ( 式 5) 發生重根, 即 r r, 則 ( 式 3) 的解為 x cr c r,,, m, 且 c c 為任意常數, 從 x 可解出 c c, 因此 x,,,, m, 也就是說 xm 特徵向量 u 為零向量, 這與特徵向量不得為零相互矛盾, 故推得 r r, 因此 ( 式 3) 的解為 x c r c r, 由已知條件 x 代入 x 可得 xm c c c r c r m m ( 式 6) r 由 ( 式 6) 解出 r m c c r m, 令 z, 即解 z ( 式 7) r 先由代數基本定理與因式定理可知 ( 式 7) 恰有 m 個複數根, 再應用棣美弗定理, 不難解出所有複數根為 j j z i si, i m m, j,,, m ( 式 8) r 將 z 代回 ( 式 8) 移項整理, 化簡為 r j j r r i si, i, j,,, m m m ( 式 9) 5

7 p 其中 j 不合, 因為 r r 由 ( 式 5) 之根與係數關係 rr 代入 ( 式 9), 解得再將 r r p j j p j j r i si, r i si m m m m 與之值代入 ( 式 5) 之根與係數關係 r r, 解得 p j ( r r) j,,, m m, ( 式 ) ( 式 ) 給出 m 個特徵根, j 其中 j,,, m 接下來再由 ( 式 6) 之第一式 c c r 與 r 之值代入 x, 整理可得這裡取 c / p j ( ) si x c r r ic, i,,,, m ( 式 ) m 代入 i ( 式 ) 化簡, 即可求得對應特徵根的特徵向量 u j j 之第個元素 x, 整理計算後對應的 m 個特徵向量 u j 便為 / j si m / j si u j m m / m j si m, 其中 j,,, m 接著將這 m 個特徵向量組成一 m 階方陣 U, 並發現此方陣 U 可整理成如下 : / p m si si si m m m / p m si si si U m m m m / p m m m si si si m m m 接著利用以下四個步驟 I~IV 來求矩陣 U 的反方陣, 記為 U, 過程如下 : 步驟 I: 首先考慮以下一矩陣之平方 m si si si m m m m si si si m m m m m m si si si m m m 發現其平方後, 矩陣內的每一個元素皆可整理成如下 : ( 式 ) ( 式 3) m i j si si i, j m m m, 其中 ( 式 4) 6

8 步驟 II: 為了求得 ( 式 4) 之值, 先證明一個有關三角函數的性質 : m, 若為偶數 m, 若為奇數, 其中 i 證明 : 利用尤拉公式, 考慮一複數 w e m m = i si, 其中, 則 m m i m, m m i 若為偶數 w ( e ) e i si, 若為奇數再利用上式的結果, 並計算其等比級數可得 (i) 在為偶數的情況下, 取其實部可得到又因 w 代入上式, 故可得 (ii) 在為奇數的情況下, 將所以 m m m m m i m m Re w Re e m w m, 若為偶數 w w, 若為奇數 w, 其中 Re[ ] m m Re w Re m w, 又因 m w, 故可得表示取 [] 之實部, 故得證 m 步驟 III: 利用步驟 (II) 的結果來計算 ( 式 4) 之值, 先透過三角函數積化差公式, 可將 ( 式 4) 化簡為 m w 之值化簡如下 : w w isi m m isi m m si i si m m m si i m m si si i si si i si i m m m m m m m m si i m m ico si m m m i j i j m m (i) 在 i j之情況下, 其中 i, j m, 不失一般性, 令 i j, 由於 i j必同為正偶數或正奇數, 利用步驟 II 之結果代入與計算如下 : m m m, i j i j i j i j i j 當為偶數 m m m m =, 當 i j為奇數 (ii) 在 i j的情況下, 其中 i, j m, 因為 i j= 且 i j必為正偶數, 再次利用步驟 II 的偶數情況之結果代入與計算如下 : 7

9 m i j i j m m m i j m m i j m m ( ) m m 綜合以上 (i)(ii) 之討論, 故可推得 ( 式 4) 之值整理如下 : m 步驟 IV: 將步驟 (III) 之結果代入 ( 式 3) 可得接著考慮一 m 階方陣 M 滿足一等式如下 : 其中 m, i j i j si si m m m, i j m si si si m m m m m si si si m m m m m m si si si m m m I 為 m 階單位方陣, 將 ( 式 5) 之結果代入 ( 式 6), 計算方陣 M 如下 : m m / p m si si si m m m / p m si si si m m m M I m m / p m m m si si si m m m ( 式 5) ( 式 6) / / p p m m / / p m p M Im M m m / m m / p p m 將方陣 M 之值代入 ( 式 6), 經由比較 ( 式 ) 與整理 ( 式 6) 可以推得 U : U 7 p si si si m m m m 7 si si si m m m m m m si si si m m m / p m / m / p m 經過上述四個步驟 I~IV 之討論後, 可得到 U, 再結合 ( 式 ) ( 式 ) 之結果, 將 ( 式 ) 中的方陣 P 進行對角化, 並計算方陣 P 代入 ( 式 ) 整理後如下 : p m A p A m U m U A m p m m 8

10 展開上式後, 比較等式的左右兩邊可得到, A () 與 A ( m ) 之值分別如下 : 與 m m p j m j p j A () si si j m m m m ( m) m m p ( ) si ( m ) j m j p j A m si j m m m m 最後利用 A () A ( m ) 之值與初始條件 A ( m), A ( i), i m 來討論通式如下 : 在計算平均回合數之前, 先整理出 A () 與 A ( m ) 之值的關係式, 計算過程如下 : m m m p p p ( m ) j j m j p j A ( m ) A () si si si j m m m m m j ( ) si m j si j, 當 j為奇數 j m m si, j 當為偶數 m m p p j m j p j si si, j j m m m m m 為偶數且故將等式移向整理化簡, 可得 A () 與 A ( m ) 之關係為 m m m p p p j m j p j A( m ) A() si si j m m m m p = A (), 其中 A () m j 9 m p j j m j p j ( ) si si m m m m 再利用, A () 與, A ( m ) 之值代入 ( 式 ), 整理與推導計算過程如下 : A () p A ( m ) m p A() A() p A( m ) p A() m m m p j m j p j j p A() p A( m ) si si ( ) p j m m m m m m m p j m j j p p j A() p A( m ) si si ( ) p j m m m m p j ( r, 當 r ; 因 <, 故上式中的無窮級數會收斂 ) ( r ) m j m m m p j ( m m m m p j m j j p ( m) si si ( ) p, m, 其中 ( m) A() p A( m ), m m, 此 ( 式 7) 給出平均回合數之通式 p, m m ) ( 式 7)

11 參結論一探究矩陣對角化的運算於解問題之平均回合數之一般通式 : m m m p j m j j p ( m) si si ( ) p j m m m p j ( ) m p, m m, 其中 ( m) A() p A( m ), m, m m 二利用數學軟體 Mahemaica 驗證其通式的準確性 : 依給定的賭局條件, 先利用電腦程式來測試次, 每次局, 每次的結果皆顯示在電腦螢幕上, 並將前次前次前次的平均值紀錄在文字 TXT 檔中, 方便觀察與紀錄, 再取前次的平均作為平均回合數之實際值, 再利用數學軟體 Mahemaica, 將賭局條件的參數代入平均回合數 ( 式 7) 通式, 計算出兩玩家平均回合數的理論值, 最後將實際值與理論值整理於表格中做比較, 可以明顯呈現其兩值非常地接近或甚至相同賭局條件 : p,, m 8 模擬的賭局數: 局測試次數 : 次 3 3 電腦程式跑出的實際值以通式 ( 式 7) 計算出的理論值 A 籌碼 B 籌碼平均回合數 A 籌碼 B 籌碼平均回合數肆引注資料一許志農黃森山教授高中數學課本第二冊龍騰出版二劉洲溶蘇淵源翟家甫高中資訊科技概論課本全華出版三高橋信世界第一簡單線性代數世茂出版社四洪維 C 語言教學手冊 ( 四版 ) 旗標出版

MergedFile

MergedFile 投稿類別 : 數學類篇名 : 電腦程式賭徒破產問題中隱藏的數學原理作者 : 林冠璋北大高中二年六班指導老師 : 黃冠閔老師沈昌懋老師壹前言一摘要我們通常仰賴電腦來模擬一些現象與事物, 進而找到一些規律, 達到預測或找到解決問題的方法本研究藉助電腦程式的運算來模擬一道有名的機率數學題賭徒破產問題 (gabler's run roble), 我在這些實驗的數據中, 探究其背後的數學原理,