- #1
pagheca
- 2
- 0
Hi,
I would like to solve this version of the unfair coin problem.
The coin has a probability p for head and 1-p for tail as usual, but the winner is the person first to reach the number of wins W.
For example, one player choose head, and the other choose tail. The players flip the coin until someone reach W=5 wins.
For W=2 we have the following possible outcomes:
AA - A wins
ABA - A wins
ABB - B wins
BAA - A wins
BAB - B wins
BB - B wins
Note that the case AAA and BBB doesn't make sense because at the second flip the one player already won.
For W =3 we have:
AAA - A wins
AABA - A wins
AABBA - A wins
AABBB - B wins
ABAA - A wins
ABABA - A wins
ABABB - B wins
ABBAA - A wins
ABBAB - B wins
ABBB - B wins
BAAA - A wins
BAABA - B wins
BAABB - B wins
BABAA - A wins
BABAB - B wins
BABB - B wins
BBAAA - A wins
BBAAB - B wins
BBAB - B wins
BBB - B wins
etc...
The maximum number of flips required to win is clearly W + (W-1) = 2 * W-1.
The number of possible outcomes, if I got it right, should be 2 * [sum(i=1,W-1) {W*i)+1], that is W^2*(W-1)+2.
That is 6 for W=2, and 20 for W=3.
However, I couldn't find the probability of winning for A (and B) as a function of W and p: A(W,p).
Do you know of any algorithm for solving this problem? I'm not an expert but I guess this is a typical Markov's chain problem.
Thanks
pagheca
I would like to solve this version of the unfair coin problem.
The coin has a probability p for head and 1-p for tail as usual, but the winner is the person first to reach the number of wins W.
For example, one player choose head, and the other choose tail. The players flip the coin until someone reach W=5 wins.
For W=2 we have the following possible outcomes:
AA - A wins
ABA - A wins
ABB - B wins
BAA - A wins
BAB - B wins
BB - B wins
Note that the case AAA and BBB doesn't make sense because at the second flip the one player already won.
For W =3 we have:
AAA - A wins
AABA - A wins
AABBA - A wins
AABBB - B wins
ABAA - A wins
ABABA - A wins
ABABB - B wins
ABBAA - A wins
ABBAB - B wins
ABBB - B wins
BAAA - A wins
BAABA - B wins
BAABB - B wins
BABAA - A wins
BABAB - B wins
BABB - B wins
BBAAA - A wins
BBAAB - B wins
BBAB - B wins
BBB - B wins
etc...
The maximum number of flips required to win is clearly W + (W-1) = 2 * W-1.
The number of possible outcomes, if I got it right, should be 2 * [sum(i=1,W-1) {W*i)+1], that is W^2*(W-1)+2.
That is 6 for W=2, and 20 for W=3.
However, I couldn't find the probability of winning for A (and B) as a function of W and p: A(W,p).
Do you know of any algorithm for solving this problem? I'm not an expert but I guess this is a typical Markov's chain problem.
Thanks
pagheca
Last edited: