Question: At each turn, if Player A has p coins and Player B has n−p coins, then the chance of A wins to the chance of B wins is p:n−p and that whoever wins gain 1 coin from the loser. The game ends if a player gets all the n coins. If currently A has nA coins and B has n−nA coins, what is the probability that A is the final winner?
A | B |
---|---|
Wealth: p coins | Wealth: n−p coins |
Winning chance: p/n | Winning chance: 1−p/n |
Answer: Let Pp denotes the probability that A is the final winner if A has p coins. Then Pp=pnPp+1+n−pnPp−1,P0=0,Pn=1.
Then
n−pn(Pp−Pp−1)=pn(Pp+1−Pp)
and thus
Pp+1−Pp=n−pp(Pp−Pp−1)=(n−p)(n−(p−1))⋯(n−1)p(p−1)⋯1(P1−P0)=Cn−1pP1.
Sum over all Pp from p=0 to r−1, we have
Pr=r−1∑p=0(Pr+1−Pr)=r−1∑p=0Cn−1pP1.
Consider the case r=n.
1=n−1∑p=0Cn−1pP1=2n−1P1
and hence
P1=12n−1.
The final answer is therefore
PnA=∑nA−1p=0Cn−1p2n−1.
The wealthier or more powerful A is, the higher the chance A wins each battle. A reasonable model, isn't it?
No comments:
Post a Comment