Probability two matching runs of coin tosses

Question

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?

Answer 1

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$).

Answer 2

An upper bound is $${\ell\choose 2} 2^{-\ell} $$ which goes to 0.

Indeed, by the union bound an upper bound is $2^{-\ell}$ times the number of positions $i<j$ such that the two matching runs start at positions $i$ and $j$. We have $1\le i<j\le (2\ell-1)-(\ell-1)=\ell$.

Now, even if the two runs overlap, the number of constrained positions is $\ell$. One way to look at this is to apply the following result of Lyndon and Schutzenberger to the case where the first run is $ab$ and the second is $b\hat a$ (so $b$ is the overlap):

Theorem. Suppose $a$, $b$ and $\hat{a}$ are strings in an arbitrary alphabet with $ab=b\hat{a}$. If $|a|\le |b|$ then there is a string $c$ and integers $k$ and $\ell$ such that $a=\hat{a}=c^k$ and $b=c^\ell$. If $|a|\ge |b|$ then there is a string $u$ with $a=bu$ and $\hat{a}=ub$.

The first few values of this bound starting at $\ell=2$, compared with felix's exact values, are $$ \frac14=\frac28\color{red}=\frac{\color{red}2}{\color{red}8} $$ $$ \frac38=\frac{12}{32} \color{red}> \frac{\color{red}8}{\color{red}3\color{red}2} $$ $$\frac38=\frac{48}{128} \color{red}> \frac{\color{red}2\color{red}8}{\color{red}1\color{red}2\color{red}8}$$ $$ \frac{5}{16} = \frac{160}{512} > \frac{\color{red}8\color{red}6}{\color{red}5\color{red}1\color{red}2} $$ (Edited to add detail and improve the bound.)