# Probability of flips n to 2n-1 being all tails?

Let us perform infinitely many fair coin flips and write them down. I want to find the probability of the event in which there exists $$n \ge 2$$ where the $$n$$th, $$(n+1)$$th, …, $$(2n-1)$$th flips are all tails.

I am not sure if there exists some closed form of this. I wrote code to approximate this probability (with a lower bound) with the first $$2i-1$$ flips, up to $$i=20$$:

use rayon::prelude::*;

fn flip_n(n: usize) -> (usize, usize) {
let total_count = 1 << (2 * n - 1);
let success_count = (0..total_count)
.into_par_iter()
.filter(|&sequence| {
(2..=n).any(|n| {
let end_index = 2 * n - 1;
let mask = (1 << end_index) - (1 << (n - 1));
})
})
.count();

(success_count, total_count)
}

fn main() {
for i in 2..=20 {
let (success_count, total_count) = flip_n(i);
println!(
"{} / {} ≈ {:.7}",
success_count,
total_count,
success_count as f64 / total_count as f64
);
}
}


And I got this output:

2 / 8 ≈ 0.2500000
10 / 32 ≈ 0.3125000
44 / 128 ≈ 0.3437500
182 / 512 ≈ 0.3554688
740 / 2048 ≈ 0.3613281
2982 / 8192 ≈ 0.3640137
11972 / 32768 ≈ 0.3653564
47972 / 131072 ≈ 0.3659973
192056 / 524288 ≈ 0.3663177
768554 / 2097152 ≈ 0.3664751
3074876 / 8388608 ≈ 0.3665538
12300812 / 33554432 ≈ 0.3665928
49205864 / 134217728 ≈ 0.3666123
196828666 / 536870912 ≈ 0.3666220
787325084 / 2147483648 ≈ 0.3666268
3149321132 / 8589934592 ≈ 0.3666292
12597326120 / 34359738368 ≈ 0.3666304
50389387580 / 137438953472 ≈ 0.3666310
201557716520 / 549755813888 ≈ 0.3666314


The difference between consecutive lower bounds here has a rather interesting pattern which makes me think that there might be some exact solution for infinite flips, but I have not succeeded in finding such a solution.

Any help would be appreciated!

• The title does not reflect exactly the question, in the title we have heads on positions $n$ to $2n$ including $2n$. In the text (and code if i correctly guess it) suddenly position $2n$ is excluded... Commented Feb 9 at 1:32
• Sorry, I'm used to Rust's range notation, where the start is inclusive and the end is exclusive. I can see how it would be ambiguous, so I'll fix it.
– ejx
Commented Feb 12 at 23:16

Another partial answer based on numerical evidence. It is easy to note that your numbers can be written as $$\frac{a_n}{4^n}$$ where $$a_n= 1,5,22,91,370,1491,5986,23986,96028,384277,1537438,6150406,\dots\tag{*}$$ After playing a bit with the number one finds: $$a_1=1;\quad a_n=4a_{n-1}+\xi_n,\tag1$$ where $$\xi_n=1,1,2,3,6,11,22,42,84,\dots$$ are the so-called Narayana-Zidek-Capell numbers with a rather simple recurrence relation: $$\xi_n= \begin{cases} 1,&n=1,2;\\ 2\xi_{n-1},& \text{odd }n>2;\\ 2\xi_{n-1}-\xi_{\frac n2-1},& \text{even }n>2. \end{cases}\tag{**}$$

Solving the recurrence $$(1)$$ one obtains: $$a_n=\sum_{i=1}^n 4^{n-i}\xi_i,$$ so that the probability in question is: $$p_n=\sum_{i=1}^n \frac{\xi_i}{4^i}.\tag2$$

Probably the relation $$(2)$$ can be derived directly from the definition of the Narayana-Zidek-Capell numbers but this is beyond my understanding of the subject.

UPDATE:

Instead I will prove the general recurrence relation for $$a_n$$ which reads: $$a_0=0;\quad a_1=1;\quad a_{n+1}=4a_{n}+2^{n-1}- \begin{cases} a_\frac{n-1}2,& \text{odd }n\ge1;\\ 2a_\frac{n-2}2,& \text{even }n\ge1. \end{cases}\tag3$$ Indeed ignoring the first throw we have the following subsequences each of which is sufficient to get suscess: $$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c} n &1&2&3&4&5&6&7&8&9&10&\cdots\\ 1&\color{red} T&\color{red}T\\ 2& &T&\color{red}T&\color{red}T\\ 3& & &T&T&\color{red}T&\color{red}T\\ 4& & & &T&T&T&\color{red}T& \color{red}T\\ 5& & & & &T&T&T&T&\color{red} T &\color{red} T\\ 6& & & & & &T&T&T&T& T & \cdots\\ \end{array}$$

Let us coin a sequence successful (s.s.) if it contains at least one of the above subsequences.

Our question is: what is the number $$a_n$$ of s.s. with length $$2n$$?

Incrementing $$n$$ by $$1$$ we simply increase the length of a sequence by two more throws. If the previous sequence of length $$2n$$ was already successful the resulting sequence will be successful as well independently from the result of two last throws. The number of such s.s. is $$4a_n$$. Additionally there present some sequences that were not successful in the previous $$2n$$ throws but get successful by a special result of the last two throws. It is easy to realize that this happens if and only if all following conditions are fulfilled:

• the last two throws ($$2n+1,2n+2$$) are tails

• the throws $$n+1\dots 2n$$ are tails

• the throw $$n$$ is head

• the throws $$1\dots n-1$$ do not form a successful sequence

Thus generally we need just to count unsuccessful sequences of length $$n-1$$ which are all $$2^{n-1}$$ sequences except for the successful ones. If $$n-1$$ is even the number of s.s. is simply $$a_{\frac{n-1}2}$$. If it is odd any s.s. is a s.s. of length $$n-2$$ supplemented at the end by either tail or head. Thus in this case the number of s.s. is $$2a_{\frac{n-2}2}$$. Putting all together we get the expression $$(3)$$.

The numerical result coincides with the integer sequence $$(*)$$. It is not difficult to prove that the numbers $$\xi_n=a_{n}-4a_{n-1}$$ indeed satisfy the recurrence relation $$(**)$$.

• After some of my own investigation, it seems like solving this problem would be equivalent to solving Erdős's distinct sums problem, since the solution seems to be 1 – (2 * A242729). Since it's an open problem, I will be accepting this answer.
– ejx
Commented Feb 12 at 23:35
• @ejx Indeed it seems to be the constant. Here is the link to the ANS paper: sciencedirect.com/science/article/pii/0012365X9090112U
– user
Commented Feb 13 at 11:33

Partial answer which is far too long for a comment

We need to take these events, which have nontrivial intersections, and create disjoint events. As a first step, assume the immediately previous flip is heads, which works for every one except the first event, but we can consider it separately.

In particular, this gives the events $$\{TTT, HTT\} \\ \{?HTTT\} \\ \{??HTTTT\} \\ \cdots$$

The problem is that, while this gives disjoint neighboring events, the event $$\{TTT, HTT\}$$ and the event $$\{???HTTTTT\}$$ is still not disjoint, but at least now they're independent. Therefore, we can define the probabilities recursively: $$p_1 = P(TTT,HTT) = \frac14 \\ p_2 = P(?HTTT) = \frac1{2^4} \\ p_3 = P(??HTTTT) = \frac1{2^5} \\ k \geq 4 \implies p_k = \frac1{2^{k+2}}\left(1 - \sum_{i=1}^{\lfloor k/2\rfloor-1}p_i\right)$$

From there, the probability you're looking for is the sum $$\sum_{n=1}^\infty p_n$$. I don't know a way to give the exact answer, but you can at least use it to make the algorithm more efficient.

• Thanks for the partial answer! I can now compute approximations with several thousand coin flips.
– ejx
Commented Feb 9 at 5:25