隨機賽程的最佳策略 (第 3 頁)

　1│2│3│4　

隨機賽程的最佳策略（第 3 頁）

蕭正堂

首頁 | 搜尋

．原載於科學月刊第十三卷第十二期
．作者當時任教於交大應數系
‧對外搜尋關鍵字

本文

問題的敘述雖很簡單，但細思之下，卻發現其並不很簡單。這道理不難明白，因為可下注的方法實在太多了，要一一比較是不可能的。

為了要克服上面所說的困難，數學家首先考慮幾種比較可能為人們採用的方法，這些方法所以較常採用，泰半是由於直覺上認為它們可被採行。當然，直覺的認定往往是不可靠的，所以最好能有理論支持。下面就介紹三種可能的方法，並比較其優劣。

: 方法一、每次甲均下賭注 1 元。（顯然，這樣的下注法最保守，我們稱之為保守型下注法。）
: 方法二、首先甲下 1 元賭注。若他贏了，則下次仍下 1 元；若輸了，則將賭注加倍，依此類推。換言之，往後只要一贏，他就下 1 元，否則就把下注金額加倍。當然，我們假設所下金額是合理的。（顯然持這種下法的理由是因為只要一贏，那麼非但所有輸的金額即全撈回來，並且反多贏 1 元，我們姑且稱之為輸不起型下注法。）
: 方法三、只要許可，甲就將所有賭本下注，因此只要一輪，某甲就血本無歸。（顯然這種方法是最大膽的，我們就稱之為極端型下注法。）

你會採用哪種方法呢？能說個道理出來嗎？事實上，答案並不簡單，它跟 p 究竟大於、等於或小於 1/2 有關，也即跟你是否比莊家強有關。我們就舉 c=2 的例子來說明。為方便計，我們以「＋」表甲贏，以「－」表甲輸，並以＋、－所形成之中列表示甲在整賽局輸贏的順序。

首先我們考慮保守型下注法，此時只有在下列諸場合，甲才會贏（即莊家賭本輸光）。

++,
+-++,-+++,
+-+-++,+-+++,-++-++,-+-+++,
$\vdots$ $\vdots$ $\vdots$ $\vdots$ 。
在第一列＋＋中，甲連贏兩次，此次機率為 $p\cdot p=p^2$ 。在第二列中，甲贏了三次，輸了一次，並且有兩種可能性，所以其機率為 $2\cdot p^3\cdot q=2p^3q$ （q 為輸的機率，故 p+q=1）。依此推導可得在第 n 列中，甲贏了 n+1 次，而輸了 n-1 次，並且有 2^n-1 種可能性，所以其機率為 2^n-1pⁿ⁺¹q^n-1。因此可得在整個賽局中，甲贏的機率為

$\begin{eqnarray*} & & p^2+2p^3q+\cdots+2^{n-1}p^{n+1}q^{n-1}\\ &=& p^2(1+2pq+4p^2q^2+\cdots+2^{n-1}p^{n-1}q^{n-1})\\ &=& \frac{p^2}{1-2pq} \end{eqnarray*}$

現在讓我們考慮輸不起型下注法。此時只有在下列諸場合，甲才會贏。

++,+-+,
-+++,-++-+,（注意：甲第二次僅能下注 1 元）
-+-+++,-+-++-+,

$-+-+\cdots-+++$ , $-+-+\cdots-++-+$ ,
。

仿上之計算，可得此時甲贏的機率為

$\begin{eqnarray*} &&(P^2+p^2q)+pq(p^2+p^2q)+p^2q^2(p^2+p^2q)+\cdots\\ &=&(p^2+p... ...\quad\mbox{{\fontfamily{cwM0}\fontseries{m}\selectfont \char 1}} \end{eqnarray*}$

最後設某甲採極端法，則甲第一次即下注2元，因此一次就決定了輸贏，所以甲贏的機率為 p 。

現在我們再回到原問題：究竟在這三種方法中，以那種方法最好？由於相對應贏的機率公式已求得，所以我們只需將 p 值代入，進而比較其大小即可，舉例來說，當 $p=\frac{1}{2}$ 時，三者之值皆為 $\frac{1}{2}$ ；而當 $p=\frac{2}{3}$ 時，三者之值依序為 $\frac{4}{5}$ 、 $\frac{16}{21}$ 、 $\frac{2}{3}$ ；至於當 $p=\frac{1}{3}$ 時，則其值依序為 $\frac{1}{5}$ 、 $\frac{5}{21}$ 、 $\frac{1}{3}$ 。這些數值告訴我們，當 $p=\frac{1}{2}$ 時，三種下注法沒影響甲贏的機會；當 $p=\frac{2}{3}$ 時，則以保守法較好；當 $p=\frac{1}{3}$ 時，卻以極端法最佳，保守法最差。

這些結論，是不是有些出你意料呢？其實問題還沒全部解決，迄今我們僅就保守、輸不起、極端三型來作比較。是否尚有其他型的下注法會使得答案更好？還有，我們僅就特例來考慮，在一般的情形下，答案又是怎樣呢？

現在，先把最一般性的結果寫在下面，其中 $\nu(i)$ 代表當甲有 i 元時會贏的機率。

: 情況一： $p=\frac{1}{2}$
此時不論甲如何下注， $\nu(c)$ 恒等於 c/(m+c)。
: 情況二： $p>\frac{1}{2}$
此時不論甲如何下注， $\nu(c)\leq[1-(\frac{q}{p})^c]/[1-(\frac{q}{p})^{m+c}]$ ，而右端為保守型下注法贏的機率。因此，在此情況以保守型的下注法為最穩當。另一方面，極端下注法的贏面最低。
: 情況三： $p<\frac{1}{2}$
此時以極端法最佳，保守法最差。同樣地，保守型下注法贏的機率為 $[(\frac{q}{p})^c-1]/[(\frac{q}{p})^{m+c}-1]$ 。

現在我們就來研究，為什麼會有這個結論！這用到了一些數學工具，不過對其中較複雜的部分，因顧及本文的可讀性，筆者只很扼要的敘述一下。

由於在上面的結論裏，保守法處於一個居中的地位，所以我們先就此法進行討論，然後再進一步研究整個問題。

如同以前， $\nu(i)$ 代表當甲所擁有的資本達 i 元時，他會贏的機率。由於甲及莊家的總資本額為 m+c 元，所以 i 之可能值為 i = 0, 1, …, m + c。顯然地， $\nu(0)=0$ ， $\nu(c+m)=1$ ，而 $\nu(c)$ 為我們最早所想求得之機率。

情況一： $p=\frac{1}{2}$

假定某甲現有 i 元，那麼有 $\frac{1}{2}$ 的機會，他的資本會成為 i+1 或 i-1 元。因此

$\begin{eqnarray*} \nu(i) &=& \frac{1}{2}\nu(i+1)+\frac{1}{2}\nu(i-1) \\ && \quad i=1,2,\cdots,m+c-1 \end{eqnarray*}$

這樣的函數 ν，在數學上是一個線性函數，因此解的通式為 $\nu(i)=a+bi$ 。由於， $\nu(0)=0$ 、 $\nu(c+m)=1$ ，得 a=0、 $b=\frac{1}{c+m}$ 。因此 $\nu(c)=\frac{c}{m+c}$ ，亦即甲的贏面為 c/(m+c)。

情況二： $p>\frac{1}{2}$

令 q=1-p。此時對 ν 我們有方程式

$\begin{eqnarray*} \nu(i) &=& p\nu(i+1)+q\nu(i-1) \\ && \quad i=1,2,\cdots,m+c-1 \end{eqnarray*}$

這樣的一組方程式，在數學上稱作是差分方程式。它也有一個求解的一般方法，但其道理較深。為此之故，我們特採用下面的方法。

利用p+q=1，上組方程式可改寫為

$\begin{eqnarray*} && \nu(1)-\nu(0)=\nu(1)-\nu(0) \\ && \nu(2)-\nu(1)=\frac{q}{p... ...\ && \nu(m+c)-\nu(m+c-1) = (\frac{q}{p})^{m+c-1}[\nu(1)-\nu(0)] \end{eqnarray*}$

兩邊相加，並利用 $\nu(m+c)=1$ 、 $\nu(0)=0$ ，得

$\begin{displaymath} 1=\frac{1-(\frac{q}{p})^{m+c}}{1-\frac{q}{p}}\nu(1)\quad\mbo... ...uad\mbox{{\fontfamily{cwM0}\fontseries{m}\selectfont \char 1}} \end{displaymath}$

若取前 c 項相加，則得

$\begin{displaymath} \nu(c)=\frac{1-(\frac{q}{p})^c}{1-\frac{q}{p}}\nu(1)=\frac{1... ...uad\mbox{{\fontfamily{cwM0}\fontseries{m}\selectfont \char 1}} \end{displaymath}$

情況三： $p<\frac{1}{2}$

仿二之解法，可求得

$\begin{displaymath} \nu(c)=\frac{(\frac{q}{p})^c-1}{(\frac{q}{p})^{m+c}-1}\quad\mbox{{\fontfamily{cwM0}\fontseries{m}\selectfont \char 1}} \end{displaymath}$

保守法的 $\nu(c)$ 已求得，現在我們來研究為什麼在情況二時，以保守下注法的 $\nu(c)$ 為最大；而在情況三時，反以保守下注法的 $\nu(c)$ 為最小；同時另一方面，在情況二時，則無論何種下注法， $\nu(c)$ 皆一樣。

首先我們引進一個定理。令 S_n 代表在第 n 次賽局時，甲所擁有之資本額，因此 S_n 是一個隨機變數。我們並設 S₀=c，即原資本。令 N 表結束賽局所需之時間，因此 S_N=0 或 c+m。我們並以 E 表期望值。

定理：: 設 f 為一定義於 S_n 上之有界函數。若在 S_n 之條件下，f(S_n+1) 之期望值 E[f(S_n+1)] = f(S_n)，則 E[f(S_N)] = f(S₀) = f(c)。若將「=」改為「 $\geq$ 」，則結論亦真。

此定理在機率學上，即著名的選擇樣本定理 (optional sampling theorem)，它的證明已超過本刊程度，所以略去不證，但它的直觀意義卻不難了解。就拿「=」的情形來說，其實是說若你的第 n+1 次賽局，平均而言並不能改變在第 n 次賽局時 f 之值，則當整個賽局結束時，f 的平均值也與原先值一樣。另一方面，若在「 $\geq$ 」的情況，亦即你的第 n+1 次賽局平均而言會改進 f 先前之值，則當賽局結束時，f 的平均值也曾比原先值為佳。

現在我們就拿這定理來證明先前我們所下之結論。

首先，我們考慮情況一。此時取 f(S_n)=S_n，則不論對何種下注法，因勝負機會均等， $p=q=\frac{1}{2}$ ，所以若給定 S_n，則 ES_n+1 = S_n。因此由上定理知 ES_N = c。但 $ES_N = (c+m)\nu(c)+0[1-\nu(c)]$ = $(c+m)\nu(c)$ ，所以知不論以何種方法， $\nu(c)=\frac{c}{c+m}$ 。

至於在情況二或三時，我們取 $f(S_n)=(\frac{q}{p})^{S_n}$ 。此時若給定 S_n，則

$\begin{eqnarray*} E[f(S_{n+1})] &=& E[(\frac{q}{p})^{S_{n+1}}] \\ &=& (\frac{... ...{-a}q] \\ &=& f(S_n)[(\frac{q}{p})^ap+(\frac{p}{q})^aq]\quad , \end{eqnarray*}$

其中 $a\geq1$ 為所下注之金額。利用

$\begin{displaymath} (\frac{q}{p})^a p + (\frac{q}{p})^a q \geq (\frac{q}{p}p + \frac{p}{q}q)^a = 1 \quad , \end{displaymath}$

可得不論以何種下注法下注，若給定 S_n，則 $E[f(S_{n+1})]\geq f(S_n)$ 。所以由定理知 $E[f(S_N)]\geq(\frac{q}{p})^c$ 。但

$\begin{eqnarray*} E[f(S_N)] &=& E[(\frac{q}{p})^{S_N}]\\ &=& (\frac{q}{p})^{m... ...{p})^0[1-\nu(c)]\\ &=& 1-[1-(\frac{q}{p})^{m+c}]\nu(c) \quad , \end{eqnarray*}$

因此可得在情況二， $p>\frac{1}{2}$ 時，

$\begin{displaymath} \nu(c)\leq\frac{1-(\frac{q}{p})^c}{1-(\frac{q}{p})^{m+c}} \quad ; \end{displaymath}$

而在情況三， $p>\frac{1}{2}$ 時，

$\begin{displaymath} \nu(c)\geq\frac{(\frac{q}{p})^c-1}{(\frac{q}{p})^{m+c}-1}\quad\mbox{{\fontfamily{cwM0}\fontseries{m}\selectfont \char 1}} \end{displaymath}$

但 $[1-(\frac{q}{p})^c]/[1-(\frac{q}{p})^{m+c}]$ 為採用保守下注法時贏的機率，所以知在情況二時，以保守法的 $\nu(c)$ 為最大；但在情況三時，卻以保守法的 $\nu(c)$ 為最小。

至於為什麼在情況二時，以極端法的贏面為最低；但在情況三時，卻以極端法的贏面為最大。這其中又牽涉到更深的理論，只好從略了。

　1│2│3│4　


	（若有指正、疑問……，可以在此留言或寫信給我們。）

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有

編輯：黃信元

最後修改日期：2/17/2002