Probability of a random binary string containing a long run of 1s?
Solution 1:
Slight trivial change in notation: Let $P_n$ be the probability that every run of consecutive 1s in our string does not exceed $n$ plus the previous acumulated runs.
Then, the following linear recursion (equivalent to that of your second approach) holds:
$$P_n = \sum_{k=1}^n P_{n+k} \; 2^{-k} \hspace{12mm} n=1, 2 \ldots \tag{1} $$
(this is obtained by summing over all the possible lengths of the first run; because, after the first run of length $k$, we have the equivant problem with $n$ replaced by $k+n$)
This recursion is rather tricky to solve, because our "initial value" would be $P_{\infty}=1$, and the recursion is not time-reversible. Here's my approach (perhaps there are more elegant procedures, I'm not really familiar with this).
I try a solution of the form:
$$P_n = 1 + a_1 2^{-n} + a_2 2^{-2n} + a_3 2^{-3n} + \cdots$$
Actually, we'll only keep the terms with exponents of the form $-(2^p-1)n$. That is, we set $a_i=0$ unless $i = 2^p-1$ for some integer $p$. Calling $Q(r, n) = 2^{-r \, n}$, we have:
$$P_n = Q(0,n) + a_1 \, Q(1 , n) + a_3 \, Q(3,n) + a_7 \, Q(7,n) + a_{15} \, Q(15,n) +\cdots$$
Now, it's straighfroward to check (geometric sum) that:
$$\sum_{k=1}^n Q(r,n+k) \; 2^{-k} = \frac{1}{2^{r+1}-1} \bigl( Q(r,n) - Q(2r+1,n) \bigr) $$
Hence, the recursion (1) induces the transformations $Q_0 \to Q_0 -Q_1$, $Q_1 \to \frac{1}{3}(Q_1 -Q_3)$, $Q_3 \to \frac{1}{7}(Q_3 -Q_7)$, etc, and thus the coefficients can be obtained:
$$\begin{align} a_1 &= \frac{a_1}{3} - 1 \Rightarrow a_1 = -\frac{3}{2} \\ a_3 &= \frac{a_3}{7} - \frac{a_1}{3} \Rightarrow a_3 = \frac{1}{3} \frac{7}{6} \frac{3}{2}=\frac{7}{6 \times 2}\\ a_7 &= \frac{a_7}{15} - \frac{a_3}{7} \Rightarrow a_7 = - \frac{1}{7} \frac{15}{14} \frac{1}{3} \frac{7}{6} \frac{3}{2} =-\frac{15}{14 \times 6 \times 2} \\ a_{15} &= \cdots = \frac{31}{30 \times 14 \times 6 \times 2}\\ a_{2^p-1} &= \cdots = (-1)^p \frac{2^{p-1}-1}{(2^{p-1}-2) \times (2^{p-2}-2) \cdots \times 14 \times 6 \times 2}\\ \end{align} $$
Or, more compact (perhaps not more illuminating) :
$$ a_{2^p-1} = \frac{2-2^{-p}}{(2;2)_p}$$
where $(a;q)_n$ is the q-Pochhammer_symbol.
Some numerical values:
$ a_1=-1.50$, $ a_3\approx0.58333$, $a_7\approx-0.08929 $, $a_{15}\approx 0.00615$, $a_{31}\approx-0.0002$
So, finally
$$ P_n = 1 - \frac{3}{2} 2^{-n} + \frac{7}{12} 2^{-3 n } + \cdots =\\ = 1 +\sum_{p=1}^\infty \frac{2-2^{-p}}{(2;2)_p}2^{-(2^p-1)n}$$
This converges quite quickly, specially for big $n$.
To get, according to the original question, the probability that some run is greater or equal than $m$, we'd evaluate
$$1 - P_{m-1} = 3 \, 2^{-m} - \frac{14}{3} 2^{-3 m} + \cdots $$
which in the first approximation coincides with the OP's estimate (using the expectation); it is quite a good approximation for, say, $n>4$.
n 1 2 3 4 5 6 7
p(n) exact 0.32222 0.63411 0.81364 0.90639 0.95314 0.97656 0.98828
p(n) approx 0.25000 0.62500 0.81250 0.90625 0.95312 0.97656 0.98828
Added Rigurous bounds for $P(n)$ can be obtained by noting that, with my definition, it's equivalent to the probability that a sequence of iid geometric variables $x_i = 1, 2 \cdots$ attaining values in $x_1 \le n$,$x_2 \le n + x_1 $,$x_3 \le n + x_1 + x_2$ ...
So
$$P(n) = \sum_{k_1}^{n} 2^{-k_1} \sum_{k_2}^{n+k_1} 2^{-k_2} \sum_{k_3}^{n+k_1+k_2} 2^{-k_3} \cdots$$
In particular, a lower bound for the $m$-th terms in this infinite nested product is obtained by setting the outer values in $k_1=1$, $k_2=1$..., so
$$P(n) \le \sum_{k_1}^{n} 2^{-k_1} \sum_{k_2}^{n+1} 2^{-k_2} \sum_{k_3}^{n+2} 2^{-k_3} \cdots = (1 - 2^{-n})(1 - 2^{-n-1})(1 - 2^{-n-2}) = \\ = \prod_{i=0}^\infty (1 - 2^{-n} 2^{-i})= S(2^{-n},2^{-1}) $$ where $S(a,q)=\prod_{i=0}^\infty (1 - a q^{i})$ is the q-Pochamer symbol or (q-series) QPochhammer[a,q]
We can check that this tends to 1 when $a\to 0$ by using the bound $0<-\log(1-x)<2x$ for $0<x \le 1/2$, so $\log( S(2^{-n},2^{-1})$ is bounded between $0$ and $-2^{-n+1}$. Hence $\lim_{n\to\infty} P(n)=1$.
Added 2: Regarding uniqueness: We must prove that the recursion (1), with the boundary condition $P_{\infty}=1$ does not admit more than one solution (with $0 \le P_n \le 1)$. This is equivalent to prove that the recursion does not have a solution with $P_{\infty}=0$ except for the trivial one: $P_n=0$.
Now, suppose $P_{n_1}>0$. Then, the equation (1) implies that there exists at least one $n_2$ in $n_1 +1 \cdots 2 n_1$ with $P_{n_2} > P_{n_1}$. Applying the same to $n_2$, this implies that we can find an increasing subsequence of $P(n)$; hence its limit cannot be zero.
Solution 2:
This answer has a "motivational" stage, and afterwards a "calculations" stage. Even if the deduction of the formulas is not as pleasant as the formulas provided by the OP and leonbloy, I think that my answer qualifies as "nice", at least because I obtain a decreasing recurrence and because of its "constructive" flavor. Please prepare yourself to see a lot of summation symbols, but do not get impatient, just don't forget the moral of the reasoning, and feel free to skip the easy steps.
STAGE 1: MOTIVATION
I always try to solve problems concerning random binary strings in a constructive manner. Then we can ask: how to "construct" an "admissible" string?
This is how I proceed: let us say that you want that the desired condition be fulfilled at the $r$-th run of $1$s (shortly, $1$-run) and not before. Then you construct the previous $1$-runs with prescribed lengths $k_1,k_2,\dots,k_{r-1}\geq1$. Now we must interleave $0$-runs between our $1$-runs. The first $0$-run, which we will be put before the first $1$-run, can have any length $i_1$ including zero (because your sequence may or not start with $1$). On the other hand, the other dividing $0$-runs must have positive length (because they must separate our $1$-runs).
Therefore the lengths $i_1,\dots,i_r$ of the $0$-runs satisfy $i_1\geq0$ and $i_2,\dots,i_r\geq1$. Finally, the $r$-th $1$-run must have length greater or equal than $n+k_1+\cdots+k_{r-1}$. Actually, we can suppose that this length is exactly equal to $n+k_1+\cdots+k_{r-1}$, because in this case it does not matter how the rest of the sequence is.
Of course, the desired condition is not fulfilled before the $r$-th step if and only if $k_j\leq s_{j-1}$ for $j=1,\dots,r-1$, being $s_j=n-1+k_1+\cdots+k_j$ ($s_0=n-1$).
The set of sequences constructed in the way described above, with the values $k_i$ and $i_j\ $ fixed has probability
$$\underbrace{2^{-(i_1+\cdots+i_r)}}_{0\text{-}\style{font-family:inherit;}{\text{runs}}}\ \underbrace{2^{-(k_1+\cdots+k_{r-1})}}_{\style{font-family:inherit;}{\text{faulty}}\ 1\text{-}\style{font-family:inherit;}{\text{runs}}}\ \underbrace{2^{-(n+k_1+\cdots+k_{r-1})}}_{\style{font-family:inherit;}{\text{successful}}\ 1\text{-}\style{font-family:inherit;}{\text{run}}}\,.$$
It remains to sum this value over all admissible values of $r,i_1,\dots,i_r,k_1,\dots,k_{r-1}$. In other words, the desired probability is equal to
$$\sum_{r=1}^\infty\Biggl[\,\sum_{i_1=0}^\infty\sum_{i_2=1}^\infty\cdots\sum_{i_r=1}^\infty\Biggr]\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}2^{-(i_1+\cdots+i_r)}\,2^{- (k_1+\cdots+k_{r-1})}\,2^{-(n+k_1+\cdots+k_{r-1})}\,.$$
The part of the sum involving the $i_j$ can be easily solved: recall that $\sum_{i=0}^\infty 2^{-i}=2$ and $ \sum_{i=1}^\infty2^{-i}=1$, so our sum simplifies to
$$2^{1-n}\sum_{r=1}^\infty\ \sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}4^{-(k_1+\cdots+k_{r-1})}\,.$$
Now we concentrate on the inner sum, that is, with $r$ fixed. We have
$$\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}4^{-(k_1+\cdots+k_{r-1})}=\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-(k_1+\cdots+k_{r-2})}\sum_{k_{r-1}=1}^{s_{r-2}}4^{-k_{r-1}}\,.$$
Since $\sum_{k=1}^s4^{-k}=\frac13(1-4^{-s})$, our sum becomes
$$\frac13\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-(k_1+\cdots+k_{r-2})}(1-4^{-s_{r-2}})$$
$$=\frac13\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-(k_1+\cdots+k_{r-2})}-\frac13\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-(k_1+\cdots+k_{r-2})}4^{-s_{r-2}}$$
$$=\frac13\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-(k_1+\cdots+k_{r-2})}-\frac13\,4^{-(n-1)}\sum_{k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}4^{-2(k_1+\cdots+k_{r-2})}$$
Now I will try to convince you that this is indeed a decreasing recurrence, unlike OP and leonbloy's approach (which of course are very clever and illuminating). This is a good time to make a generalization of the problem and introduce some convenient notation:
STAGE 2: CALCULATIONS
Let $p\in(0,1)$ and let $q=1-p$. Now we suppose that the probability of $1$ in each place of a binary string is equal to $p$ (so the probability of $0$ is $q$). In the case of interest we have $p=q=1/2$, but the general case is not harder than this particular case.
Reasoning as in the previous stage, the probability of the set of desired sequences with the numbers $r,i_1,\dots,i_r,k_1,\dots,k_{r-1}$ fixed is equal to
$$\underbrace{q^{i_1+\cdots+i_r}}_{0\text{-}\style{font-family:inherit;}{\text{runs}}}\ \underbrace{p^{k_1+\cdots+k_{r-1}}}_{\style{font-family:inherit;}{\text{faulty}}\ 1\text{-}\style{font-family:inherit;}{\text{runs}}}\ \underbrace{p^{n+k_1+\cdots+k_{r-1}}}_{\style{font-family:inherit;}{\text{successful}}\ 1\text{-}\style{font-family:inherit;}{\text{run}}}\,,$$
It is important to distinguish the case $r=1$ of the probability above: in this case there is no choice of numbers $k_1,\dots,k_{r-1}$, we only choose $i_1\geq0$, so in this case the probability is equal to $p^nq^{i_1}$. Thus, the total probability is equal to
$$\sum_{i_1=0}^\infty p^nq^{i_1}+\sum_{r=2}^\infty\Biggl[\,\sum_{i_1=0}^\infty\sum_{i_2=1}^\infty\cdots\sum_{i_r=1}^\infty\Biggr]\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}q^{i_1+\cdots+i_r}\,p^{k_1+\cdots+k_{r-1}}\,p^{n+k_1+\cdots+k_{r-1}}\,.$$
$$=\frac{p^n}{1-q}+\frac{p^n}{1-q}\sum_{r=2}^\infty\biggl(\frac{q}{1-q}\biggr)^{r-1}\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}\bigl(p^2\bigr)^{k_1+\cdots+k_{r-1}}\,.$$
Define
$$S(\alpha,1)=1;\ S(\alpha,r)=\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-1}=1}^{s_{r-2}}\alpha^{k_1+\cdots+k_{r-1}}\,,\ \style{font-family:inherit;}{\text{for}}\ r\geq2\,.$$
Then our probability can be written as
$$\frac{p^n}{1-q}\sum_{r=1}^\infty\biggl(\frac{q}{1-q}\biggr)^{r-1}S(p^2,r)\,.$$
We have $S(\alpha,1)=1$, and for $r\geq2$:
$$S(\alpha,r)=\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}\alpha^{k_1+\cdots+k_{r-2}}\sum_{k_{r-1}=1}^{s_{r-2}}\alpha^{k_{r-1}}$$
$$=\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}\alpha^{k_1+\cdots+k_{r-2}}\biggl[\frac{\alpha}{1-\alpha}\,(1-\alpha^{s_{r-2}})\biggr]$$
$$=\frac{\alpha}{1-\alpha}\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}\alpha^{k_1+\cdots+k_{r-2}}-\frac{\alpha}{1-\alpha}\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}\alpha^{k_1+\cdots+k_{r-2}+s_{r-2}}$$
$$=\frac{\alpha}{1-\alpha}S(\alpha,r-1)-\frac{\alpha}{1-\alpha}\,\alpha^{n-1}\sum_ {k_1=1}^{s_0}\sum_{k_2=1}^{s_1}\sum_{k_3=1}^{s_2}\cdots\sum_{k_{r-2}=1}^{s_{r-3}}\alpha^{2(k_1+\cdots+k_{r-2})}$$
$$=\frac{\alpha}{1-\alpha}\,S(\alpha,r-1)-\frac{\alpha^n}{1-\alpha}\,S(\alpha^2,r-1)\,.$$
Changing $\alpha$ by $\alpha^j$, we obtain, for $r\geq2$:
$$S(\alpha^j,r)=\frac{\alpha^j}{1-\alpha^j}\,S(\alpha^j,r-1)-\frac{\alpha^{jn}}{1-\alpha^j}\,S(\alpha^{2j},r-1)\,.$$
Why the hell I did this? because defining
$$b_j=\frac{\alpha^j}{1-\alpha^j},\ c_j=-\,\frac{\alpha^{jn}}{1-\alpha^j}\quad \style{font-family:inherit;}{\text{and}}\quad T(j,r)=S(\alpha^j,r)$$
the recurrence becomes
$$T(j,1)=1;\quad T(j,r)=b_j\,T(j,r-1)+c_j\,T(2j,r-1),\ \style{font-family:inherit;}{\text{for}}\ r\geq2\,.$$
OK, I agree that this is not a genuine decreasing recurrence, as index $j$ is increasing; fortunately, the index $r$ decreases. In general, these recurrences can be explicitly solved, either by bare hands or using computer algebra systems. Later I will try to solve it step by step, for the benefit of those who believed (or disbelieved?) me and endured up this point.