6
$\begingroup$

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));
                sequence & mask == mask
            })
        })
        .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!

$\endgroup$
2
  • 1
    $\begingroup$ 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... $\endgroup$
    – dan_fulea
    Commented Feb 9 at 1:32
  • $\begingroup$ 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. $\endgroup$
    – ejx
    Commented Feb 12 at 23:16

2 Answers 2

5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – ejx
    Commented Feb 12 at 23:35
  • $\begingroup$ @ejx Indeed it seems to be the constant. Here is the link to the ANS paper: sciencedirect.com/science/article/pii/0012365X9090112U $\endgroup$
    – user
    Commented Feb 13 at 11:33
2
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .