返回题库

三人筹码博弈：终止前期望轮数

Three players

专题
Strategy / 策略
难度
L4

题目详情

Three players A,BA, B , and CC have a,ba, b , and cc coins initially. In each turn each player tosses a fair coin. If all three outcomes are heads or all three are tails, then nothing happens; otherwise the player with an outcome different from others receives a coin from each of the other two players. The game stops when one or more of the players end up with 0 coins. What is the average number of turns that will occur before the game ends?

解析

令第 nn 轮后三人筹码数为 An,Bn,CnA_n,B_n,C_n，并设

Pn=AnBnCn.P_n=A_nB_nC_n.

可以验证

Mn:=Pn+34(a+b+c−2)nM_n:=P_n+\frac{3}{4}(a+b+c-2)n

是鞅。

令停时 TT 为首次出现有人筹码为 0 的轮数，则 ATBTCT=0A_TB_TC_T=0，所以 PT=0P_T=0。由可选停止定理：

abc=M0=E[MT]=0+34(a+b+c−2)E[T].abc=M_0=\mathbb{E}[M_T]=0+\frac{3}{4}(a+b+c-2)\mathbb{E}[T].

因此

E[T]=4abc3(a+b+c−2).\boxed{\mathbb{E}[T]=\frac{4abc}{3(a+b+c-2)}}.