Probability: coin toss

[nayel]

A fair coin is tossed $n$ times. Find the probability that the sequence of tosses doesn't have a pair of consecutive heads.

[Zzzz]

A valid sequence is a sequence of tosses which doesn't contain a pair of consecutive heads.

Lets define three sequences :
i) $T_1=2,\ T_2=3,\ T_{i+2}=T_{i+1}+T_i$
i) $t_1=1,\ t_2=2,\ t_{i+2}=t_{i+1}+t_i$
i) $h_1=1,\ h_2=1,\ h_{i+2}=h_{i+1}+h_i$

Notice that if the coin is tossed for $k$ times, the number of valid sequences which end with a tail is $t_k$, the number of valid sequences which end with a head is $h_k$ and the number of total valid sequence is $T_k$. All these can be proved using strong induction. We need to use this fact -
'a valid sequence of $k$ terms can be obtained either by putting a tail after a valid sequence of $k-1$ terms that ends with head or by putting a head or a tail after a valid sequence of $k-1$ terms that ends with tail.'

Now, just need to calculate the $T_n$ and its $\frac{\sqrt 5+3}{2 \sqrt 5}\cdot \frac {1}{(\frac{-1+\sqrt 5}{2})^n} + \frac{\sqrt 5 -3}{2 \sqrt 5}\cdot \frac{1}{(\frac{-1-\sqrt 5}{2})^n}$

Please use generating function ... and mm... don't know if my calculation is correct or not

Total number of possible sequence when the coin is tossed for $n$ times = $2^n$.

So, the probability is $\frac{T_n}{2^n}$.

[rakeen]

Tough problem! After 2 days I've found this:
কয়েন্টীকে n বার টস করলে তার head ও tail 2n ভাবে বিন্নাসিত হতে পারে।
এখন আমরা, দুটি head যেন পাশাপাশি না থাকে- তার বিন্নাশ সঙ্খ্যা নিরনয় করব।

সব গুলোই যদি টেইল হয় তবে তা ১ ভাবে হতে পারে।
Sequence এ যদি ১টা হেড থাকে তবে তা C(n,1) = n ভাবে হতে পারে।
২ টা হেড থাকলে তা C(n,2) – C(n-1,1) ভাবে হতে পারে। কারন, ২টি হেড C(n,2) উপায়ে হতে পারলেও, তার মধ্যে এমন C(n-1,1) টি বিন্ন্যাস আছে যাতে ২টি হেড পাশাপাশি থাকে।
একি ভাবে ৩টা হেড থাকলে তা C(n,3) – C(n-1,2) – C(n-2,1) ভাবে হতে পারে।
.....................................................................
...................................................................
এই সব যোগ করে তা থেকে সম্ভব্যতা বের করলেই হয়ে যাবে।

Am I correct!?

[nayel]

Zubaer, you nearly had the right answer, maybe there was some mistake in your calculation. The answer is $u_n=\left(\frac{3+\sqrt 5}{2\sqrt 5}\right)\left(\frac{1+\sqrt 5}{4}\right)^n+\left(\frac{-3+\sqrt 5}{2\sqrt 5}\right)\left(\frac{1-\sqrt 5}{4}\right)^n$ where $u_n$ is the required probability. You can get this in a simpler way by noting that

i) if the $n$-th outcome is a head, the previous one must have been a tail. So this occurs with probability $\frac 12\cdot\frac 12\cdot u_{n-2}$

ii) if the $n$-th outcome is a tail, the probability is $\frac 12\cdot u_{n-1}$

and therefore $u_n=\frac 12u_{n-1}+\frac 14u_{n-2}$, with $u_0=u_1=1$. (in fact we indirectly used the formula $\mathbb P(A)=\mathbb P(A|B)\mathbb P(B)+\mathbb P(A|\bar{B})\mathbb P(\bar{B})$)

Rakeen, I think your way works too if you can prove your assertions, but it might be difficult to come up with a closed expression.

[sourav das]

I'm confused with my solution, Please someone help finding the bug if it has any:

Solution:

Denote:
$C_n$=number of such sequences for $n$ tosses
$H_n$=number of such sequences end with head for $n$ tosses
$T_n$=number of such sequences end with tail for $n$ tosses

For given condition it's easy to find recurrences of:
(i)$H_n=T_{n-1}$
(ii)$T_n=H_{n-1}+T_{n-1}=T_{n-2}+T_{n-1}$
(iii)$C_n=H_n+T_n=T_{n-1}+T_n=T_{n+1}$

But, as $T_1=1,T_2=2$
$T_n= f_{n+1}$ where $f_i$ is (i+1)th Fibonacci number.
So, $C_n=f_{n+2}=\frac{1}{\sqrt {5}} ((\frac{1+\sqrt{5}}{2})^{n+2}-(\frac{1-\sqrt{5}}{2})^{n+2})$
It implies the probability would be : $\frac{f_{n+2}}{2^n}=\frac{\frac{1}{\sqrt {5}} ((\frac{1+\sqrt{5}}{2})^{n+2}-(\frac{1-\sqrt{5}}{2})^{n+2})}{2^n}$

[Corei13]

Let $C_n$ is the number of such sequence,
Let, in a such sequence there are $k$ Heads
$a_0-1$ is the number of Tails before the first Head
$a_i$ is the number of Tails between the $(i-1)$'th and $i$'th Head, $0<i<k$
$a_k-1$ is the number of Tails after the $k$'th Head
It's easy to see that, $a_i>0$ for all $i$ and $\sum_{0\le i\le k}{a_i}=n-k+2$
We can choose $a_i$'s in $\binom{n-k+1}{k}$ ways
So, $C_n = \sum_{k\le n}\binom{n-k+1}{k} = F_{n+2}$

[sourav das]

Ok , is that mean numerical value of both solutions (One of Nayel bhaia's and One of corei13 ) will coincide?

[*Mahi*]

Yes, it is because of the difference of starting values( $C_0=F_{2},C_1=F_3$ etc.)