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

问题描述:

甲乙两人比赛投篮。约定甲先投篮,每人投篮投进一球,则继续投球,若投失一球,则换人投球。初始积分为1分,甲每投进一球,积分加1分;乙每投进1球,积分减1分。若积分达到N分(N>1),甲获胜;若积分减至0分,乙获胜。假定甲投进的概率为P1(0<P1<1),乙投进的概率为P2(0<P2<1)。那么这场投篮比赛,甲获胜的概率P为多少?

 

 

很显然的,甲获胜的概率P是和P1、P2、N相关的。

P1越大,P越大

P2越大,P越小

N越大,P越小

 

不失一般性,假设P1=0.7,P2=0.3,N=4,求甲获胜的概率P

 

解法一:大数量模拟法(10000000次)

 

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

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

一共模拟了10批次的比赛,每批次模拟10000000次比赛的过程(P1=0.7,P2=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个状态起了名字,分别是S1、S2、S3、……、S7、S8

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

 

如图,比赛初始是在S1状态,比赛结束在S7(甲获胜)或S8(乙获胜)状态,状态之间有转换箭头。

例如:当前是S3状态(积分3,甲投篮),那么下一个状态可能是S6(甲投失,换成积分3,乙投篮的状态)或者是S7(甲投进,积分4,甲获胜的状态)。再比如当前是S6状态(积分3,乙投篮),那么下一个状态可能是S5(乙投进,换成积分2,乙投篮的状态)或者是S3(乙投失,换成积分3,甲投篮的状态)

 

 

用A1、A2、A3、A4、A5、A6、A7、A8表示某次投篮后,各个状态所占的比重。那么再投篮一次后,各个状态的所占比重计算如下(等号左边是新的比重,等号右边是原来的比重):

A1=A4(1-P2

A2=A1P1+A5(1-P2

A3=A2P1+A6(1-P2

A4=A5P2+A1(1-P1

A5=A6P2+A2(1-P1

A6=A3(1-P1

A7=A3P1+A7

A8=A4P2+A8

 

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

令向量Ti=(A1、A2、A3、A4、A5、A6、A7、A8表示第i次(i=0时表示初始状态)投篮各状态所占比重的向量,则

Ti+1=Ti×A

 

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

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

 

因为

T1=T0×A

T2=T1×A=T0×A×A=T0×A2

T3=T2×A=T0×A2×A=T0×A3

……

TM=T0×AM

 

实际上,本题中的甲获胜的概率就是当M趋向于无穷时,TM的A7分量。同时,TM的A8分量表示乙获胜的概率

把上面的矩阵A分成四个小矩阵Q1、Q2、Q3、Q4,如下图所示:

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

 

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

 

 

由于TM=T0×AM,故在这儿分析AM

 

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

 

 

由于矩阵I-Q1可逆,则上述的表达式可以简化为

Q1M-1+Q1M-2+…+Q1+I=(Q1M-1+Q1M-2+…+Q1+I)(I-Q1)(I-Q1-1

=(Q1M-1+Q1M-2+…+Q1+I-Q1M-Q1M-1-…-Q1)(I-Q1-1

=(I-Q1M)(I-Q1-1

 

 

于是矩阵AM就简化成如下形式

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

 

 

对于矩阵Q1来说。由于是非负矩阵,根据G. Frobenius可知,它的谱半径ρ满足不等式,r≤ρ≤R。其中r表示G1矩阵中所有行和值(一行所有元素加起来的值)的最小值,R表示G1矩阵中所有行和值最大值。可知R=1,r=MIN(1-P1,1-P2

 

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

 

得到如下的不等式

r≤ρ≤R-(1-P2)(R-r)/R

 

由此可以得知Q1的谱半径ρ<1

而利用谱半径的性质可知,当谱半径ρ<1时,矩阵Q1的M次方趋向于0矩阵

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

 

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

 

T=T0×A*

 

 

本题中P1=0.7,P2=0.3,T0=(1,0,0,0,0,0,0,0)

 

矩阵A和矩阵A*分别为

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

 

于是

T=T0×A*=(0,0,0,0,0,0,0.828302342,0.171697658)

 

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

 

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

 

 

本方法从理论的角度给出了问题的解。本示例中,P1=0.7,P2=0.3,N=4

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

 

 

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

 

解法三:迭代法

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

依次计算向量T1、T2、……、TM等等

若TM+1-TM≈0(若每个分量小于10-9,我们就认为两个向量相等),

 

还是以上面的示例为例(P1=0.7,P2=0.3,N=4)

 

T1=(0,0.7,0,0.3,0,0,0,0)

T2=(0.21,0,0.49,0,0.21,0,0,0.09)

T3=(0,0.294,0,0.126,0,0.147,0.343,0.09)

T4=(0.0882,0,0.3087,0,0.1323,0,0.343,0.1278)

T5=(0,0.15435,0,0.06615,0,0.09261,0.55909,0.1278)

T6=(0.046305,0,0.172872,0,0.074088,0,0.55909,0.147645)

T7=(0,0.0842751,0,0.0361179,0,0.0518616,0.6801004,0.147645)

T8=(0.02528253,0,0.09529569,0,0.04084101,0,0.6801004,0.15848037)

T9=(0,0.046286478,0,0.019837062,0,0.028588707,0.746807383,0.15848037)

T10=(0.013885943,0,0.05241263,0,0.022462556,0,0.746807383,0.164431489)

T11=(0,0.025443949,0,0.01090455,0,0.015723789,0.783496224,0.164431489)

T12=(0.007633185,0,0.028817417,0,0.012350321,0,0.783496224,0.167702854)

T13=(0,0.013988454,0,0.005995052,0,0.008645225,0.803668415,0.167702854)

T14=(0.004196536,0,0.015843576,0,0.006790104,0,0.803668415,0.169501369)

……

T71=(0,4.08706E-10,0,1.7516E-10,0,2.52594E-10,0.828302342,0.171697657)

T72=(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%

 

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

上一篇:Go语言备忘录(3):net/http包的使用模式和源码解析


下一篇:WebBrowser的Cookie操作之流量刷新机