HOW MANY COIN TOSSES WOULD YOU NEED UNTIL YOU GET n HEADS OR m TAILS

SVANTE JANSON, LUCY MARTINEZ, AND DORON ZEILBERGER

Abstract. ABSTRACT

1. Introduction

Let (ξ_{i})_{0}^{∞} be an infinite sequence of independent fair coin tosses, with ξ_{i} = 1 representing “Heads” and ξ_{i} = −1 representing “Tails”. Let S_{n} := ∑_{i=1}^{n} ξ_{i}.

Let H_{n} and T_{n} be the number of Heads and Tails, respectively, in the first n tosses. Thus

H_{n} = \frac{n + S_{n}}{2} ,  T_{n} = \frac{n − S_{n}}{2} .  (1)

Let

X(n) := min{N : H_{N} = n or T_{N} = n} = min{N : max (H_{N}, T_{N}) = n}.

Note that

H_{n} + T_{n} = n,  (2)
H_{n} − T_{n} = S_{n}.  (3)

In particular,

X(n) = H_{X(n)} + T_{X(n)} ⩽ 2n.  (4)

Furthermore, at time X(n), one of H_{X(n)} and T_{X(n)} equals n while the other is smaller. By (3), the smaller one is n − |S_{X(n)}|, and thus (4) yields

X(n) = 2n − |S_{X(n)}|.  (5)

Hence, the random variable 2n−X(n) that we are interested in is |S_{X(n)}|. In particular, the centered variable

X(n) − 𝔼 [X(n)] = −(S_{X(n)} − 𝔼 [S_{X(n)}]).  (6)

The idea to analyse S_{X(n)} is that X(n) ≈ 2n, and thus S_{X(n)} ≈ S_{2n}, which has a nice normal limit by the central limit theorem. One elegant way to do this rigorously is by using Donsker’s theorem on convergence of the entire process (S_{i})_{i=1}^{2n}, after suitable scaling, to a Brownian motion. But I guess that you might be more comfortable with the following, I hope more pedestrian, approach.

We split the process of coin tosses into two phases, in the first we toss n_{1} := 2n − 2n^{2/3} times, and in the second we proceed to the end. (2n^{2/3} is just for convenience; any sequence that is o(n) and ω(n^{1/2}) would do. Moreover, I really mean ⌊n^{2/3}⌋, but I omit floors here for convenience.)

By the central limit theorem, since 𝔼 ξ_{i} = 0 and Var ξ_{i} = 1,

\frac{S_{n_{1}}}{\sqrt{n}} = \sqrt{\frac{n_{1}}{n}} \frac{S_{n_{1}}}{\sqrt{n_{1}}} = (\sqrt{2} + o(1))\frac{S_{n_{1}}}{\sqrt{n_{1}}} ⟶^{d} N(0, 2).  (7)

In particular, w.h.p. (with high probability, meaning with probability tending to 1 as n → ∞), |S_{n_{1}}| < 2n^{2/3}, and thus H_{n_{1}}, T_{n_{1}} < n by (1), so we have not reached the stopping time X(n) before n_{1}. We may thus condition on this event, so we will assume it in the sequel.

Let n_{2} = 2n^{2/3}, so n_{1} + n_{2} = 2n. Then, by the assumption just made and (4),

n_{1} ⩽ X(n) ⩽ 2n = n_{1} + n_{2}.  (8)

Let

S′_{k} := S_{n_{1}+k} − S_{n_{1}} = ∑_{i=1}^{k} ξ_{n_{1}+i}.  (9)

By Kolmogorov’s inequality [2, Theorem 3.1.6], for every x > 0,

ℙ( max_{1⩽k⩽n_{2}} |S′_{k}| > x) ⩽ \frac{∑_{i=1}^{n_{2}} Var(ξ_{i+n_{1}})}{x^{2}} = \frac{n_{2}}{x^{2}} = \frac{2n^{2/3}}{x^{2}} .  (10)

In particular,

ℙ( max_{1⩽k⩽n_{2}} |S′_{k}| > n^{0.4}) → 0,  (11)

and thus w.h.p., recalling (8),

|S_{X(n)} − S_{n_{1}}| = |S′_{X(n)−n_{1}}| ⩽ max_{1⩽k⩽n_{2}} |S′_{k}| ⩽ n^{0.4}.  (12)

Hence,

\frac{S_{X(n)} − S_{n_{1}}}{\sqrt{n}} ⟶^{p} 0,  (13)

which together with (7) yields

\frac{S_{X(n)}}{\sqrt{n}} ⟶^{d} N(0, 2).  (14)

If we let Z denote a standard normal variable, then (14) can also be written as

\frac{S_{X(n)}}{\sqrt{n}} ⟶^{d} \sqrt{2}Z.  (15)

We have proved the following, recalling (5) and (6), Theorem 1.1. We have, with notation defined above,

\frac{2n − X(n)}{\sqrt{n}} ⟶^{d} \sqrt{2}|Z|  (16)

and, for the centered variables,

\frac{X(n) − 𝔼 X(n)}{\sqrt{n}} ⟶^{d} −\sqrt{2}(|Z| − 𝔼 |Z|).  (17)

2. n Heads and n Tails

We can argue similarly with

Y (n) := min{N : H_{N} ⩾ n and T_{N} ⩾ n} = min{N : min (H_{N}, T_{N}) = n}.  (18)

Now, Y (n) ⩾ 2n. Furthermore, one of H_{Y (n)} and T_{Y (n)} is n, and the other is n + |S_{Y (n)}|. Consequently, by (3),

Y (n) = 2n + |S_{Y (n)}|.  (19)

Let n_{2} = 2n^{2/3} as above. It follows from the central limit theorem, similarly to (7), that

\frac{S_{2n+n_{2}}}{\sqrt{n}} ⟶^{d} N(0, 2)  (20)

and it follows easily that w.h.p. |S_{2n+n_{2}}| < n_{2} and thus, by (1), H_{2n+n_{2}}, T_{2n+n_{2}} > n. Hence, w.h.p.,

2n ⩽ Y (n) < 2n + n_{2}.  (21)

We use Kolmogorov’s inequality (10) again, but now for 1 ⩽ k ⩽ 2n_{2}, and obtain as above

\frac{S_{Y (n)} − S_{n_{1}}}{\sqrt{n}} ⟶^{p} 0,  (22)

and thus

\frac{S_{Y (n)}}{\sqrt{n}} ⟶^{d} N(0, 2),  (23)

and equivalently

\frac{S_{Y (n)}}{\sqrt{n}} ⟶^{d} \sqrt{2}Z.  (24)

Hence we obtain by (19), in analogy to Theorem 1.1:

Theorem 2.1. We have, with notation defined above,

\frac{Y (n) − 2n}{\sqrt{n}} ⟶^{d} \sqrt{2}|Z|  (25)

and, for the centered variables,

\frac{Y (n) − 𝔼 Y (n)}{\sqrt{n}} ⟶^{d} \sqrt{2}(|Z| − 𝔼 |Z|).  (26)

Remark. Thus X(n) and Y (n) have, apart from a sign, the same (centered) asymptotic distribution. Moreover, it is really “the same” Z in Theorem 1.1 and 2.1: it follows from the profs above that

\frac{X(n) + Y (n) − 4n}{\sqrt{n}} = \frac{Y (n) − 2n}{\sqrt{n}} − \frac{2n − X(n)}{\sqrt{n}} = \frac{|S_{Y (n)}| − |S_{X(n)}|}{\sqrt{n}} ⟶^{p} 0.  (27)

In fact, an extension of the arguments above shows that X(n) + Y (n) − 2n is of the order n^{1/4}. More precisely,

\frac{X(n) + Y (n) − 4n}{n^{1/4}} ⟶^{d} W  (28)

for a random variable W with a distribution that is a mixture of normal distributions. (I omit the proof.)

3. Moment convergence

The results in Theorem 1.1 and 2.1 are convergence in distribution, and as always, this does not by itself imply convergence in distribution. In this case, it is easy to give supplementary arguments showing uniform integrability of powers of the random variables in (16)–(17) and (25)–(26), and consequently these hold with convergence of all moments. Here is one such argument:

Theorem 3.1. We have convergence of all moments (both ordinary and absolute) in (16), (17), (25), and (26).

Proof. Let

ν_{H}(n) := inf{k : H_{k} ⩾ n},  ν_{T} (n) := inf{k : T_{k} ⩾ n}.  (29)

Then

X(n) = ν_{H}(n) ∧ ν_{T} (n),  (30)
Y (n) = ν_{H}(n) ∨ ν_{T} (n).  (31)

Note that ν_{H}(n) and ν_{T} (n) have the same distribution. They are dependent, so the representation (30)–(31) is of limited use, but it is nevertheless very helpful here.

Let r ⩾ 2; it is then well-known from renewal theory, see e.g. [1, Theorem 3.7.4(ii)], that the sequence of random variables

|\frac{ν_{H}(n) − 2n}{\sqrt{n}}|^{r} ,  n ⩾ 1  (32)

is uniformly integrable. (See e.g. [2, Section 5.4] for the definition.) The same is true for ν_{T} (n), since it has the same distribution as ν_{H}(n), and it follows from (30)–(31) that

|\frac{X(n) − 2n}{\sqrt{n}}|^{r}  and  |\frac{Y (n) − 2n}{\sqrt{n}}|^{r} ,  n ⩾ 1  (33)

also are uniformly integrable.

This implies that all moments converge in (16) and (25), see e.g. [2, Theorem 5.5.9]. In particular, this shows that (𝔼 [X(n)] − 2n)/\sqrt{n} converges to 𝔼 [\sqrt{2}|Z|], so 𝔼 [X(n)] = 2n + O(\sqrt{n}). Similarly, 𝔼 [Y (n)] = 2n + O(\sqrt{n}). This and (33) implies that

|\frac{X(n) − 𝔼 [X(n)]}{\sqrt{n}}|^{r}  and  |\frac{Y (n) − 𝔼 [Y (n)]}{\sqrt{n}}|^{r} ,  n ⩾ 1  (34)

also are uniformly integrable. Hence we have moment convergence also in (16) and (25). □

Acknowledgements

S. Janson was supported by the Knut and Alice Wallenberg Foundation and the Swedish Research Council. L. Martinez was supported by the NSF Graduate Research Fellowship Program under Grant No. 2233066.

References

[1] Allan Gut, Stopped Random Walks. Limit theorems and applications, 2nd ed., Springer, New York, 2009.

[2] Allan Gut, Probability: A Graduate Course, 2nd ed., Springer, New York, 2013.

(S. Janson) Department of Mathematics, Uppsala University, PO Box 480, SE-751 06 Uppsala, Sweden

   Email address: svante.janson@math.uu.se

(L. Martinez & D. Zeilberger) Department of Mathematics, Rutgers University, Piscataway, NJ 08854

   Email address: lucy.martinez@rutgers.edu
   Email address: doronzeil@gmail.com