Intereting Posts

How to design/shape a polyhedron to be nearly spherically symmetrical, but not a platonic solid?
Prove by induction that $a-b|a^n-b^n$
Calculating equidistant points around an ellipse arc
Formal power series, the Chain Rule and the Product Rule.
Counting surjective functions
Invertibility of $BA$
Jeep problem variant: cross the desert with as much fuel as possible
Is it possible to evaluate $ \int_0^1 x^n \, dx$ by contour integration?
Projective but not free (exercise from Adkins – Weintraub)
Number of conjugacy classes of the reflection in $D_n$.
Proof of the derivative of $a^x$
Is there any motivation for Zorn's Lemma?
$75$ students in three balanced groups: Probability, cardinality.
Existence of non-trivial ultrafilter closed under countable intersection
Is there an Inverse Gamma $\Gamma^{-1} (z) $ function?

A fair coin is tossed repeatedly until 5 consecutive heads occurs.

What is the expected number of coin tosses?

- Simplify : $( \sqrt 5 + \sqrt6 + \sqrt7)(− \sqrt5 + \sqrt6 + \sqrt7)(\sqrt5 − \sqrt6 + \sqrt7)(\sqrt5 + \sqrt6 − \sqrt7) $
- Find all such functions defined on the space
- Connecting square vertexes with minimal road
- Determine all real polynomials with $P(0)=0$ and $P(x^2+1)=(P(x))^2+1$
- How prove that there are $a,b,c$ such that $a \in A, b \in B, c \in C$ and $a,b,c$ (with approriate order) is a arithmetic sequence?
- Infinite Series (Telescoping?)

- combining conditional probabilities
- $x^4 + y^4 = z^2$
- Is this condition enough to determine a random variable?
- Expected number of steps till a random walk hits a or -b.
- Mapping CDF's to each other
- Uniform distribution on the surface of unit sphere
- Probability of winning a prize in a raffle
- Probability of having at least $K$ consecutive zeros in a sequence of $0$s and $1$s
- Is statistical dependence transitive?
- Discrete probability problem: what is the probability that you will win the game?

Let $e$ be the expected number of tosses. It is clear that $e$ is finite.

Start tossing. If we get a tail immediately (probability $\frac{1}{2}$) then the expected number is $e+1$. If we get a head then a tail (probability $\frac{1}{4}$), then the expected number is $e+2$. Continue $\dots$. If we get $4$ heads then a tail, the expected number is $e+5$. Finally, if our first $5$ tosses are heads, then the expected number is $5$. Thus

$$e=\frac{1}{2}(e+1)+\frac{1}{4}(e+2)+\frac{1}{8}(e+3)+\frac{1}{16}(e+4)+\frac{1}{32}(e+5)+\frac{1}{32}(5).$$

Solve this linear equation for $e$. We get $e=62$.

Here is a generating function approach.

Consider the following toss strings, probabilities, and terms

$$

\color{#00A000}{

\begin{array}{llc}

T&\frac12&\qquad\frac12x\\

HT&\frac14&\qquad\frac14x^2\\

HHT&\frac18&\qquad\frac18x^3\\

HHHT&\frac1{16}&\qquad\frac1{16}x^4\\

HHHHT&\frac1{32}&\qquad\frac1{32}x^5\\

\color{#C00000}{HHHHH}&\color{#C00000}{\frac1{32}}&\color{#C00000}{\qquad\frac1{32}x^5}

\end{array}

}

$$

Each term has the probability as its coefficient and the length of the string as its exponent.

Possible outcomes are any combination of the green strings followed by the red string. We get the generating function of the probability of ending after $n$ tosses to be

$$

\begin{align}

f(x)&=\sum_{k=0}^\infty\left(\frac12x+\frac14x^2+\frac18x^3+\frac1{16}x^4+\frac1{32}x^5\right)^k\frac1{32}x^5\\

&=\frac{\frac1{32}x^5}{1-\left(\frac12x+\frac14x^2+\frac18x^3+\frac1{16}x^4+\frac1{32}x^5\right)}\\

&=\frac{\frac1{32}x^5}{1-\frac{\frac12x-\frac1{64}x^6}{1-\frac12x}}\\

&=\frac{\frac1{32}x^5-\frac1{64}x^6}{1-x+\frac1{64}x^6}

\end{align}

$$

The average duration is then

$$

\begin{align}

f'(1)

&=\left.\frac{\left(\frac5{32}x^4-\frac6{64}x^5\right)\left(1-x+\frac1{64}x^6\right)-\left(\frac1{32}x^5-\frac1{64}x^6\right)\left(-1+\frac6{64}x^5\right)}{\left(1-x+\frac1{64}x^6\right)^2}\right|_{\large x=1}\\

&=\frac{\frac4{64}\frac1{64}+\frac1{64}\frac{58}{64}}{\left(\frac1{64}\right)^2}\\[12pt]

&=62

\end{align}

$$

This problem is solvable with the next step conditioning method. Let $\mu_k$ denote the mean number of tosses until 5 consecutive heads occurs, given that $k$ consecutive heads just occured. Obviously $\mu_5=0$. Conditioning on the outcome of the next coin throw:

$$

\mu_k = 1 + \frac{1}{2} \mu_{k+1} + \frac{1}{2} \mu_0

$$

Solving the resulting linear system:

```
In[28]:= Solve[Table[mu[k] == 1 + 1/2 mu[k + 1] + mu[0]/2, {k, 0, 4}],
Table[mu[k], {k, 0, 4}]] /. mu[5] -> 0
Out[28]= {{mu[0] -> 62, mu[1] -> 60, mu[2] -> 56, mu[3] -> 48,
mu[4] -> 32}}
```

Hence the expected number of coin flips $\mu_0$ equals 62.

Lets calculate it for $n$ consecutive tosses the expected number of tosses needed.

Lets denote $E_n$ for $n$ consecutive heads.

Now if we get one more head after $E_{n-1}$, then we have $n$ consecutive heads

or if it is a tail then again we have to repeat the procedure.

So for the two scenarios:

- $E_{n-1}+1$
- $E_{n}{+1}$ ($1$ for a tail)

So, $E_n=\frac12(E_{n-1} +1)+\frac12(E_{n-1}+ E_n+ 1)$,

so $E_n= 2E_{n-1}+2$.

We have the general recurrence relation. Define $f(n)=E_n+2$ with $f(0)=2$. So,

\begin{align}

f(n)&=2f(n-1) \\

\implies f(n)&=2^{n+1}

\end{align}

Therefore, $E_n = 2^{n+1}-2 = 2(2^n-1)$

For $n=5$, it will give us $2(2^5-1)=62$.

The question can be generalized to what is the expected number of tosses before we get x heads.Let’s call this E(x). We can easily derive a recursive formula for E(x).

Now, there are a total of two possibilities, first is that we fail to get the xth consecutive heads in xth attempt and second, we succeed. Probability of success is 1/(2^x) and probability of failure is 1-(1/(2^x)).

Now, if we were to fail to get xth consecutive heads in xth toss (i.e. case 1), the we will have to use a total of (E(x)+1) moves, because one move has been wasted.

On the other hand if we were to succeed in getting xth consecutive head in xth toss (i.e. case 2), the total moves is E(x-1)+1 , because we now take one move more than that was required to get x-1 consecutive heads.

So,

E(x) = P(failure) * (E(x)+1) + P(success) * (E(x-1)+1)

E(x) = [1-(1/(2^x))] * (E(x)+1) + [1/(2^x)] * (E(x-1)+1)

Also E(0) = 0 , because expected number of tosses to get 0 heads is zero, duh

now,

E(1) = (1-0.5) * (E(1)+1) + (0.5) * (E(0)+1) =>

E(1) = 2

E(2) = (1-0.125) * (E(1)+1) + (0.125) * (E(1)+1) =>

E(2) = 6

Similarly,

E(3) = 14

E(4) = 30

E(5) = 62

I would simplify the problem as follows:

Let $e$ = Expected number of flips until $5$ consecutive $H$, i.e., $E[5H]$

Let $f$ = Expected number of flips until $5$ consecutive $H$ when we have seen **one** $H$, i.e., $E[5H|H]$

Let $g$ = Expected number of flips until $5$ consecutive $H$ when we have seen **two** $H$, i.e., $E[5H|2H]$

Let $h$ = Expected number of flips until $5$ consecutive $H$ when we have seen **three** $H$, i.e., $E[5H|3H]$

Let $i$ = Expected number of flips until $5$ consecutive $H$ when we have seen **four** $H$, i.e., $E[5H|4H]$

Now Start flipping coin, there is $\frac{1}{2}$ probability of getting $H$ or $T$. So if we get $H$ then expected number of flips until 5 consecutive $H$ is $(f+1)$. Alternatively if $T$, we wasted 1 flip and expected number is still $(e+1)$

$$

e=\frac12(e+1)+\frac12(f+1)\;

$$

We now need $f$ to solve above to get $e$. Now we start with 1 $H$ and seeking 4 more $H$ to get total 5 $H$. Again, there is $\frac{1}{2}$ probability of getting $H$ or $T$. So if we get $H$ (total $2H$ so far) then expected number of flips until 5 consecutive $H$ is $(g+1)$. Alternatively if $T$, we wasted this flip and expected number is back to $(e+1)$

$$

f=\frac12(g+1)+\frac12(e+1)\;

$$

Continuing this way…

$$

g=\frac12(h+1)+\frac12(e+1)\;

$$

$$

h=\frac12(i+1)+\frac12(e+1)\;

$$

Finally, Now we have 4 $H$ and seeking last $H$ to get total 5 $H$. Still, there is $\frac{1}{2}$ probability of getting $H$ or $T$. So if we get $H$ (total $5H$) then we need just $1$ flip. Alternatively if $T$ is observed, we wasted this flip and expected number is back to $(e+1)$

$$

i=\frac12(1)+\frac12(e+1)\;

$$

Solving these equations, $e=62$, $f=60$, $g=56$, $h=48$, $i=32$

This solution offers some insight into conditional expectations of number of flips needed till 5 consecutive $H$ given 1, 2, 3 and 4 consecutive $H$.

Expectation for getting n consecutive heads is : 2*(2^n-1). Thus for 5 heads it is = 62.

No one else seems to have suggested the following approach. Suppose we keep flipping a coin until we get five heads in a row. Define a “run” as either five consecutive heads or a tails flip plus the preceding streak of heads flips. (A run could be a single tails flip.) The number of coin flips is equal to the number of runs with at least four heads ($R_{4+}$), plus the number of runs with at least three heads ($R_{3+}$), and so on down to the number of runs with at least zero heads ($R_{0+}$). We can see this by expanding the terms:

$R_{0+}$ = # runs with 0 heads + # runs with 1 head + … + # runs with 5 heads

$R_{1+}$ = # runs with 1 head + # runs with 2 heads + … + # runs with 5 heads

…

$R_{4+}$ = # runs with 4 heads + # runs with 5 heads

# flips = # flips in runs with 0 heads + # flips in runs with 1 head + … + # flips in runs with 5 heads

# flips in runs with 0 heads = # runs with 0 heads

# flips in runs with 1 head = 2 x # runs with 1 head

…

# flips in runs with 4 heads = 5 x # runs with 4 heads

# flips in runs with 5 heads = 5 x # runs with 5 heads

By linearity of expectation, the expected number of coin flips is $E(R_{0+}) + E(R_{1+}) + \ldots + E(R_{4+})$. $E(R_{4+})$ is $2 E(R_{5+}) = 2$, because one half of the time we flip at least four heads in a row, we go on to flip five heads in a row, i.e. the following coin flip is heads. In other words, in expectation, it takes two runs that start with four heads to achieve one run of five heads. Likewise, $E(R_{3+}) = 2 E(R_{4+}) = 4$, $E(R_{2+}) = 2 E(R_{3+}) = 8$, $E(R_{1+}) = 2 E(R_{2+}) = 16$, and $E(R_{0+}) = 2 E(R_{1+}) = 32$. The expected number of coin flips is $32 + 16 + 8 + 4 + 2 = 62$.

More generally, given a biased coin that comes up heads $p$ portion of the time, the expected number of flips to get $n$ heads in a row is $\frac{1}{p} + \frac{1}{p^2} + \ldots + \frac{1}{p^n} = \frac{1 – p^n}{p^n(1 – p)}$.

- How to calculate Maximum or Minimum of two numbers without using if?
- How many integer solution to $y_1+y_2+y_3+y_4\leq184$with $y_1>0,\,0<y_2\leq10,\,0\leq y_3\leq17 $ and $0\leq y_4\leq 19$
- Laplacian as a Fredholm operator
- Finding the derivative of $2^{x}$ from first terms?
- Can someone explain me this summation?
- Speed of convergence of $\frac1n\int_0^1 f(x/n)dx\to0$?
- Problem of rank, trace, determinant and eigenvalue
- convergence of $ \sum_{n=1}^{\infty} (-1)^n \frac{2^n \sin ^{2n}x }{n } $
- Prove that $\lim\limits_{x\to\infty} \frac{\Gamma(x+1,x(1+\epsilon))}{x\Gamma(x)}=0$.
- A high-powered explanation for $\exp U(n)=2\iff n\mid24$?
- How to prove the optimal Towers of Hanoi strategy?
- Symmetric monoidal products that preserve limits and colimits
- Exponential fields as structures with three binary operations.
- Weights – Objects into bags puzzle
- Prove that $ f(x) = e^x + \ln x $ attains every real number as its value exactly once