Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say we flip a biased coin such that the probability of getting the same outcome in a row (head-head or tail-tail) is $p$.

What is the probability of getting three or more tails consecutively out of $n$ flips (and alternatively out of infinite number of flips).

For example: TTT-H-TTT-HH-TTTT...

I am looking for:

  1. The fraction of tails that are in sections of size three or more.
  2. The expected size of sections with tails.
share|improve this question
1  
If the probability of getting heads is denoted $q$ we have $$p=q^2+(1-q)^2.$$ Solve as a quadratic in $q$, and then this problem is reduced to some more standard ones. –  anon Mar 4 '12 at 2:10
1  
@anon: Can you please add that as an answer? –  Aryabhata Mar 4 '12 at 2:43
    
i m not sure i get it. Here when q=1/2, p=1/2. Once we get heads, the prob that the next one is heads is p. So the prob of getting heads=tail can be 1/2 but p doesnt have to be 1/2. or maybe I didnt fully understand your answer. –  Gizem Mar 4 '12 at 2:57
    
"Once we get heads, the prob that the next one is heads is p" No, it is $q$. The probability of getting two heads in a row, where the first head is not taken for granted, plus the probability of getting two tails in a row (again, neither taken for granted), is $p$. @Aryabhata: I don't consider my comment an answer, only how to start off. –  anon Mar 4 '12 at 3:07

2 Answers 2

I’ll consider the case of an infinite string of coin tosses, as it’s easier.

Start with anon’s suggestion. Let $q$ be the probability that the coin comes up tails. Then the probability of getting two tails in a row must be $q^2$, and the probability of getting two heads in a row must be $(1-q)^2$, so you know that $p=q^2+(1-q)^2=2q^2-2q+1$, and therefore $$q=\frac14\left(2\pm\sqrt{4-8(1-p)}\right)=\frac12\left(1\pm\sqrt{2p-1}\right)\;.$$ One of the solutions is $q$; the other is $1-q$, the probability that the coin comes up heads. There’s no way to decide which is which without further information.

At any stage in the process the probability of a run of $n$ tails is $q^n(1-q)$, so the expected length of a run of tails is $\sum_{n\ge 0}nq^n(1-q)$. However, this includes runs of length $0$, which you don’t want to count, so an adjustment is needed. The probability of a run of length $0$ is $1-q\,$, so the probability of a run of positive length is $q$, and for $n>0$ the probability of a run of length $n$ given that the run has positive length is therefore $$\frac{q^n(1-q)}q=q^{n-1}(1-q)\;.$$ Thus, the expected length of a non-zero run of tails is $$\sum_{n\ge 1}nq^{n-1}(1-q)=(1-q)\sum_{n\ge 1}nq^{n-1}=\frac{1-q}{(1-q)^2}=\frac1{1-q}\;.$$

This is a fairly standard summation, but if you’re not familiar with it, just differentiate $$\sum_{n\ge 0}x^n=\frac1{1-x}\;.$$

For $k=1,\dots,n$ the probability that a given tail is the $k$-th of a run of $n$ tails is $q^{n-1}(1-q)^2$ (since we may ignore edge the effects at the beginning of the infinite string of tosses), so the probability that it belongs to a run of $n$ tails is $nq^{n-1}(1-q)^2$, and the probability that it belongs to a run of at least three tosses is $$\begin{align*}\sum_{n\ge 3}nq^{n-1}(1-q)^2&=(1-q)^2\sum_{n\ge 3}nq^{n-1}\\ &=(1-q)^2\left(\frac1{(1-q)^2}-(1+2q)\right)\\ &=q^2(3-2q)\;; \end{align*}$$

this is the fraction of tails belonging to runs of three or more.

share|improve this answer
    
Thank you very much for your answer, it was very useful! I just want to make one thing clear in my head. The relation between p and q. What I mean is that q=1/2 does not mean that p must be 1/2. We can have half tails and half heads in total. but p affects the probability that tails are together as well as heads. So when p=1 we have only 2 separate sections such that one section is composed of only tails and the other only runs of heads. I'm looking forward to your comment! –  Gizem Mar 4 '12 at 16:50
    
@Gizem: No, if $q=1/2$, then $p=q^2+(1-q)^2=1/4+1/4=1/2$ necessarily. However, it is true that when $p=1$, $q$ is either $0$ (all heads) or $1$ (all tails). –  Brian M. Scott Mar 4 '12 at 16:58
    
exactly! what i actually need is another parameter independent of q. 'homophily' parameter that does not effect the fraction of tails and heads but effects how they are clustered. The question is ''finding the expected length of run of tails and the fraction of tails belonging to runs of three or more'' as a function of that parameter (when q can still be 1/2). Does it make sense? Thanks a lot for all!! –  Gizem Mar 4 '12 at 17:31

Call $q$ the probability to get a tail, hence $q$ solves $2q(1-q)=1-p$. Let $X_n$ denote the length of the run of consecutive tails just before time $n$ and $T_k=\inf\{n\geqslant0\mid X_n=k\}$.

Your first question is asking for the probability of $[T_3\leqslant n]$. Note that $(X_n)_{n\geqslant0}$ is a Markov chain on $\{0,1,2,\ldots\}$, starting from $X_0=0$, with transition probabilities $p_{k,k+1}=q$ and $p_{k,0}=r$ with $r=1-q$.

The usual method to compute the distribution of $T_3$ applies. Call $t_k=\mathrm E_k(s^{T_3})$ for every $k\leqslant3$ and for a given $|s|\leqslant1$. Thus, one is interested in $t_0$ and one knows that $t_3=1$ and that, for every $k$ in $\{0,1,2\}$, $t_k=s(qt_{k+1}+rt_0)$.

This reads $t_0=qst_1+rst_0$, $t_1=qst_2+rst_0$ and $t_2=qs+rst_0$, hence $t_1=qs(qs+rst_0)+rst_0$ and $t_0=qs(qs(qs+rst_0)+rst_0)+rst_0$, that is, $$ t_0=\frac{q^3s^3}{1-rs-qrs^2-q^2rs^3}. $$ Introducing the three roots $s_1$, $s_2$ and $s_3$ of the polynomial $1-rs-qrs^2-q^2rs^3$, one gets for some coefficients $a_i$ that $$ t_0=q^3s^3\sum_{i=1}^3\frac{a_i}{1-s/s_i}=q^3s^3\sum_{i=1}^3a_i\sum_{n\geqslant0}s^n/s_i^n, $$ hence, by identification, $$ \mathrm P(T_3=n+3)=q^3\sum_{i=1}^3a_i/s_i^{n}, $$ and finally, $$ \mathrm P(T_3\leqslant n+3)=q^3\sum_{i=1}^3\frac{a_i}{s_i-1}(1-1/s_i^{n+1}). $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.