6
$\begingroup$

Please consider the following problem which came up when I was thinking about modeling options.

Problem:

Suppose we have a magic two-sided coin. The probability it comes up heads in a given throw is normally $0.5$. However, if it has come up heads three times in the last three throws then the probability that it will come up heads in the next throw drops to $0.25$. In addition, if it has come up tails three times in the last three throws then the probability that it will come up heads in the next throw is $0.75$. For the first three throws of the coin the probability it will come up heads is $0.5$.

If I throw this coin $10$ times, what is the probability that I will get at least $7$ heads?

Here is my attempt to solve the problem.

Let $E(c,h,t)$ be a function which tells us the expected number of heads in $c$ throws given that we are on a run of $t$ heads and a run of $h$ heads. This means that $t$ will equal 0 or $h$ will be zero. They will both be zero at the start. For example, if the last three throws were heads, tails, tails then $t$ would be $2$ and $h$ would be $0$.

\begin{eqnarray*} E(0,t,h) &=& 0 \\ E(1,0,t) &=& 0.5 \\ E(2,0,t) &=& 1 \\ E(3,0,t) &=& 1.5 \\ E(2,1,t) &=& 1.5 \\ E(2,2,t) &=& .5(1+E(1,3,t) + 0.5(E(1,0,1)) \\ E(1,3,t) &=& 0.25 \\ E(2,2,t) &=& .5(1+0.25) + 0.5(.5) = .5(1.25) + .25 = 1.125 \\ E(4,0,t) &=& .5(1 + E(3,1,0)) + .5(E(3,0,1) \\ \end{eqnarray*} It seems to me that there should be an easier way to do this problem. I am hoping that somebody could point out a useful theorem that would make the problem much easier to solve.

Bob

$\endgroup$
  • $\begingroup$ It will inspire people to help if you show what you have tried so far. What are your ideas? $\endgroup$ – Graham Kemp Feb 19 '16 at 0:43
  • $\begingroup$ For one thing, we don't even need the case that it comes up tails three times in the last three throws, as that would make the probability = 0 $\endgroup$ – Ahmed Elyamani Feb 19 '16 at 0:50
  • $\begingroup$ Now that I have made some edits, can we take the problem off hold? $\endgroup$ – Bob Feb 19 '16 at 17:20
  • 1
    $\begingroup$ Is it possible you have studied Markov chains and probability transition matrices but overlooked the way to model this problem using that approach? $\endgroup$ – hardmath Feb 19 '16 at 18:07
  • 1
    $\begingroup$ looks like this question is related: stats.stackexchange.com/questions/74242/… -- it shows how to reduce second-order MC to usual one. $\endgroup$ – lowtech Feb 19 '16 at 19:32
2
$\begingroup$

Let's start with a formulation of probability states that is obviously adequate to the task, and then consider whittling their number down for a more efficient computation.

Let $s(L,T)$ denote a state where $L$ is a three character string recording the last three throws:

$$ L \in \{\; hhh,\; hht,\; hth,\; htt,\; thh,\; tht,\; tth,\; ttt\; \} $$

and $T$ is an integer counting the (non-negative) number of tails that have occurred.

Then we can begin with the states possible after the first three coin tosses, since these are uniformly distributed (due to "magic" initialization conditions). At time $t=3$:

$$ Pr(s(hhh,0)) = Pr(s(hht,1)) = Pr(s(hth,1)) = Pr(s(htt,2)) = \frac{1}{8} $$

$$ Pr(s(thh,1)) = Pr(s(tht,2)) = Pr(s(tth,2)) = Pr(s(ttt,3)) = \frac{1}{8} $$

Then each subsequent coin toss will again be a fifty-fifty affair except for the states $s(hhh,T)$ and $s(ttt,T)$, where "magic" causes it to be more likely ($75\%$) that the streak ends than that it continues.

All these probability transition rules could be expressed, without regard for the number of tosses possible or the number of tails allowed, by a semi-infinite Markov matrix:

$$ M = \begin{bmatrix} A & B & 0 & 0 & \ldots \\ 0 & A & B & 0 & \ldots \\ 0 & 0 & A & B & \ldots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{bmatrix} $$

where the states are "graded" as to the number $T$ of accumulated tails and:

$$ A = \begin{bmatrix} 0.25 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.5 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.5 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0.5 & 0 \\ 0.5 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0.5 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.5 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0.75 & 0 \end{bmatrix} $$

accounts for coin tosses that produce "heads", and similarly matrix $B$ would account for coin tosses producing "tails":

$$ B = \begin{bmatrix} 0 & 0.75 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.5 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0.5 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.5 \\ 0 & 0.5 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0.5 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0.5 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0.25 \end{bmatrix} $$

Let $v_3$ be the (row) vector with the probabilities of states distributed after the first three tosses (as above). Then the probability that there will be seven or more heads after ten tosses is:

$$ v_3 M^7 u^T $$

where $u$ is a (row) vector with ones in the first $32=8\cdot 4$ entries, and thus captures the total likelihood of no more than three tails at a given step.

Since we are only interested finally in the states where no more than three tails have appeared, we can truncate the vectors $v_3$ and $u$ and matrix $M$ accordingly. Thus let $v_*$ and $u_*$ be the truncations of $v_3$ and $u$ (resp.) to their first $32$ entries (corresponding to states with $T=0,1,2,3$) and similarly let $M_*$ be the leading principal $32\times 32$ submatrix of $M$:

$$ M_* = \begin{bmatrix} A & B & 0 & 0 \\ 0 & A & B & 0 \\ 0 & 0 & A & B \\ 0 & 0 & 0 & A \end{bmatrix} $$

Thus $v_3 M^7 u^T = v_* M_*^7 u_*^T$ also expresses the final probability (of seven or more heads in ten tosses).

We could make a further reduction from eight to six states in each graded block by adopting the idea expressed by the OP, of tracking only the current "run" of heads or tails, i.e. $h_k$ or $t_k$ in place of $L$, denoting $k=1,2,3$ immediately preceding heads or tails, respectively. This would bring down the dimension of the state vector from $32$ to $24$. Formally this would only affect the structure of our block submatrices $A,B$, which would become $6\times 6$ rather than size $8\times 8$.

Final Answer

I implemented the matrix multiplication in two spreadsheet environments separately, as a guard against misplaced cut-and-paste errors. The vector $v_*$ scales to integer entries when multiplied by $8$, and the matrix $M_*$ to integer entries when multiplied by $4$ (vector $u_*$ is already all ones). Thus the matrix product could be computed exactly with integer arithmetic.

Both the $8\times 8$ and $6\times 6$ block versions were implemented (on both platforms) as a guard against formula errors.

The result was probability of seven or more heads in ten tosses is $\frac{15808}{2^{17}} = \frac{13\cdot 19}{2^{11}} = 0.12060546875$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.