Simulating Coin Flips vs Probability of Coin Flips

Question

Is there a standard formula for calculating the maximum, minimum and average number of times you need to flip a coin before observing a desired sequence?

Suppose you have a coin that has a 95% chance of landing on HEADS and a 5% chance of landing on TAILS. Suppose you are interested in knowing the maximum, minimum and average number of times you need to flip a coin before observing HEADS, TAILS, HEADS.

It is straightforward to find out the probability of this sequence : P(H,T,H) = 0.95 * 0.05 * 0.95 = 0.045.

But for some reason, I don't think that this means that :if you were to consider 3 flips as a "run" - in 100 "runs", on average 4.5 of these runs would result in HEADS, TAILS, HEADS

My question: Is there an exact formula that can answer these kinds of questions?

• The maximum number of "runs" before observing HEADS, TAILS, HEADS
• The minimum number of "runs" before observing HEADS, TAILS, HEADS
• The average number of "runs" before observing HEADS, TAILS, HEADS

Or can such a question only be solved using simulation methods? (e.g. program a computer to simulate many such "runs" and answer the above questions through simulation)

Thanks!

Answer 1

Your intuition about the meaning of the probabilities is wrong. $P(H,T,H)=p$ does mean that, considering a sequence of 3 flips, $H,T,H$ will appear with probability $p$.

As for the maximum number of runs before you observe your desired run: there are no such numbers. In any finite number of runs, there will be a positive probability that you did not observe your desired run. The minimum is simply 1 - you might observe it the first time.

To calculate the average number of runs before observing $H,T,H$: we can treat each run as a Bernoulli trial or coin flip by itself. We observe $H,T,H$ with probability $p$ and fail to with probability $1-p$. The number of runs is then described by the Geometric distribution. The average number of runs is then its mean: $1/p$.

Answer 2

Qustion 1: There is none since determining that maximum number of flips (let be M that number) to get ypur event is equivalent to ensure that event $E=\{HTH\}$ will occur with probability one before M flips, wich is not true.

Question 2: It is not difficult realize that the minimum number to get event $E$ is 3, for that event need at least three flips to take place.

Question 3: Yes there is, if you define $X$ as the trial where occurs $E$ for the very first time, then $X$ is a geometric random variable with parameter $p= P(E)=0.045$, so the average number of flips before observing $E$ is the expected values of $X$, wich is $E[X]= 1/p \approx 22.2$.

Answer 3

"Or can such a question only be solved using simulation methods? (e.g. program a computer to simulate many such "runs" and answer the above questions through simulation)" - Yes most definitely - this is what experimental probability is, and as your number of simulations $\to \infty$, you will arrive at your theoretical probabilities... which being...

You have already found that the specific probability of the permutation {H, T, H} $= 0.045$, with Pr(H) $= 0.95$ and Pr(T) $= 0.05$.

This means every run to occur, there is a $0.045$ chance of this, exact, permutation occurring, since your runs are independent of each other.

"exact formula" - not just a formula, there is an entire distribution set out to help you, The Binomial Distribution.

Lets consider, for a second, of your run as a whole, instead of its parts (flips). So a particular run of yours has $0.045$ chance of occuring. Since this is the event you want, this will be your probability of success (Pr(S) $= 0.045$). This also means your probability of not achieving any success or failure, Pr(F) $= 0.955$.

The binomial distribution consists of three variables, $n$, your number of trials, $p$, your probability of success (we just talked about), and $X$, number of successes out of your trials you want to achieve.

In your case $n = 100$, $p = 0.045$, $X = 3$, (lets just say we want to have exactly $3$ of your permutation {H, T, H} occurring in a 100 trials). So,

$Pr(X = 3) = {n\choose{x}}(p)^x(1-p)^{n - x} = {100\choose{3}}(0.045)^3(0.955)^{100 - 3}$

This works for any successes until, $n$, (coz you cannot have more successes than the number of trials possible).

1. "The maximum number of "runs" before observing HEADS, TAILS, HEADS."

I don't think there is a real maximum possible (there is no limit to $n$). It might just be $\infty$. However, your second question is more feasible...

2. "The minimum number of "runs" before observing HEADS, TAILS, HEADS."

If you want an absolute minimum, then its $1$ run, but your probabilities are likely not that high.

3. "The average number of "runs" before observing HEADS, TAILS, HEADS"

If you know the binomial distribution, then it might just be $np$, $100 * 0.045 = 4.5$.

Obviously this is not the case. We want the expected number of trials for at least a $X = 1$ to occur. We also want to reach a maxmimum possible probability of $X = 1$, on $n$ trials (hence the mean). This means we have to adjust the number of trials, $n$, such that $X = 1$ reaches a peak probability possible.

$Pr(X_n = 1) = {n\choose{1}}(0.045)^1(0.955)^{n - 1}$ is maximum. Let this be equal to $f(n)$. We can find the maximum by solving $\frac{d(f(n))}{dn} = 0$ for $n$, which yield, $n = 21.7184$. However, since $n \in \mathbb{N}$, $n = 22$. This means doing $22$ runs will allow you to achieve a maximum of chance of atleast $1$ {H, T, H} occurring. Thats your "average".