Yamagishi Complexity Torus LabYamagishi Lab

[Paper 636] The Longest Run of Heads Grows by One Each Time the Tosses Double, and Its Spread Does Not Shrink

Abstract

A fair coin is tossed $n$ times and the longest stretch of consecutive heads (the longest run) is counted. Its distribution is found exactly by matrix powers and checked by simulation. No new theorem or law is claimed.

First, in $200$ tosses a run of $5$ or more almost always appears——the longest run is $5$ or more with probability $0.965903$, $6$ or more with $0.800932$, $7$ or more with $0.543708$, and even $10$ or more with $0.089919$. The mean is $6.984206$, and $200000$ simulated sequences gave $6.983795$ (Section 2).

Second, the mean grows like $\log_2 n$——the growth for each tenfold increase of $n$ is $3.308277$, $3.320555$, $3.321789$ and $3.321917$, approaching $\log_2 10=3.321928$: one more for each doubling. At $n=10^6$ the mean is $19.264317$, the mean minus $\log_2 n$ is $-0.667252$, and the difference from the known asymptotic value $-0.667254$ is $0.000002$ (Section 3).

Third, and this is the core. The spread of the longest run does not shrink however many times the coin is tossed——the standard deviation is $1.793249$ at $n=100$, $1.871193$ at $10^4$ and $\mathbf{1.872689}$ at $10^6$, approaching the asymptotic value $1.872711$ and stopping there. This contrasts with the standard deviation of the share of heads, $0.5/\sqrt{n}$, which shrinks from $0.05$ to $0.0005$ (Section 4).

Fourth, the separator is whether the sum or the maximum is looked at——the number of heads (a sum) settles in share as tosses increase, but the longest run (a maximum) keeps growing like $\log_2 n$ and keeps its spread. From the same sequence of the same coin, a quantity that settles and one that does not can be drawn (Section 5).

Keywords: longest run, coin tossing, extreme value statistics, variance, logarithmic growth.

Scope (what is not claimed)

No new theorem or law is claimed——that the longest run grows like $\log_2 n$ (Erdős and Rényi, $1970$), the asymptotic values of its mean and spread, and that a run of $5$ or more almost always appears in $200$ tosses (Schilling’s exposition of $1990$ and others) are known. The psychology of people writing “random” sequences with runs too short is not treated——no human-written sequences were counted. Relation to earlier papers: Paper 629 counted that in the uncapped St. Petersburg game the average prize over plays keeps growing like $\log_2 n$ and does not settle——here the same $\log_2 n$ appears as the growth of the longest run, and its spread does not shrink either. What is added is finding the distribution exactly by matrix powers, checked against all $1024$ sequences for $n=10$ and against simulation for $n=200$, setting out the mean and spread from $n=10$ to $10^6$, and placing the separator on “sum or maximum”.

1. Notation and the Question

Setting: a fair coin is tossed $n$ times, and $R_n$ is the longest stretch of consecutive heads. With states $0,1,\ldots,r-1$ for “how many heads in a row so far”, a tail returning to $0$, a head moving up one, and reaching $r$ removing the path, multiplying the matrix $n$ times gives the surviving probability $P(R_n<r)$. The mean was found from $\sum_{r\ge1}P(R_n\ge r)$ and the mean square from $\sum_{r\ge1}(2r-1)P(R_n\ge r)$.

Question: how does the longest run grow with the number of tosses, and how much does it spread?

2. Tossing 200 Times

Computation 2.1: the distribution for $n=200$ was found exactly.

longest run$5$ or more$6$ or more$7$ or more$10$ or more
probability$0.965903$$0.800932$$0.543708$$0.089919$

The mean is $6.984206$. $200000$ simulated sequences of $200$ tosses gave a mean of $6.983795$ (difference $-0.000411$, standard error of the mean $0.004087$) and a share of $6$ or more of $0.799390$. For $n=10$ the mean agreed within $10^{-12}$ with the value from counting all $1024$ sequences.

Observation 2.2 five heads in a row within $200$ tosses is nothing unusual. The chance that the longest run stays below $5$ is only $1-0.965903$——long runs catch the eye, but with many tosses they are the normal outcome.

3. How the Mean Grows

Computation 3.1: the mean and standard deviation were found for $n$ from $10$ to $10^6$.

$n$meanstandard deviationmean $-\log_2 n$
$10$$2.798828$$1.392137$$-0.523100$
$100$$5.991780$$1.793249$$-0.652076$
$1000$$9.300057$$1.861224$$-0.665727$
$10^4$$12.620612$$1.871193$$-0.667101$
$10^5$$15.942400$$1.872527$$-0.667240$
$10^6$$19.264317$$\mathbf{1.872689}$$-0.667252$

The growth of the mean for each tenfold increase of $n$ was $3.308277$, $3.320555$, $3.321789$ and $3.321917$, approaching $\log_2 10=3.321928$. At $n=10^6$ the mean minus $\log_2 n$ differed by $0.000002$ from its known asymptotic value $\gamma/\ln2-3/2=-0.667254$.

Observation 3.2 the longest run grows by one each time the tosses double. The expected number of places where a run of length $r$ or more starts is about $n/2^{r+1}$, and the $r$ at which this is about $1$ lies near $\log_2 n$——doubling the tosses lets one meet, once, a run one longer.

4. The Spread

Computation 4.1: the standard deviation went $1.871193$, $1.872527$ and $1.872689$ from $n=10^4$ to $10^6$, differing at $n=10^6$ by $0.000022$ from the known asymptotic value $\sqrt{\pi^2/(6\ln^2 2)+1/12}=1.872711$. For comparison, the standard deviation of the share of heads, $0.5/\sqrt{n}$, is $0.050000$ at $n=100$, $0.005000$ at $10^4$ and $0.000500$ at $10^6$.

Observation 4.2 this is the core: the spread of the longest run does not shrink as tosses increase. The share of heads has its spread cut to a tenth for each hundredfold increase of tosses and settles at $1/2$. The longest run keeps a spread of about $\pm1.87$ even after $10^6$ tosses——a maximum is set by the one place where heads happened to run long, so more tosses do not smooth it out.

5. The Separator

Observation 5.1 the separator is whether the sum or the maximum is looked at. From the same sequence of the same coin, taking the number of heads (a sum) gives a spread shrinking like $1/\sqrt{n}$, and taking the longest run (a maximum) gives a spread staying at $1.87$——“toss enough and it settles” is a statement about sums.

Observation 5.2 beside Paper 629. In Paper 629, the average prize over plays of the uncapped game grew like $\log_2 n$ and did not settle——here the same $\log_2 n$ appears as the growth of the longest run. In both, the rare long runs met as the number grows are what count.

Observation 5.3 what is not said. The psychology of people writing “random” sequences with runs too short is not treated, and no human-written sequences were counted——what is shown is the exact distribution of the longest run of a fair coin, how it grows, and how it spreads.

6. Roll Call and Closing

  1. $5$ or more in $200$ tosses: $0.965903$ (Computation 2.1): almost always.
  2. mean $6.984206$ for $200$ tosses (Computation 2.1): agrees with simulation.
  3. long runs are normal (Observation 2.2): they only catch the eye.
  4. $3.32$ more per tenfold (Computation 3.1): approaching $\log_2 10$.
  5. mean $-\log_2 n$ is $-0.667252$ (Computation 3.1): $0.000002$ from the asymptotic value.
  6. one more per doubling (Observation 3.2): where $n/2^{r+1}$ is about $1$.
  7. standard deviation $\mathbf{1.872689}$ (Computation 4.1): even at $10^6$ tosses.
  8. the spread does not shrink (Observation 4.2): the core.
  9. sum or maximum (Observation 5.1): the separator.
  10. the same $\log_2 n$ (Observation 5.2): Paper 629.

Closing: The longest run of heads in $n$ tosses of a fair coin has a mean of about $\log_2 n-0.667$, growing by $3.32$ for each tenfold and by one for each doubling of $n$. In $200$ tosses a run of $5$ or more appears with probability $0.965903$. The spread of the longest run does not shrink: even after $10^6$ tosses the standard deviation is $1.872689$——in contrast with the spread of the share of heads, which shrinks like $0.5/\sqrt{n}$. The separator is whether the sum or the maximum is looked at. Placed among the earlier papers——the $\log_2 n$ that kept raising the average in the game of Paper 629 appears here as the growth of the longest run. To be honest——the psychology of people writing random sequences is not entered.

References

  1. Erdős, P., & Rényi, A. (1970). On a new law of large numbers. Journal d’Analyse Mathématique.
  2. Schilling, M. F. (1990). The longest run of heads. The College Mathematics Journal.
  3. Yamagishi, Y. (2026). A Game with Infinite Expectation Has an Expectation of About $41$ Once the Bank Is Limited to $10^{12}$ [Paper 629]. Zenodo. 10.5281/zenodo.23014552

Reference

Yamagishi, Y. (2026). The Longest Run of Heads Grows by One Each Time the Tosses Double, and Its Spread Does Not Shrink [Paper 636]. YOI: https://www.yamagishiyuuki.com/yoi/636
DOI: 10.5281/zenodo.23014588
ORCID: 0009-0006-8587-3450

PDF (English) · PDF (Japanese) · Date proof of the English PDF (OpenTimestamps .ots) · SHA256SUMS

The record page for this paper (in Japanese, with the PDFs in each language and the date proof): YOI 636. This paper is a preprint and has not been peer reviewed.