0
$\begingroup$

My question is motivated by generalizing Flipping heads 10 times in a row. In that question a fair coin is used, and it is thus a probability of $(1/2)^{10}$ that heads will not appear in ten consecutive flips. Further, if we undertake fifty flips, the answer to that previous question puts the chance of some ten consecutive flips not showing heads is about $2$%.

In my generalization we throw an $n$-sided die, with equal chances of each side $1$ to $n$ coming up. The probability that no $1$ appears on $x$ consecutive rolls is then $((n-1)/n)^x$.

What is the probability that if the die is thrown $y$ times, there will be some $x$ consecutive rolls in which no $1$ appears?

The previous question is a special case of this, if one imagines a two-sided die. Actually a physical realization of a fair $n$-sided die is only possible for some special values of $n$, so perhaps a better way to think about my problem is to imagine an unfair coin being flipped, with a chance of $p$ coming up heads and $1-p$ coming up tails. It is this more generalized question that I'm interested in.

For the sake of a specific example, suppose the chance of "heads" is $p=1/6$ (as if a standard six-sided die were thrown to get $1$). Let the toss be done fifty times. What is the probability that, at any point within those fifty tosses, there will be some ten consecutive tosses that don't produce any "heads"?

$\endgroup$
  • $\begingroup$ not sure i follow...can you give an example? $\endgroup$ – Abovestand Apr 28 '17 at 22:04
  • $\begingroup$ @Abovestand - I edited my post. $\endgroup$ – neubert Apr 28 '17 at 22:30
  • 1
    $\begingroup$ ahh, ok. a better wording might be "after y rolls". iirc this type of problem doesn't have a simple answer and requires a fairly complex recursive formula. $\endgroup$ – Abovestand Apr 28 '17 at 22:54
  • $\begingroup$ I still don't follow the Question. I suspect the body of the Question here is not self-contained in presenting the problem you want help with. Linking back to the "special case of this question" is potentially helpful, but it should not take the place of a good problem formulation by adding "I'm interested in a more generalized answer to that question." $\endgroup$ – hardmath Apr 29 '17 at 1:35
  • 1
    $\begingroup$ I've edited the Question to include the points you've clarified in the Comments. Please review to make sure I've not changed your meaning unintentionally. $\endgroup$ – hardmath Apr 29 '17 at 5:39
1
$\begingroup$

There is a well-known approach to solving such problems, often introduced in an undergraduate discrete mathematics course, called probability transition matrices.

Once you have reached "ten consecutive non-heads" in your experiment, the remaining trials (if any) will not affect the result that some ten consecutive trials accomplished the goal.

We identify the possible "states" that the experiment progresses through as the trials proceed. When each trial has two possible outcomes (with independent probabilities from other trials) we refer to the experiment as a Bernoulli process. In your case we have "heads" in a trial with probability $p$ and not-heads ("tails"?) with probability $1-p$.

At the beginning we have a run of non-heads of length zero. With each trial the length of the run can either increase by one, get reset to zero. We thus define states that reflect either that a completed run of ten non-heads has been reached or that we are still trying to reach that goal (and have a current run of length less than ten).

Using your figures of $p=1/6$ and $1-p=5/6$, we will build an $11\times 11$ matrix $M$ that has an entry $M_{ij}$ that reflects the probability of going from state $i$ to state $j$.

Letting the states be ordered from zero to $9$ (for uncompleted runs) and finally the completed run state tenth, we have the matrix:

$$ M = \begin{pmatrix} 1/6 & 5/6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1/6 & 0 & 5/6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1/6 & 0 & 0 & 5/6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ & & & & \ddots & & & & & \\ 1/6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 5/6 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} $$

Recall that with probability one the experiment starts with a run of length zero. Thus the initial distribution of probabilities of states is known:

$$ s_0 = (1\; 0\; 0\; 0\; 0\; 0\; 0\; 0\; 0\; 0\; 0) $$

After (say) $r$ repetitions of the trials, the distribution of probabilities over the eleven states is $s_r = s_0 M^r$.

Finally the answer to your problem, "What is the chance of some consecutive run of ten non-heads in fifty trials?", is given by the last entry of $s_{50} = s_0 M^{50}$.

$\endgroup$
  • $\begingroup$ In my haste to post the probability transition matrix I got the entries mixed up. We have chance $1/6$ of getting heads and breaking the run (so run length goes back to zero) and $5/6$ chance of getting non-heads (thus extending the length of the current run by one, unless we already had a run of length ten). $\endgroup$ – hardmath May 1 '17 at 19:33

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.