0
$\begingroup$

Consider an infinite sequence of $1$'s and $0$'s such as the following:

$$1000111100011100000101010101010101.........$$

$1$ appears with a probability of $0.5$ and so does $0$

Player $1$ wins if $0011$ appears

Player $2$ wins if $1111$ appears

If one player wins, the game stops so only one player can win

do players $1$ and $2$ have the same chance of winning?

My work:

The immediate answer one would think of is that both players have the same chance of winning given that if taken independently of the infinite sequence both $0011$ and $1111$ have a probability of occurring equal to ${1}\over {16}$ However this answer must surely be wrong as a simple computer program simulating the experiment seems to indicate that: Player $1$ wins with probability $3\over 4$ Player $2$ wins with probability $1\over 4$ I am having trouble representing this situation mathematically however given that the winning subsequences can appear anywhere and at anytime. Although this explanation is very muddled, I mean to say that a simple probability tree is hard to use. Perhaps markov chains would be better$?$

$\endgroup$
  • 2
    $\begingroup$ Indeed a Markov chain on the states $\{0,1,00,11,001,111,W,L\}$ does the job. The states are the prefixes of the words of interest, plus W for a win for player 1 and L for a win for player 2. The transitions, all with probability $\frac12$, are $0\to1$, $0\to00$, $1\to0$, $1\to11$, $00\to001$, $00\to00$, $11\to111$, $11\to0$, $001\to W$, $001\to0$, $111\to L$ and $111\to0$. The probability $p$ that player 1 wins if the probability to hit $W$ before $L$, starting from the empty word... $\endgroup$ – Did Sep 22 '15 at 21:11
  • $\begingroup$ To this Markov chain we should also add the starting state $\endgroup$ – Thomas Pouget Sep 22 '15 at 21:13
  • $\begingroup$ ... Thus, if $p_x$ denotes the probability that player 1 wins starting from $x$, $p=\frac12(p_0+p_1)$, $p_0=\frac12(p_1+p_{00})$, $p_1=\frac12(p_0+p_{11})$, $p_{00}=\frac12(p_{001}+p_{00})$, $p_{11}=\frac12(p_0+p_{111})$, $p_{001}=\frac12(1+p_0)$ and $p_{111}=\frac12p_0$. Solving this affine system indeed yields $$p=\tfrac34.$$ $\endgroup$ – Did Sep 22 '15 at 21:14
  • $\begingroup$ "we should also add the starting state" No need to, see the equation $p=\frac12(p_0+p_1)$. $\endgroup$ – Did Sep 22 '15 at 21:16
  • $\begingroup$ ah yes well thanks $\endgroup$ – Thomas Pouget Sep 22 '15 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.