If you toss a coin $2\ell-1$ times you get a sequence of outcomes, say, $HTHTHTH$ for $\ell = 4$. I am trying to work out the probability that there are at least two runs (in other words contiguous subsequences of outcomes) of length $\ell$ that are identical. In this case $HTHT$ occurs twice, starting at the first and third positions.


The problem I am having is how to deal with the overlap between runs. Is there a simple (or not so simple) observation that makes this problem solvable?


I worked it out for some small examples.



```
l=2. Prob is 2/8
l=3. Prob is 8/32
l=4. Prob is 28/128
l=5. Prob is 86/512
l=6. Prob is 250/2048
l=7. Prob is 680/8192
l=8. Prob is 1792/32768
l=9. Prob is 4562/131072
l=10.Prob is 11344/524288
l=11.Prob is 27614/2097152

```

The sequence $2,8,28,86,250$ is <http://oeis.org/A118047> but after that it diverges.


If it turns out that an exact solution is not feasible, I would be very interested in any large $\ell$ approximations.




---


Is there a direct argument which tells us that the probabilities in this problem are bounded above by the case where the runs of length $\ell$ are all independent?



Probability two matching runs of coin tosses
Inspecting the bound of Bjorn Kjoss-Hanssen's answer with the numerical results in the question, it seems that the upper bound is about twice as large as the true value. I give a refined upper bound that saves this factor of $2$, and which I expect is close to the correct answer. Numerically it seems that $\binom{\ell}{2}2^{-\ell-1}$ is very close to the right answer; the upper bound I give gets the (presumably) right coefficient for the $\ell^2$ term but not the $\ell$ term. 


Suppose the string of length $2\ell -1$ is given by values $a(n)$ with $1\le n\le 2\ell -1$.  

Suppose that such a string of length $2\ell-1$ has two strings of length $r$ that match, where $r\ge \ell$ and is the maximal length of strings that match. Then there exist $1\le i< j$ such that $a(i)=a(j)$, $a(i+1)=a(j+1)$, $\ldots$, $a(i+r-1)=a(j+r-1)$ (note that this means $j\le 2\ell-r$), and also we have $a(i-1)\neq a(j-1)$ (this condition doesn't exist if $i=1$) and $a(i+r) \neq a(j+r)$ (this condition doesn't exist when $j+r=2\ell$). If $1<i$ and $j<2\ell-r$ then the probability that this happens is $2^{-r-2}$. If $i=1$ or $j=2\ell -r$ but not both then this happens with probability $2^{-r-1}$. Finally if $i=1$ and $j=2\ell-r$ we obtain a probability of $2^{-r}$. 


Thus, by the union bound over the possibilities for $i$ and $j$, for a given value of $\ell \le r \le 2\ell -2$, we have a probability of at most 
 $$ 
 2^{-r-2} \binom{2\ell-r-2}{2} + 2^{-r-1} \cdot 2 \cdot (2\ell -r-2) + 2^{-r}.
 $$ 
 Summing this over all $\ell \le r \le 2\ell-2$ gives our upper bound 
 $$ 
 \sum\_{r=\ell}^{2\ell-2} 2^{-r} \Big( \frac{1}{4} \binom{2\ell- r-2}{2} + 2\ell -r -1 \Big) = 
 2^{-\ell} \sum\_{k=0}^{\ell-2} 2^{-k} \Big(\frac 14 \binom{\ell-k-2}{2} + \ell-k-1\Big). 
 $$ 
 Asymptotically this bound is about 
 $$ 
 \frac{\ell^2}{4} \cdot 2^{-\ell};
 $$
 that is, about half the size of the previous bound. 
 When $\ell =11$ it gives an upper bound of 
 $$ 
 \frac{33280}{2097152},
 $$ 
 which is closer to the true answer of $27614/2097152$ (and the earlier bound would have a numerator of $56320$). 


