.

Bernoulli trials are random experiments with two possible outcomes: "yes" and "no" (in the case of polls), "success" and "failure" (in the case of gambling or clinical trials). The trials are independent from each other: for instance tossing a coin multiple times, or testing the success of a new drug against a specific medical condition, on multiple patients: improvements for a specific patient is viewed as a success, lack of improvement as a failure.

Here we are interested in maximum runs of successes (also called record runs), when they are expected to occur, and their expected length or duration. While the classical application is in games of chance, we will discuss an exciting application in number theory, more specifically, very good approximations of irrational numbers by rational numbers, and numeration systems with a non-integer base. We will also consider the case where the trials are not independent, and where there are more than two outcomes. For instance, if throwing a dice rather than a coin, there are six rather than two outcomes.

The data used here is simulated and allows us to get some good approximations for a number of interesting statistics. It is based on an unusual pseudo-random number generator that is very relevant to the problem being studied. A more theoretical approach can be found here, with connections to extreme value theory and the Gumbel distribution. See also my previous article *Distribution of Arrival Times for Extreme Events*, posted here.

**1. Simulations and theoretical results**

Bernoulli trials with *b* potential outcomes, each with the same probability of occurring, can be simulated using the following system. Start with some irrational number *x*0 in [0, 1], say *x*0 = log 2 (called the *seed*), and use the following iterations:

*an* = INT(*b xn*)

*xn*+1 = *b xn* - INT(*b xn*).

INT represents the integer part function. The result of the *n*-th trial is *an*: it is a coding integer between 0 and *b* - 1 inclusive, representing for instance the result of throwing a dice with *b* sides labeled 0, ..., *b* - 1. Also, *an* is the *n*-th digit of *x*0 in base *b*. These digits are strongly conjectured to be independent from each other, and have the same probability 1 / *b* to take on any of the *b* potential values. Thus this scheme can be used to simulate the Bernoulli trials in question. Also, unlike traditional pseudorandom number generators, it does not produce periodic sequences. Such a system can be viewed as a chaotic dynamical system, just like the sine map discussed in my previous article, here.

The Bernoulli trials generated with *x*0, that is the sequence *a*0, *a*1, and so on, constitutes just one instance of a Bernoulli experiment. If you try with *N* different seeds (the number *x*0), then you end up with *N* different, independent instances of Bernoulli experiments sharing the same dynamics, and things start to become interesting.

**1.1. Simulations**

I performed *N* = 200 simulations, each representing a Bernoulli experiment starting with a different seed *x*0 each time, each consisting of 1,000,000 trials, with *b* = 3. Possible outcomes of each trial are 0, 1 or 2. I looked at successive record runs of zeros. For one of these experiments (a typical case), I've found this:

- One isolated zero (the first occurrence of zero) starts at position
*n*= 3 - The first run of 2 zeros starts at position 13 in the digits expansion
- The next longer run consists of 3 zeros, starting at position 69
- The next longer one (4 zeros) starts at position 132
- Then we have 5 zeros starting at position 670, then 6 starting at position 743, 8 starting at position 13411, 10 starting at position 58454, and 12 starting at position 384100.

The observations can be summarized by the following bivariate sequence:

(3,1), (13,2), (69,3), (132,4), (670,5), (743,6), (13411,8), (58454,10), (384100,12), …

If you blend all the sequences of vectors (*X*, *Y*) together, from the 200 experiments, you get the following:

**Figure 1**: *Record runs of Y zeros vs the position X at which they occur in a Bernoulli experiment*

Note that in Figure 1, the plot represents *Y* versus log(*X*), and *b* = 3. A record run equal to *Y* means that starting at position *X*, we observe the first instance of a (record) run consisting of *Y* consecutive zeros, in at least one of the *N* experiments. In Figure 2 featuring aggregated data, you can see the average log(*X*) computed across the *N* = 200 experiments, for any record run of length *Y* = 0, 1, 2, and so on (up to *Y* = 13). The chart speaks for itself; in the linear fit in Figure 2, the slope approaches log *b* as *N* tends to infinity.

**Figure 2**: *Same as Figure 1, with log(X) averaged across the N = 200 experiments*

**1.2. Theory**

A lot of theoretical results are known for maximum runs. We present a few of them here, with additional references. Note that in my article, I focus on record runs, which are different from maximum runs: in any Bernoulli experiment, maximum runs correspond to the first occurrence of a run of length 2, 3, 4, and so on. Record runs, as in the example outlined at the beginning of section 1, do not necessarily increase by unit increments: in my example, the first run of length 7 (not a record) occurs after the first (record) run of length 8. In short, you see a run of length 8 before you see one of length 7.

The main theoretical results, provided by Yuval Peres, are:

- Let
*Rn*be the length of the longest run in the first*n*digits. Then*Rn*log(*b*) / log(*n*) tends to 1 almost surely as*n*tends to infinity. It was first proved by Renyi, see the discussion in reference [1]. - The waiting times
*Tk*for the occurrence of a run of length*k*satisfy that*Tk*/ E(*Tk*) is asymptotically exponentially distributed with mean 1. See references [2] - [4]. We also have (see reference [5] and [7]):

All references are in section 3. Note that these theoretical results apply to any run, not just runs of zeros.

**2. Application and generalization**

If you replace the integer *b* by a non integer (strictly larger than 1), then the Bernoulli trials will inherit the properties of that unusual numeration system:

- The number of potential outcomes, for any trial, is INT(
*b*), the integer part of*b* - The trials are no longer independent: the
*n*-th outcome*an*is correlated with*an*+1 - Outcomes have different probabilities: P(
*an*= 0) is not the same as P(*an*= 1)

Nevertheless, once can still perform the same simulations to estimate the statistics of interest. If *b* is a quadratic irrational, the corresponding successive outcomes (the *an*'s) follow a Markov chain model. See here for the theoretical details.

Regardless of whether *b* is an integer or not, the application we are interested in is the approximation of irrational numbers by a specific class of numbers. This is usually done using continued fractions if the class of numbers in question consists of the rational numbers, and there is an abundant literature on this topic, see for instance here. However, we focus instead on best approximations of an irrational number *x*0 in [0, 1] by a rational number *βn*, where

Note that *βn* can be expressed as *pn* / *qn*, a quotient of two integers if *b* is an integer, with *qn* being equal to *b* at the power *n*. The best approximation is obtained when the *ak*'s are the successive outcomes of the Bernoulli experiment with seed *x*0, or in other words, the first *n* digits of *x*0 in base *b*. The approximation is exceptionally good if the last digit *an*-1 is not zero, and it is followed ty a record run of digits equal to zero. The length of that run is expected to be asymptotically of the order to (log *n*) / (log *b*). It can not be better than that, for a fixed *n*. Therefore, I propose the following conjecture, based on the probability distributions associated with extreme (record) runs discussed in section 1.

**Conjecture**

For most numbers *x*0 in [0, 1], and for any *ε* > 0, if *p* / *q* is an approximation of *x*0, with *p*, *q* co-prime positive integers, we have

The details as how I came to this conjecture are outlined in the section* Connection with approximations of irrationals by rational numbers*, in this article. While this is beyond the scope of this article, a discussion of best approximations by continued fractions leads to a similar conclusion. In particular, if *pn* / *qn* is the *n*-th convergent of the number *x*, we have the following result, see last theorem in this article, pictured below. In short, it says that if *ε* = 0, then only some proportion of all numbers *x*0 will satisfy the above inequality. With *ε* > 0, almost all *x*0 will.

Finally, record runs in Bernoulli trials is a topic of combinatorial analysis, and thus relevant to machine learning, with numerous applications in combinatorics. Also, you can learn more about non-integer bases in this article. A summary table is available here.

**3. References**

[1] Schilling, Mark F. *The longest run of heads*. The College Mathematics Journal 21, no. 3 (1990): 196-207.

[2] Aldous, David. *Probability approximations via the Poisson clumping heuristic*. Vol. 77. Springer Science & Business Media, 2013.

[3] Földes, A. *The limit distribution of the length of the longest head-run*. Period Math Hung 10, 301–310

[4] Godbole, Anant P. *Poisson approximations for runs and patterns of rare events*. Advances in applied probability (1991): 851-865.

[5] Feller, William. *An introduction to probability theory and its applications*. 1957.

[6] Gerber, Hans U., and Shuo-Yen Robert Li. *The occurrence of sequence patterns in repeated experiments and hitting times in a Markov chain*. Stochastic Processes and their Applications 11, no. 1 (1981): 101-108.

[7] Li, Shuo-Yen Robert. *A martingale approach to the study of occurrence of sequence patterns in repeated experiments*. Annals of Probability 8, no. 6 (1980): 1171-1176.

*To receive a weekly digest of our new articles, subscribe to our newsletter, here.*

**About the author**: Vincent Granville is a data science pioneer, mathematician, book author (Wiley), patent owner, former post-doc at Cambridge University, former VC-funded executive, with 20+ years of corporate experience including CNET, NBC, Visa, Wells Fargo, Microsoft, eBay. Vincent is also self-publisher at DataShaping.com, and founded and co-founded a few start-ups, including one with a successful exit (Data Science Central acquired by Tech Target). You can access Vincent's articles and books, here.

© 2021 TechTarget, Inc. Powered by

Badges | Report an Issue | Privacy Policy | Terms of Service

**Most Popular Content on DSC**

To not miss this type of content in the future, subscribe to our newsletter.

- Book: Applied Stochastic Processes
- Long-range Correlations in Time Series: Modeling, Testing, Case Study
- How to Automatically Determine the Number of Clusters in your Data
- New Machine Learning Cheat Sheet | Old one
- Confidence Intervals Without Pain - With Resampling
- Advanced Machine Learning with Basic Excel
- New Perspectives on Statistical Distributions and Deep Learning
- Fascinating New Results in the Theory of Randomness
- Fast Combinatorial Feature Selection

**Other popular resources**

- Comprehensive Repository of Data Science and ML Resources
- Statistical Concepts Explained in Simple English
- Machine Learning Concepts Explained in One Picture
- 100 Data Science Interview Questions and Answers
- Cheat Sheets | Curated Articles | Search | Jobs | Courses
- Post a Blog | Forum Questions | Books | Salaries | News

**Archives:** 2008-2014 |
2015-2016 |
2017-2019 |
Book 1 |
Book 2 |
More

**Most popular articles**

- Free Book and Resources for DSC Members
- New Perspectives on Statistical Distributions and Deep Learning
- Time series, Growth Modeling and Data Science Wizardy
- Statistical Concepts Explained in Simple English
- Machine Learning Concepts Explained in One Picture
- Comprehensive Repository of Data Science and ML Resources
- Advanced Machine Learning with Basic Excel
- Difference between ML, Data Science, AI, Deep Learning, and Statistics
- Selected Business Analytics, Data Science and ML articles
- How to Automatically Determine the Number of Clusters in your Data
- Fascinating New Results in the Theory of Randomness
- Hire a Data Scientist | Search DSC | Find a Job
- Post a Blog | Forum Questions

## You need to be a member of Data Science Central to add comments!

Join Data Science Central