3
$\begingroup$

If the question was stated to appeal to the general public, it would be something like this. For a number such as $\pi$ or $\sqrt{2}$, the digits in base $b$ appear to be randomly distributed. We are looking for successive runs of increasing lengths, or in other words, successive run records of the digit $0$, their respective (increasing) lengths, and the position where they occur in the base $b$ expansion of the numbers in question.

It is a probability question where a theoretical distribution is sought, not just for numbers like $\pi$ but for numbers with random digits or even strings of random characters (the digits or characters being uniformly and independently distributed). So it can be of interest for mathematicians interested in combinatorics. In my case, my interest is in the asymptotics related to approximating irrational numbers by rational ones, and in particular, by dyadic fractions.

I did some simulations, and my empirical results are consistent with what has been observed for the digits of (say) $\pi$. My simulations are summarized in the illustration below. I created 200 artificial numbers with same properties as $\pi$ (as far as the digit distribution in base $b=3$ is concerned), looking at the first million digits, with $b=3$. For one of them (a typical case), I've found this:

  • One isolated zero (the first occurrence of zero) starts at position 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 six 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), \dots $$

Now repeat the process for a very large set of numbers and blend all the sequences of vectors $(X,Y)$ together. We have, as I expected, the following very good approximation: $$Y=\log_b \bar{X}$$ where $\bar{X}$ is the average $X$ corresponding to a specific, fixed $Y$, computed on all the numbers in your sample.

Question: I am looking at the distribution of $\log X$, conditionally to $Y$. Is it Gaussian? If not what are the asymptotics?

Connection to approximations of irrationals by rational numbers

Here, the rational numbers in question are of the form $\frac{p_n}{q_n}$ with (for now), $q_n=3^n$. But there are strong analogies with best approximations or approximations with convergents of continued fractions. A best approximation for an irrational $\alpha \in [0, 1]$, in my case, occurs when the first $n$ digits end with non-zero, followed by a record run of zeros, thus the purpose of my above question. If that record run is of length $r_n$, we have $$\alpha-\frac{p_n}{q_n} \geq \frac{1}{q_{n+r_n}}$$ My simulations suggest that $r_n = b^{\lambda n} \sim q_n^\lambda$ makes sense. When you put things together, it ends up with something like this: $$S(\alpha)\equiv q^\lambda (q\alpha - p)\geq 1$$ for a large proportion of $\alpha\in[0,1]$. That proportion can be computed with as much accuracy as desired. The larger $\lambda$, the more irrationals can be approximated that way. It sounds that $\lambda>1+\epsilon$ is good enough, and maybe $S(\alpha)\equiv q \cdot (\log q) \cdot (q\alpha - p)$ can be used to define the rational part of an irrational number in the above context: find $p,q$ that minimizes $S(\alpha)$ and then the "best" (in some way) approximation of $\alpha$ by a rational is that $p/q$ achieving the minimum. For more details about my earlier investigations about this, see my previous MO question, here.

Edit: A related result for convergents $p_n/q_n$ of continued fractions is the following (it is the last theorem in this article, and pictured below):

enter image description here

In short, it seems to imply that if $\lambda=1+\epsilon$ with $\epsilon = 0$, then only some proportion of all numbers $\alpha$ will satisfy $q^\lambda |q\alpha-p|\geq 1$, where $p/q$ is any rational approximation to $\alpha$ with $p,q$ coprime positive integers. With $\epsilon > 0$, almost all $\alpha$ will. Note that in the above theorem, my number $\alpha$ is denoted as $x$.

$\endgroup$
8
$\begingroup$

The length $R_N$ of the longest run in the first $N$ digits satisfies $R_N/\log_b(N) \to 1$ almost surely as $N \to \infty$, as first proved by Renyi, see the discussion in [1]. (Many references focus on $b=2$ but the arguments work for all $b$.) The waiting times $T_k$ for the occurrence of a run of length $k$ satisfy that $T_k/E(T_k)$ is asymptotically exponentially distributed with mean 1. This can be inferred from the Clumping Heuristic [2]. Rigorous proofs in various levels of generality are in [3] and [4]. In particular [4] discusses the history at length. Exact generating functions for the law of $T_k$ are in Feller [5], generalized in [6]. Note that the mean of $T_k$ is not $b^k$ but rather $\sum_{j=1}^k b^j$; this can also be found in Feller, and is best explained by the Martingale argument of Li [7].

[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.

$\endgroup$
6
  • $\begingroup$ Thank you. I am currently investigating the case $b=\sqrt{2}$ (yes, the base need not be an integer). In that case, the distribution of 0's and 1's (the digits are binary just like for $b=2$) is not uniform, it's a bit like non-independent Bernoulli trials with $p\neq\frac{1}{2}$. Wondering if all the theory you are citing (thank you!) still holds. I may need such results to get best approximations to irrationals, by numbers such as $(a_n+b_n\sqrt{2})/2^n$ where $a_n, b_n$ are integers. $\endgroup$ – Vincent Granville Feb 8 at 0:55
  • $\begingroup$ The fact that I used $b=3$ in my simulations is due to a computer glitch. I use the chaotic dynamical system $x_{n+1}=\{bx_n\}$ to generate digits (the brackets denote the fractional part) and after 45 or so iterations, $x_n=0$ if $b=2$ due to the way computer arithmetic is performed in Perl. It words with $b=3$ (or $b=1.999999$ for that matter), the sequence is still wrong due to round-off errors growing exponentially, but at least because of ergodicity, the asymptotic results remain correct if $b$ is an odd integer. $\endgroup$ – Vincent Granville Feb 8 at 1:15
  • 2
    $\begingroup$ In the original question it seemed that $b$ was an integer. All the description and data corresponded to that. The non-integer case is a different question, also very interesting. But substantial changes/extensions to a question after someone answers reduce the effort people will put in to answer questions in the future. $\endgroup$ – Yuval Peres Feb 8 at 1:59
  • $\begingroup$ Yes, original question is for $b$ integer, and mostly $b=2$. No need to answer the case $b$ non-integer, I just thought about it as I played in the past with non-integer bases, and it leads to some exciting stuff: approximation of transcendental numbers by quadratic irrationals, rather than by rationals. $\endgroup$ – Vincent Granville Feb 8 at 2:33
  • 1
    $\begingroup$ Thanks. Yes, if $b$ is a quadratic irrational the corresponding expansion yields a Markov chain (see e.g. [IT]) and the theory of runs has been extended to that case. [IT] jstage.jst.go.jp/article/jmath1948/26/1/26_1_33/_pdf $\endgroup$ – Yuval Peres Feb 8 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.