掷硬币问题

可以用Markov Chain hitting time求解：

甲、乙状态转移图为

初始状态$x_0=[1,0,0,0]$，$x_{t+1}=x_{t}P$,$P$是状态转移矩阵

$K_i^A $是状态i到状态A的步数的期望

对于甲：

$$P_A=\begin{bmatrix}0.5 & 0.5 & 0\\0.5 & 0 & 0.5\\0 & 0 & 1\end{bmatrix}$$

$K_1^3 = 1 + \sum\limits_{j = 1,2} {{P_{1j}}K_j^3} =1+0.5K_1^3+0.5K_2^3$

$K_2^3 = 1 + \sum\limits_{j = 1,2} {{P_{2j}}K_j^3} =1+0.5K_1^3$

有$K_1^3=1+0.5K_1^3+0.5(1+0.5K_1^3）$

最后$K_1^3=6$

对于乙：

$$P_B=\begin{bmatrix}0.5 & 0.5 & 0\\0 & 0.5 & 0.5\\0 & 0 & 1\end{bmatrix}$$

$K_1^3 = 1 + \sum\limits_{j = 1,2} {{P_{1j}}K_j^3} =1+0.5K_1^3+0.5K_2^3$

$K_2^3 = 1 + \sum\limits_{j = 1,2} {{P_{2j}}K_j^3} =1+0.5K_2^3$

有$K_2^3=2$,$K_1^3=4$

由上可知，甲平均6步能达到HH，乙平均4步能到达HT，所以乙胜利的概率高。如果还要考虑平局的情况，要计算出甲乙胜出的概率会更复杂。改了下代码，加入了最终步数的计算。

import numpy as np
n=10000
a_wins, b_wins, draw = 0, 0, 0
a_step_all,b_step_all=[],[]
for j in range(n):
    coin_flips1, coin_flips2, flag = [],[], True
    a_step=0
    while flag:
        coin_flips1.append(np.random.randint(0, 2))
        a_step+=1
        if coin_flips1[-2:] == [1, 1]:
            a_step_all.append(a_step)
            flag = False
    b_step=0
    flag=True
    while flag:
        coin_flips2.append(np.random.randint(0, 2))
        b_step+=1
        if coin_flips2[-2:] == [1, 0]:
            b_step_all.append(b_step)
            flag = False 
    if a_step<b_step: a_wins+=1 elif a_step>b_step:
        b_wins+=1
    else:
        draw+=1
print ("P(A wins)=%.3f,P(B wins)=%.3f, P(draw)=%.3f" % (a_wins/n, b_wins/n, draw/n))
print ("P(A win+draw)=%.3f, P(B win+draw)=%.3f"%((a_wins+draw)/(n+draw), (b_wins+draw)/(n+draw)))
print("Mean of steps to reach target, A=%.3f, b=%.3f"%(np.mean(a_step_all),np.mean(b_step_all)))

结果：

P(A wins)=0.329,P(B wins)=0.527, P(draw)=0.144
P(A win+draw)=0.413, P(B win+draw)=0.587
Mean of steps to reach target, A=5.941, b=3.999

根据的xwemin解答，找到一个解法。

重贴下状态转移图。

#https://en.wikipedia.org/wiki/Absorbing_Markov_chain
import numpy as np
#transitioning matrixes
#states of(A,B) [11,12,21,22,13,23,31,32,33]
P=np.matrix([
            [1,1,1,1,0,0,0,0,0],
            [0,1,0,1,1,1,0,0,0],
            [1,1,0,0,0,0,1,1,0],
            [0,1,0,0,1,0,0,1,1],
            [0,0,0,0,4,0,0,0,0],
            [0,0,0,0,0,4,0,0,0],
            [0,0,0,0,0,0,4,0,0],
            [0,0,0,0,0,0,0,4,0],
            [0,0,0,0,0,0,0,0,4]])/4.
print('Transitioning matrix:')
print(P)

Q=P[:4,:4]
R=P[:4,4:]
Ir=P[4:,4:]

print('Fundamental matrix:')
N=np.linalg.pinv(np.eye(4)-Q)
print(N)

print('Initial state')
s0=np.array([1,0,0,0])
print('Absorbing probabilities')
B=N*R
#Absorbing probabilities from state 11
B0=s0*B
print(B0)
print('P(A wins)=%.6f'%np.sum(B0[0,2:4]))
print('P(B wins)=%.6f'%np.sum(B0[0,:2]))
print('P(draws)=%.6f'%np.sum(B0[0,4]))

答案是

P(A wins)=0.322314
P(B wins)=0.537190
P(draws)=0.140496

甲胜：P甲； 乙胜：P乙； 平：P平

甲H乙H

甲胜：1/4

乙胜：1/4

平： 1/4

1/4*(甲T乙H)

甲H乙T

甲胜：1/2

乙胜：0 

平 ：0 

1/4*（甲T乙H） 

1/4*（甲T乙T）

甲T乙H

甲胜：0

乙胜：1/2

1/4（甲T乙H）

1/4（甲H乙H）

甲T乙T

甲胜：P甲

乙胜：P乙

平 ：P平

列方程求解

P甲 = 39/121

P乙 = 65/121

P平 = 17/121

To: 得得得

可能是我说的不太清楚，甲乙之间的比赛是有可能出现平局的，也就是甲扔出了HH乙扔出了HT， 你的code里是甲乙同时看一个硬币，而我的问题时甲乙两个人同时扔两个硬币。我把你的code修改了一下结果好像确实是乙胜出的概率大。具体解释我还没有想好。

import json
import numpy as np


a_wins, b_wins, draw = 0, 0, 0
for j in range(100000):
    coin_flips1, coin_flips2, flag = [],[], True
    while flag:
        coin_flips1.append(np.random.randint(0, 2))
        coin_flips2.append(np.random.randint(0, 2))
        if coin_flips1[-2:] == [1, 1] and coin_flips2[-2:] != [1, 0]:
            a_wins += 1
            flag = False
        elif coin_flips1[-2:] != [1, 1] and coin_flips2[-2:] == [1, 0]:
            b_wins += 1
            flag = False
        elif coin_flips1[-2:] == [1, 1] and coin_flips2[-2:] == [1, 0]:
            draw += 1
            flag = False
print (a_wins, b_wins, draw)

>> 32116    53763     14121

一样大，python写个simulation

a_wins, b_wins = 0, 0
for j in range(100000):
    coin_flips, flag = [], True
    while flag:
        coin_flips.append(np.random.randint(0, 2))
        if coin_flips[-2:] == [1, 1]:
            a_wins += 1
            flag = False
        elif coin_flips[-2:] == [1, 0]:
            b_wins += 1
            flag = False

最后得到的a_wins和b_wins几乎是相等的

具体分析的话，就是扔到T对于甲和乙都是等价的没用；扔到H对甲和乙一样，下一轮获胜的概率各50%。所以甲乙一样。

肯定是乙啊