算法题——投篮比赛获胜概率问题

问题描述：

甲乙两人比赛投篮。约定甲先投篮，每人投篮投进一球，则继续投球，若投失一球，则换人投球。初始积分为1分，甲每投进一球，积分加1分；乙每投进1球，积分减1分。若积分达到N分（N＞1），甲获胜；若积分减至0分，乙获胜。假定甲投进的概率为P₁（0＜P₁＜1），乙投进的概率为P₂（0＜P₂＜1）。那么这场投篮比赛，甲获胜的概率P为多少？

很显然的，甲获胜的概率P是和P₁、P₂、N相关的。

P₁越大，P越大

P₂越大，P越小

N越大，P越小

不失一般性，假设P₁=0.7，P₂=0.3，N=4，求甲获胜的概率P

解法一：大数量模拟法（10000000次）

在前文 算法题——投篮比赛获胜的概率 中介绍的就是这种方法。

用计算机模拟10000000次比赛的过程，统计甲获胜的次数。然后甲获胜的次数比上总次数接近甲获胜的概率。

一共模拟了10批次的比赛，每批次模拟10000000次比赛的过程（P₁=0.7，P₂=0.3，N=4）

第1批次，甲获胜8282467次

第2批次，甲获胜8282839次

第3批次，甲获胜8283808次

第4批次，甲获胜8281636次

第5批次，甲获胜8282652次

第6批次，甲获胜8283432次

第7批次，甲获胜8281948次

第8批次，甲获胜8284125次

第9批次，甲获胜8284626次

第10批次，甲获胜8283720次

平均10个批次，平均甲获胜8283125次。那么甲获胜的概率大约是82.83125%

解法二：矩阵法

解法一是建立在大量的模拟上，所得的数据离理论值还是有一定的偏差的（模拟的次数越多，偏差值越小）。那么，本方法就是从理论上来计算甲获胜的概率P的。

分析该问题，可以得出整个问题存在8个状态（状态的个数和N有关，状态的个数为2N个）

分别是

积分0分，乙获胜

积分1分，乙要投篮；积分1分，甲要投篮

积分2分，乙要投篮；积分2分，甲要投篮

积分3分，乙要投篮；积分3分，甲要投篮

积分4分，甲获胜

这8个状态之间的关系可以用下图表示（为了后文表述方便，给这8个状态起了名字，分别是S₁、S₂、S₃、……、S₇、S₈）

如图，比赛初始是在S₁状态，比赛结束在S₇（甲获胜）或S₈（乙获胜）状态，状态之间有转换箭头。

例如：当前是S₃状态（积分3，甲投篮），那么下一个状态可能是S₆（甲投失，换成积分3，乙投篮的状态）或者是S₇（甲投进，积分4，甲获胜的状态）。再比如当前是S₆状态（积分3，乙投篮），那么下一个状态可能是S₅（乙投进，换成积分2，乙投篮的状态）或者是S₃（乙投失，换成积分3，甲投篮的状态）

用A₁、A₂、A₃、A₄、A₅、A₆、A₇、A₈表示某次投篮后，各个状态所占的比重。那么再投篮一次后，各个状态的所占比重计算如下（等号左边是新的比重，等号右边是原来的比重）：

A₁=A₄（1-P₂）

A₂=A₁P₁+A₅（1-P₂）

A₃=A₂P₁+A₆（1-P₂）

A₄=A₅P₂+A₁（1-P₁）

A₅=A₆P₂+A₂（1-P₁）

A₆=A₃（1-P₁）

A₇=A₃P₁+A₇

A₈=A₄P₂+A₈

可以把上面的计算式子转换为矩阵的形式

令向量T_i=（A₁、A₂、A₃、A₄、A₅、A₆、A₇、A₈）表示第i次（i=0时表示初始状态）投篮各状态所占比重的向量，则

T_i+1=T_i×A

其中，A为8*8的矩阵，如下图所示

因为

T₁=T₀×A

T₂=T₁×A=T₀×A×A=T₀×A²

T₃=T₂×A=T₀×A²×A=T₀×A³

……

T_M=T₀×A^M

实际上，本题中的甲获胜的概率就是当M趋向于无穷时，T_M的A₇分量。同时，T_M的A₈分量表示乙获胜的概率

把上面的矩阵A分成四个小矩阵Q₁、Q₂、Q₃、Q₄，如下图所示：

由于T_M=T₀×A^M，故在这儿分析A^M

由于矩阵I-Q₁可逆，则上述的表达式可以简化为

Q₁^M-1+Q₁^M-2+…+Q₁+I=（Q₁^M-1+Q₁^M-2+…+Q₁+I）（I-Q₁）（I-Q₁）^-1

=（Q₁^M-1+Q₁^M-2+…+Q₁+I-Q₁^M-Q₁^M-1-…-Q₁）（I-Q₁）^-1

=（I-Q₁^M）（I-Q₁）^-1

于是矩阵A^M就简化成如下形式

对于矩阵Q₁来说。由于是非负矩阵，根据G. Frobenius可知，它的谱半径ρ满足不等式，r≤ρ≤R。其中r表示G₁矩阵中所有行和值（一行所有元素加起来的值）的最小值，R表示G₁矩阵中所有行和值最大值。可知R=1，r=MIN（1-P₁，1-P₂）

而在李华所著的《非负矩阵谱半径的一个新估计》中，将谱半径的范围缩小

得到如下的不等式

r≤ρ≤R-（1-P₂）（R-r）/R

由此可以得知Q₁的谱半径ρ＜1

而利用谱半径的性质可知，当谱半径ρ＜1时，矩阵Q₁的M次方趋向于0矩阵

于是本问题就得出了结论，令T为T_M中M趋向无穷大时的向量，A^*为A^M中M趋向无穷大时的矩阵。可知

T=T₀×A^*

本题中P₁=0.7，P₂=0.3，T₀=（1，0，0，0，0，0，0，0）

矩阵A和矩阵A*分别为

于是

T=T₀×A*=（0，0，0，0，0，0，0.828302342，0.171697658）

甲获胜的概率是82.8302342%，乙获胜的概率是17.1697658%

和方法一的结论比较（82.83125%），还是非常接近的。也间接说明了方法一的可行性。

本方法从理论的角度给出了问题的解。本示例中，P₁=0.7，P₂=0.3，N=4

本方法的计算难点就是求（I-Q₁）^-1，这是一个消耗大量计算时间的过程。Q₁是一个2N-2*2N-2的稀疏矩阵，I-Q₁也是一个2N-2*2N-2的稀疏矩阵，求它的逆矩阵是非常耗时的

可以在本方法的理论基础上，给出简化的计算方法，也就是接下来讲的迭代法

解法三：迭代法

迭代法的理论基础在解法二上

依次计算向量T₁、T₂、……、T_M等等

若T_M+1-T_M≈0（若每个分量小于10^-9，我们就认为两个向量相等），

还是以上面的示例为例（P₁=0.7，P₂=0.3，N=4）

T₁=（0，0.7，0，0.3，0，0，0，0）

T₂=（0.21，0，0.49，0，0.21，0，0，0.09）

T₃=（0，0.294，0，0.126，0，0.147，0.343，0.09）

T₄=（0.0882，0，0.3087，0，0.1323，0，0.343，0.1278）

T₅=（0，0.15435，0，0.06615，0，0.09261，0.55909，0.1278）

T₆=（0.046305，0，0.172872，0，0.074088，0，0.55909，0.147645）

T₇=（0，0.0842751，0，0.0361179，0，0.0518616，0.6801004，0.147645）

T₈=（0.02528253，0，0.09529569，0，0.04084101，0，0.6801004，0.15848037）

T₉=（0，0.046286478，0，0.019837062，0，0.028588707，0.746807383，0.15848037）

T₁₀=（0.013885943，0，0.05241263，0，0.022462556，0，0.746807383，0.164431489）

T₁₁=（0，0.025443949，0，0.01090455，0，0.015723789，0.783496224，0.164431489）

T₁₂=（0.007633185，0，0.028817417，0，0.012350321，0，0.783496224，0.167702854）

T₁₃=（0，0.013988454，0，0.005995052，0，0.008645225，0.803668415，0.167702854）

T₁₄=（0.004196536，0，0.015843576，0，0.006790104，0，0.803668415，0.169501369）

……

T₇₁=（0，4.08706E-10，0，1.7516E-10，0，2.52594E-10，0.828302342，0.171697657）

T₇₂=（1.22612E-10，0，4.6291E-10，0，1.9839E-10，0，0.828302342，0.171697658）

T72≈T71，故可以认为T=（0，0，0，0，0，0，0.828302342，0.171697658）

也就是甲获胜的概率是82.8302342%，乙获胜的概率是17.1697658%

本方法相比解法二，计算上来得简单，仅仅通过迭代计算（加加乘乘），就计算出最后的结果。相比求矩阵的逆来说，要简单的多。