38308 賭徒輸光問題中的決策優化

終極密碼

遊戲規則:本遊戲為猜密碼的遊戲。密碼為0到100之間的其中1個整數,電腦會提示密碼的所在範圍,玩家必須在6次之內猜到密碼才能過關。
★ 終極密碼為0到100之間 ★
您共有六次機會

摘要: 「賭徒輸光問題」是隨機漫步 (Random Walk) 理論中一個典型問題, 主要探討在由兩名博弈者參與、 單回合勝率及雙方賭本給定的情況下, 博弈者各自的首先輸光賭本的概率。 本文對該問題相應的決策進行研究, 建立了通過增加賭本降低輸光概率的量化優化方法, 並證明在特定情況下, 博弈中單回合勝率處於劣勢的一方將無法通過增加賭本持續降低自己輸光的概率, 得出了放棄繼續增加賭本或放棄參與博弈的條件。

關鍵詞: 賭徒輸光問題、 隨機漫步、 停止規則。

1. 引言

「賭徒輸光問題」是隨機過程 (具體為 Markov Process) 中的一個經典問題, 常見的對「賭徒輸光問題」的描述如下: 兩賭徒甲、乙進行多回合賭博。 賭徒甲有 $a$ 元, 賭徒乙有 $b$ 元, 每賭一局輸者給贏者 1 元, 沒有和局, 直到兩人中有一個輸光為止。 設在每一局中, 甲贏的概率為 $p$, 輸的概率為 $q=1-p$ (即單回合勝率已給定), 求甲輸光的概率 (由對稱性可知, 使用完全相同的方法也可求得乙輸光的概率) 。

可見, 「賭徒輸光問題」的實質是帶有兩個吸收壁的隨機漫步問題。 將該問題抽象化, 可表述如下: 如圖1, 在 $x$ 軸上有一個質點, 受到一個外力的隨機作用, 以概率 $p$ 向右或以概率 $1-p$ 向左移動一個單位。 設吸收壁在 $x=0$ 和 $x=c$ ($c=a+b$), $t=0$ 時質點位於 $a$, 求質點在 $x=0$ 處(或 $x=c$) 被吸收的概率。

圖1:

「賭徒輸光問題」有著一定的現實背景。 本文著力於研究該問題中的決策優化。

2. 該問題的相關公式

設賭本為 $x$ 的博弈者先輸光的概率為 $u_x$, 其它假設、條件及符號均同引言中的第一種表述, 由參考文獻 中相關推導可給出如下結果:

  1. 當甲乙雙方單回合勝率相等, 即 $p=q$, 甲輸光的概率為 \begin{equation} u_a=1-\frac{a}{a+b}=\frac b{a+b}\label{2.1} \end{equation} 即在 $p=q$ 的情況下, 甲輸光的概率與對手的賭本 $b$ 成正比, 直觀的描述即賭本小者輸光的概率更大。

    甲、乙在這種情況下的地位對稱, 所以乙輸光的概率為 \begin{equation} u_b=\frac{a}{a+b}\label{2.2} \end{equation}
  2. 當甲、乙雙方單回合勝率不等, 即 $p\not= q$, 令 $c=a+b$, $r=\dfrac qp$, 則甲輸光的概率為 \begin{equation} u_a=\frac{\Big(\frac qp\Big)^a-\Big(\frac qp\Big)^c}{1-\Big(\frac qp\Big)^c}=\frac{r^a-r^c}{1-r^c}\label{2.3} \end{equation} 由對稱性可得乙輸光的概率類似。

在上述兩種情況中, 均有 $u_a+u_b=1$, 即在兩種情況下都總會有一人輸光。

3. 該問題中的決策優化

3.1. 通過增加賭本降低自己首先輸光的概率

一般情況下, 博弈雙方的單回合勝率不一, 兩者相同的理想情況極少出現。 而且, 在單回合勝率相同 (即 $p=q$) 的情況下, 根據前一節分析, 雙方輸光的概率僅取決於其賭本的多少, 賭本多者占據絕對優勢。 對應圖1, 博弈雙方勝率相同的情況相當於質點左右移動的概率相等, 可以直觀看出, 若 $p=q$, 則質點到達某一個吸收壁的概率大小只與它的初始位置有關。 為規避輸光的結果, 博弈者只需盡量多地籌集賭本, 而沒有其它對決策做出優化的餘地。

如果博弈參與者對自己的單回合勝率 $p$ 有較悲觀的估計, 即 $p\lt q$, 則因 $u_x$ 不僅與單回合勝率相關, 同時也受賭本量的影響, 博弈者可通過盡量增加自己的賭本彌補單回合勝率上的劣勢。

前文通過引用給出了雙方勝率不相等 ($p\not=q$) 情況下的相關公式, 即 \eqref{2.3} 式, 其中 $p$、 $q$ 分別為甲、乙的勝率 ($q=1-p$), $r=\dfrac qp$, $a$、 $b$ 為甲、乙各自的賭本, $c=a+b$。

對 \eqref{2.3} 式進一步化簡, 得 \begin{equation} u_a=\frac{r^a-r^c}{1-r^c}=1-\frac{1-r^a}{1-r^c}\label{3.1} \end{equation} 這裏考慮乙的勝率大於甲的勝率 ($p\lt q$) 的情況。 取定一定的數值進行模擬, 取 $r=\dfrac qp=1.01$, $b=50$, 可得如圖 2 的結果

圖2:

由圖2可看出, 隨著甲方的賭本 $a$ 持續增加, 其輸光的概率 $u_a$ 隨之降低。 可見在一般情況下, 增加自己的賭本可以彌補單回合勝率上的劣勢。

令 $u_a=u_b=0.5$, 即甲、乙雙方輸光的概率相等, 則由 \eqref{3.1} 式可得 \begin{eqnarray} \frac 12&=&1-\frac{1-r^a}{1-r^{a+b}}\nonumber\\[-8pt] &&\label{3.2}\\[-8pt] 1-2r^a&=&-r^{a+b}\nonumber \end{eqnarray} \eqref{3.2} 式是關於 $a$ 的隱函數, 在勝率比 $r=\dfrac qp$、 乙方賭本 $b$ 已知的情況下, 則可解得 $a$, 即求得甲方需要准備多少賭本才能使雙方在博弈中的地位平等。 而在這一基礎上, 甲方繼續增加賭本有可能使得自己輸光的概率小於乙方, 獲得博弈中的優勢地位。

這也就建立起了該類博弈的量化評估及優化方法。

3.2. 增加賭本失去意義的情況

直覺判斷一般會認為持續增加賭本可幫助將自己輸光的概率持續降低, 但通過更大範圍的數值模擬可發現該概率隨賭本的單調變化呈收斂的狀態。 即在某些情況下持續增加自己的賭本對降低自己輸光的概率將會失去效用。

為得到這一現象的原因, 進一步分析 \eqref{3.1} 式。 考慮乙方勝率大於甲方的情況, 即 $q\gt p$, 則 $r\gt 1$, 可得 \begin{equation} \lim_{a\to +\infty}u_a=\lim_{a\to +\infty}\Big(1-\frac{1-r^a}{1-r^{a+b}}\Big)=1-\frac 1{r^b}\label{3.3} \end{equation} \eqref{3.3} 式說明了 $u_a$ 的極限是一個以 $r$ ($r=\dfrac qp$)、 $b$ 為自變量的函數, 與 $a$ 無關。 這也就從分析的角度證明了在甲方賭本 $a$ 增大到一定量之後, 甲方輸光的概率 $u_a$ 將穩定在某一確定值 (即 $u_a$ 的極限), 且該值只與 $r$、 $b$ 有關。

結合 \eqref{2.3} 式, 可得 \begin{equation} 1-\frac 1{r^b}=\frac{r^a-r^{a+b}}{1-r^{a+b}}\label{3.4} \end{equation} 在相關條件已知的情況下, \eqref{3.4} 式可認為是關於 $a$ 的隱函數, 對其求解, 則可得出甲方應該出的最高的賭本 $a^*$ ($a^*\not=0$)。 當 $a=a^*$, 甲方已將自己輸光的概率降低到了能夠達到的最小程度, 繼續增加賭本也已無意義。

而由 \eqref{3.3} 式也可驗證, 在某些情況下, 甲方無論如何增加自己的賭本, 都不可能使自己在與乙方的博弈中處於平等的地位, 即 $u_a$ 恒大於0.5。 這時甲方也應重新衡量自己是否與乙方進行博弈。

3.3. 對最優停止規則的分析

「賭徒輸光問題」一般說明在賭本小於對方的情況下, 即使勝率比為1 ($p=q$), 仍應放棄參與該博弈。 但如果在參與博弈之前制定如下停止規則:"甲方贏得乙方 $d$ 元後, 可選擇停止博弈, 其中 $d\lt a$" (其它假設、條件及符號均同引言中對「賭徒輸光問題」的第一種描述) , 則此時即使甲方賭本 $a\lt b$, 但因 $d\lt a$ (即相當於通過停止規則將乙方資本由 $b$ 降為了 $d$, $d\lt a\lt b$) , 甲方仍可在該博弈中占據優勢。

這說明了在類似「賭徒輸光問題」這樣的博弈過程中, 擁有"中止博弈"這一權力所能帶來的巨大效益。 在對應的現實問題中, 例如商業合同的制訂中, 應盡力爭取以及謹慎賦予對方"中止某項協議"的權力。

致謝: 作者謹此感謝北京林業大學數學系講師司林博士的無私幫助與指導。

參考文獻

劉次華, 隨機過程及其應用 (第三版), 北京:高等教育出版社, 2004。 刁在筠, 劉桂真, 宿潔, 馬建華, 運籌學 (第三版), 北京:高等教育出版社, 2007。 Kai Lai Chung, A Course in Probability Theory, Elsevier Inc., 2001. 劉嘉焜, 王公恕, 應用隨機過程 (第二版), 北京:科學出版社, 2004。

---本文作者就讀北京林業大學理學院數學系---