# Thread: Recursive formula for Negative Binomial(?) random variable

1. ## Recursive formula for Negative Binomial(?) random variable

I am struggling with this homework problem any help would be greatly appreciated.

Let X denote the random variable counting the number of tosses of a fair coin until (and including) the event of two consecutive heads. Let pn = P(X = n). Find p2. For n ≥ 3, find a recursive formula for pn in terms of pn-1 and pn-2 using the Low of Total Probability based on the fact that in order to obtain two consecutive heads for the first time in n tosses, either heads followed by tails occurred in the first two tosses and consecutive heads occurred for the first time in the subsequent n - 2 tosses, or tails occurred in the first toss and consecutive heads occurred in the subsequent n-1 tosses. Use this recursive formula to find the expected value of X.

2. I would condition on the flip after the first head.

E(X) = E(X|H)P(H) + E(X|T)P(T)

The expected number of flips until the first head is 1/(1/2) = 2.

If the flip after your first head is another head, you're done. If the flip after you're first head is a tails, you're not any closer to your goal than when you started.

so E(X) = (2+1)(1/2) + (2+1+E(X))(1/2)

E(X)(1-1/2) = 3

E(X) = 6

3. Let f(n) be the number of sequences of length n such that the event HH doesn't occur until the end

f(1) = 0
f(2) = 1 (HH)
f(3) = 1 (THH)
f(4) = 2 (TTHH or HTHH)
f(5) = 3 (TTTHH or HTTHH or THTHH)

f(n) = f(n-1)+f(n-2)

f(n-1) is the number of sequences (of length n) of the form $\displaystyle (T\overbrace{... \ HH}^\text{(n-1) terms})$ such that the event HH doesn't occur until the end

f(n-2) is the number of sequences (of length n) of the form $\displaystyle (HT\overbrace{... \ HH}^\text{(n-2) terms})$ such that the event HH doesn't occur until the end

f(n) is simply the Fibonacci sequence shifted backwards one term

and since 2^n is the total number of possible sequences of length n

so $\displaystyle P(X=n) = \frac{F(n-1)}{2^{n}}$ where F(n) is the nth Fibonacci number

now $\displaystyle E(X) = 2*\frac{1}{4} + 3 *\frac{1}{8} + 4*\frac{2}{16} + 5*\frac{3}{32} + ...$ is hopefully equal to 6 (the answer I got above) but I don't see how to sum this series

4. Originally Posted by Random Variable
f(n) is simply the Fibonacci sequence shifted backwards one term
and since 2^n is the total number of possible sequences of length n
so $\displaystyle P(X=n) = \frac{F(n-1)}{2^{n}}$ where F(n) is the nth Fibonacci number
now $\displaystyle E(X) = 2*\frac{1}{4} + 3 *\frac{1}{8} + 4*\frac{2}{16} + 5*\frac{3}{32} + ...$ is hopefully equal to 6 (the answer I got above) but I don't see how to sum this series
It does.
$\displaystyle F_n = \frac{1} {{\sqrt 5 }}\frac{{\left( {1 + \sqrt 5 } \right)^n - \left( {1 - \sqrt 5 } \right)^n }} {{2^n }}\, \Rightarrow \,\sum\limits_{n = 2} {\frac{{F_{n - 1} }} {{2^n }}n} =$$\displaystyle \frac{1} {{\sqrt 5 }}\sum\limits_{ = 2}^\infty {\frac{{\left( {1 + \sqrt 5 } \right)^{n - 1} - \left( {1 - \sqrt 5 } \right)^{n - 1} }} {{2^{2n - 1} }}n} = 6$

5. Using the closed form solution for F(n-1) doesn't seem to make the sum of the series any easier to calculate (at least not by hand). Did you use a program like Maple or Mathetica to compute the sum?

6. Hello,
Originally Posted by Random Variable
Using the closed form solution for F(n-1) doesn't seem to make the sum of the series any easier to calculate (at least not by hand). Did you use a program like Maple or Mathetica to compute the sum?
\displaystyle \begin{aligned}\sqrt{5}\mathbb{E}(X)&=\sum_{n=2}^\ infty \frac{(1+\sqrt{5})^{n-1}-(1-\sqrt{5})^{n-1}}{2^{2n-1}} \cdot n \\ &=2\left(\sum_{n=2}^\infty \frac{n(1+\sqrt{5})^{n-1}}{4^{n-1}}-\sum_{n=2}^\infty \frac{n(1-\sqrt{5})^{n-1}}{4^{n-1}}\right)\end{aligned}
(because the two sums converge)

Consider $\displaystyle \frac{1}{1-x}=\sum_{n=0}^\infty x^n$
Differentiate :
$\displaystyle \frac{1}{(1-x)^2}=\sum_{n=1}^\infty nx^{n-1}$

So $\displaystyle \sum_{n=2}^\infty nx^{n-1}=1+\frac{1}{(1-x)^2}$

Let $\displaystyle x=\frac{1\pm\sqrt{5}}{4}$ :

\displaystyle \begin{aligned}\frac{\sqrt{5}}{2}\cdot\mathbb{E}(X )&=\frac{1}{\left(1-\frac{1+\sqrt{5}}{4}\right)^2}-\frac{1}{\left(1-\frac{1-\sqrt{5}}{4}\right)^2} \\ &=16 \left(\frac{1}{(3-\sqrt{5})^2}-\frac{1}{(3+\sqrt{5})^2}\right) \\ &=16\left(\frac{1}{14-6\sqrt{5}}-\frac{1}{14+6\sqrt{5}}\right)\\ &=16\cdot\frac{12\sqrt{5}}{14^2-36\cdot 5}=\boxed{12\sqrt{5}} \end{aligned}

And hence $\displaystyle \boxed{\mathbb{E}(X)=6}$

I guess it's also possible to get this result by using the binomial expansions of $\displaystyle (1\pm\sqrt{5})^{n-1}$.
Should even be better, but I didn't try.