标题: 随机赛程的最佳策略 [打印本页] 作者: 狗咬尾巴 时间: 2010-12-4 11:08 标题: 随机赛程的最佳策略 引言 4 y, J9 u. T3 Y; \) T4 T7 ` ! R! R, ~- w3 {. D0 a( R在日常生活中的许多场合,像生意的投资、决策的推行等,我们往往无法事先确知其结果,但对其成败的机会,则往往可事先估计出。这种成败的机会,也即是我们通常所说的事情成败的机率,然而使事情成功的方法不一,所以如何选用一个方法,使其成功的机率最大,是一个很值得研究的问题。本文拟就此类问题中之某型问题作一探讨。为叙述方便,作者特考虑下面的数学模型,实际生活中的模型当较此复杂得多。不过笔者为文之目的,不单是提出一个结果供读者参考,而是希望能藉着本文介绍一些简单而又实用的数学方法,让读者能一窥这些方法在这类问题中是如何被使用的。 ; z v/ {- o- g( y9 P
% M9 K; `% ]1 [
问题 , [7 d: Y }3 w9 K7 ] " W# z6 l- ?1 L0 d0 e+ Q 1 `- L. j- ~1 j, o1 c% ~( b& |有某甲持 c 元,拟与持 m 元的庄家赛局,并明定每局所下赌注至少为 1 元。设在每局中,某甲赢的机率恆为一常数 p (0<p<1)。并且我们假设只要某甲或庄家输尽,整个赛局即结束。那么某甲应如何在每局中下注,才会使他赢得庄家所有资本的机率达到最大值呢? ) s$ w* n4 X1 i h+ w: {
8 g$ X- h: J L9 ?6 E% U
当然,我们假设下注的金额是合理的,比如说若某甲现已有 8 元,而庄家只有 2 元时,那么某甲最多只能下注2元。 7 I1 P' ~3 q4 J7 f 9 `4 c3 E& x7 C- y0 C% n/ J本文 % g7 K- o; J; Z ' u. }/ N4 }& v1 P( \. C+ x0 x3 S- _# d4 | x1 Q' e
问题的叙述虽很简单,但细思之下,却发现其并不很简单。这道理不难明白,因为可下注的方法实在太多了,要一一比较是不可能的。 - N, ^- [2 Q7 S
3 u% l: z0 t# P: Y3 ]7 l为了要克服上面所说的困难,数学家首先考虑几种比较可能为人们採用的方法,这些方法所以较常採用,泰半是由于直觉上认为它们可被採行。当然,直觉的认定往往是不可靠的,所以最好能有理论支持。下面就介绍三种可能的方法,并比较其优劣。 7 y$ J. |, x. J! Q1 B1 c( d) ]8 V5 j5 Z5 S1 {8 F
- @1 ~4 r9 t, G# V
方法一、每次甲均下赌注 1 元。(显然,这样的下注法最保守,我们称之为保守型下注法。) x6 J0 C/ s4 i" _# @0 c3 D- t
方法二、首先甲下 1 元赌注。若他赢了,则下次仍下 1 元;若输了,则将赌注加倍,依此类推。换言之,往后只要一赢,他就下 1 元,否则就把下注金额加倍。当然,我们假设所下金额是合理的。(显然持这种下法的理由是因为只要一赢,那么非但所有输的金额即全捞回来,并且反多赢 1 元,我们姑且称之为输不起型下注法。) $ ~+ V; N1 O9 |7 C
方法三、只要许可,甲就将所有赌本下注,因此只要一轮,某甲就血本无归。(显然这种方法是最大胆的,我们就称之为极端型下注法。) ) T: g$ o* B p `9 D. t8 |
你会採用哪种方法呢?能说个道理出来吗?事实上,答案并不简单,它跟 p 究竟大于、等于或小于 1/2 有关,也即跟你是否比庄家强有关。我们就举 c=2 的例子来说明。为方便计,我们以「+」表甲赢,以「-」表甲输,并以+、-所形成之中列表示甲在整赛局输赢的顺序。 B+ l# U. k% m! H0 K7 [3 [* m$ x. s! k) H* Y* i; D
首先我们考虑保守型下注法,此时只有在下列诸场合,甲才会赢(即庄家赌本输光)。 3 f1 `+ s/ H1 z0 r& ] - b/ M1 k, h9 y* q6 s++, 6 {' k+ x1 u2 V0 q3 d, |8 C4 j2 F+-++,-+++, : q8 U' z" q5 W+ C# p6 [1 O3 u
+-+-++,+-+++,-++-++,-+-+++, 6 u2 E& y' @* z0 R( _0 s+ o
。 5 H. v0 B6 ~/ V* W, K6 d在第一列 ++ 中,甲连赢两次,此次机率为 。在第二列中,甲赢了三次,输了一次,并且有两种可能性,所以其机率为 (q 为输的机率,故 p+q=1)。依此推导可得在第 n 列中,甲赢了 n+1 次,而输了 n-1 次,并且有 2n-1 种可能性,所以其机率为 2n-1pn+1qn-1。因此可得在整个赛局中,甲赢的机率为 ' p% a" ~: v) U 9 X/ ~, }- T/ s6 l+ A M# ?2 J/ N/ G! T' E. M4 d
' ~& M: |& Y+ W+ c6 y' s& {
4 m H, m' h* p7 H
$ M* q8 Z6 K8 x4 q1 X$ F7 x% Y: J% p
w8 e" ^8 u5 m: U7 g7 s* n
; v( L# Z* o/ W6 s
F9 {8 S% P' M/ Q3 _& W4 K
1 P0 s7 h3 g* s
/ Q+ s6 x, @" I+ D
现在让我们考虑输不起型下注法。此时只有在下列诸场合,甲才会赢。 6 N; O$ u' C, j" {: p) i" Q# k
1 E6 U% \" M! w* e
++,+-+, . z6 T4 Q$ B) _, L+ w& W9 s-+++,-++-+,(注意:甲第二次仅能下注 1 元) & o; [. L ~. f' N+ m
-+-+++,-+-++-+, % U% `6 G: s9 { e7 c # I) u8 M! w6 k& a/ n6 N$ r7 ?$ n, , $ Z ^# p: p9 k/ m/ q
。 7 V4 W9 `, d7 k$ T
$ M1 p, f9 d7 e) X
仿上之计算,可得此时甲赢的机率为 . V3 F2 P/ |! d. v4 N& W
8 K' \% K$ |9 M$ s2 s" p1 j# @
3 d) B0 Z" z1 B) h; c9 j 0 v6 c6 [/ @: q3 l7 Q 7 S; B( m* q. d 5 t, p' l3 F, k8 u a+ L' b+ z1 m' c, \& h
5 Q; f7 i7 F! r5 @/ V
4 i/ n7 ]; c* v1 B$ b6 L
最后设某甲採极端法,则甲第一次即下注2元,因此一次就决定了输赢,所以甲赢的机率为 p 。 1 Q1 b- N" w' Y/ j5 Y! Q6 W" {; ~1 a" @5 f
现在我们再回到原问题:究竟在这三种方法中,以那种方法最好?由于相对应赢的机率公式已求得,所以我们只需将 p 值代入,进而比较其大小即可,举例来说,当 时,三者之值皆为 ;而当 时,三者之值依序为 、、;至于当 时,则其值依序为 、、。这些数值告诉我们,当 时,三种下注法没影响甲赢的机会;当 时,则以保守法较好;当 时,却以极端法最佳,保守法最差。 # l: k# p) T, r9 J5 c6 H/ @0 S) M4 N; ]/ O
这些结论,是不是有些出你意料呢?其实问题还没全部解决,迄今我们仅就保守、输不起、极端三型来作比较。是否尚有其他型的下注法会使得答案更好?还有,我们仅就特例来考虑,在一般的情形下,答案又是怎样呢? # G L6 c3 i0 r
' Z! L6 i! s& h3 q2 M V/ u, H
现在,先把最一般性的结果写在下面,其中 代表当甲有 i 元时会赢的机率。 ( n6 X; i5 @. l& F$ R! H0 b! L- u. G
5 Q8 ]$ x4 o9 c' o, o' K情况一: , T8 v% ~7 u a此时不论甲如何下注, 恒等于 c/(m+c)。 ; Y% K, f- ^7 N3 Y
, D. ]' W# E6 r+ V( w1 `/ u/ j情况二: ( H0 |, c: V5 h3 w! W& l* m |0 O此时不论甲如何下注, ,而右端为保守型下注法赢的机率。因此,在此情况以保守型的下注法为最稳当。另一方面,极端下注法的赢面最低。 7 R. R- G" B; v
" t+ \0 R5 _8 \: c5 A0 m3 z
情况三: ! M6 K# e5 M$ d4 ]1 @
此时以极端法最佳,保守法最差。同样地,保守型下注法赢的机率为 。 2 `! J9 G, Z, U3 D" Q
* P1 d! u* K7 E5 S1 n' B/ d
现在我们就来研究,为什么会有这个结论!这用到了一些数学工具,不过对其中较复杂的部分,因顾及本文的可读性,笔者只很扼要的叙述一下。 ' Z0 `) ~, G9 ?0 Q+ z0 b9 a* {+ o% N( t+ S
由于在上面的结论里,保守法处于一个居中的地位,所以我们先就此法进行讨论,然后再进一步研究整个问题。 % D3 F2 o0 N/ Z# A( B5 S. w+ \+ V) S1 S1 m$ q
如同以前, 代表当甲所拥有的资本达 i 元时,他会赢的机率。由于甲及庄家的总资本额为 m+c 元,所以 i 之可能值为 i = 0, 1, …, m + c。显然地,,,而 为我们最早所想求得之机率。 # m0 n7 f U. F' B# J
$ Q' b3 {, F. j9 ~$ N' w4 }' o . s5 a& W0 I. e9 ^' q3 c6 ?情况一: : W# R# U; Q9 g- m假定某甲现有 i 元,那么有 的机会,他的资本会成为 i+1 或 i-1 元。因此 ' U; l8 @( n: O( h6 r ( k; c7 v- V R& V; Q 7 U, @& b% m* s e- \! ]+ d . ?2 s7 P; r7 _$ v : D' n J8 |: ^7 E. }, a- O + P8 O1 k" A6 Z6 @1 d0 D8 M5 X R# N2 S" o, O
这样的函数 ν,在数学上是一个线性函数,因此解的通式为 。由于,、,得 a=0、 。因此 ,亦即甲的赢面为 c/(m+c)。 6 [ ^3 R3 i4 `! c ! B7 T! k4 }* Q# `8 d5 f f情况二: / F( g* d( q6 p7 e& t令 q=1-p。此时对 ν 我们有方程式 5 T$ s+ V0 p4 g+ L* ~# o# {: X
9 l! Y& x/ p! `9 m7 [" R& r4 V. U+ N; O$ ^. \, ]2 q" O
6 y6 [! B/ c2 L4 F! L" b
; n( ?; _* W# [; O7 O! e & _# {, u, ], F9 _- F: k$ ? $ e5 T8 l% A1 y9 N2 y这样的一组方程式,在数学上称作是差分方程式。它也有一个求解的一般方法,但其道理较深。为此之故,我们特採用下面的方法。 0 U& W% z* s- C9 g: {( ^% T+ s: k% b利用p+q=1,上组方程式可改写为 f& @7 q" x3 j" n% t, p' l5 N3 W
8 F$ k- F D+ l/ i* Q/ l) t7 w
0 U9 _6 R% f$ _3 z0 W( r' ?
3 T5 \. F6 t. G0 |: Y9 r3 b7 E
8 Z) c \2 o. z0 s1 a
I2 I4 Z8 Y# P4 l6 N
2 W: T7 g- l) h% J
两边相加,并利用 、,得 ! p3 s+ j2 q; K , B/ Z+ _9 c; I+ [% i( f; T) U+ v( x
0 |2 ^, `& H1 j. G" B
% E5 v3 ~5 B3 m: {6 O* Q
, l) n1 @2 O/ J: L. z
l1 f* A3 \* Q% A' I; R
若取前 c 项相加,则得 h. w3 V3 d- q
% |2 w2 }- \# f: V' P" F/ s6 ?" \
/ T+ D3 @' @( d1 ?1 C; C
& V) Y9 b; o0 o/ G 4 b9 E1 Z; h$ a% D4 n/ ~* d' ~ " X. F1 v+ {3 J1 _1 S1 s % L2 A; o d( C1 D7 N情况三: + ]" T" d* r/ L$ g3 i
仿二之解法,可求得 : b: @ n6 v& l8 e' z0 ] : ?3 e1 j* i; D4 _9 R! @* i, F0 l1 o7 ^5 Z; F" j2 r6 W7 H! w
" c1 p7 |' R* E) R8 [+ I" g; D # _7 f* s0 e' q2 u. L: N9 Y7 H9 I! I1 i m v9 S7 P2 i
3 G( V5 L; I4 D9 {) x D# k+ O; } f6 c
保守法的 已求得,现在我们来研究为什么在情况二时,以保守下注法的 为最大;而在情况三时,反以保守下注法的 为最小;同时另一方面,在情况二时,则无论何种下注法, 皆一样。 ) @% u. D: L9 ~, I3 S* {- X* o+ l0 ~; M5 ~. D q$ [
首先我们引进一个定理。令 Sn 代表在第 n 次赛局时,甲所拥有之资本额,因此 Sn 是一个随机变数。我们并设 S0=c,即原资本。令 N 表结束赛局所需之时间,因此 SN=0 或 c+m。我们并以 E 表期望值。 - h6 h3 A$ n6 D9 Q9 X7 X" ]2 F* [5 q6 \$ f4 K
8 T7 D6 g; q4 i
定理: ! y, F; {% u* \6 {3 f7 R4 b
设 f 为一定义于 Sn 上之有界函数。若在 Sn 之条件下,f(Sn+1) 之期望值 E[f(Sn+1)] = f(Sn),则 E[f(SN)] = f(S0) = f(c)。若将「=」改为「」,则结论亦真。 & |2 `! B/ v7 B2 h$ j此定理在机率学上,即着名的选择样本定理 (optional sampling theorem),它的证明已超过本刊程度,所以略去不证,但它的直观意义却不难了解。就拿「=」的情形来说,其实是说若你的第 n+1 次赛局,平均而言并不能改变在第 n 次赛局时 f 之值,则当整个赛局结束时,f 的平均值也与原先值一样。另一方面,若在「」的情况,亦即你的第 n+1 次赛局平均而言会改进 f 先前之值,则当赛局结束时,f 的平均值也曾比原先值为佳。 O/ ^# {6 Y5 R! D% D. m. V * V% t% y* ^- |' a2 t V- y现在我们就拿这定理来证明先前我们所下之结论。 6 j+ ]$ F) a; b9 n8 ]3 V1 F' o, {' M
首先,我们考虑情况一。此时取 f(Sn)=Sn,则不论对何种下注法,因胜负机会均等, ,所以若给定 Sn,则 ESn+1 = Sn。因此由上定理知 ESN = c。但 = ,所以知不论以何种方法, 。 / H% }. u/ J' C5 o/ Z- y
& u+ G3 B. a) D0 S% \' S; `
至于在情况二或三时,我们取 。此时若给定 Sn,则 % X0 r5 r4 D- u0 p' T 3 B; Q1 ?/ y, G & f9 z# d7 p2 y7 l) @' c1 h5 N6 N8 r, P0 Q
( R& l$ `: Z N2 {; [9 l) P1 v5 I* l5 j, g
, K) x2 S& z0 N* H( q' [% y
0 ~5 |! ^0 l. I
, h, f! f( R% K% q* I其中 为所下注之金额。利用 * c9 ]; X9 l. R # M1 p- E$ _5 z$ {0 k$ s- d' s& G9 F% c/ u5 p. {+ ]( D0 ^- A- X
: Y, D- z% G R' d z, Z. K! n
( c& [5 Z) L4 {1 M. F