UMA 2022
Years ago Zeev Rudnick defined the $\lambda$-Poisson generic sequences as the infinite sequences of symbols in a finite alphabet where the number of occurrences of long words in the initial segments follow the Poisson distribution with parameter $\lambda$. Benjamin Weiss and Yuval Peres [5] proved that almost all sequences with respect to Lebesgue measure are Poisson generic (see also [1]). Despite this result, no explicit example has yet been given.
In this talk I will present a construction of an explicit $\lambda$-Poisson generic sequence over an alphabet of at least three symbols, for any fixed positive real number $\lambda$. Since $\lambda$-Poisson genericity implies Borel normality, the constructed sequence is Borel normal. The same construction provides explicit instances of Borel normal sequences that are not $\lambda$-Poisson generic.
Given $x\in\Omega^{\mathbb N}$, and a positive real number $\lambda$, $i\in\mathbb N_0$ and $k\in\mathbb N$ we write $Z^\lambda_{i,k}(x)$ for the proportion of words of length $k$ that occur exactly $i$ times in the prefix of $x$ of length $\lfloor \lambda b^k \rfloor$.
Definition 1
Let $\lambda$ be a positive real number. A sequence $x\in\Omega^{\mathbb N}$ is $\lambda$-Poisson generic if for every $i\in \mathbb{N}_0$, \[ \lim_{k\rightarrow\infty} Z^\lambda_{i,k}(x) = e^{-\lambda} \frac{\lambda^i}{i!}. \]
A sequence is Poisson generic if it is $\lambda$-Poisson generic for all positive real numbers $\lambda$.
The main result I will discuss is the following:
Theorem 1 ([Becher and S.H. [3, Theorem 1])
Let $\lambda $ be a positive real number and $\Omega$ a $b$-symbol alphabet, $b\geq 3$. Let $(p_i)_{i\in \mathbb N_0}$ be a sequence of non-negative real numbers such that $\sum\limits_{i\geq 0}p_i=1$ and $\sum\limits_{i\geq 0}ip_i=\lambda$. Then there is a construction of an infinite sequence $x$ over alphabet $\Omega $, which satisfies for every $i\in\mathbb{N}_0$, \[ \lim_{k\rightarrow\infty} Z^\lambda_{i,k}(x) = p_i. \]
The construction in Theorem 1 consists in concatenating segments of any infinite de Bruijn sequence [2, Theorem 1], which is a sequence that satisfies that each initial segment of length $b^k$ is a cyclic de Bruijn sequence of order $k$. Our construction works by selecting segments of this given sequence and repeating them as many times as determined by the probabilities $p_i$, for every $i\in\mathbb {N}_0$.
Weiss showed that $1$-Poisson genericity implies Borel normality and that the two notions do not coincide [6], witnessed by the Champernowne sequence [4]. The next result is a normality criterion that generalizes this fact. In contrast to Theorem 1, this result does not require the alphabet size $b$ to be greater than $2$.
Theorem 2 ([Becher and S.H. [3, Theorem 2])
Let $\Omega$ be a $b$-symbol alphabet, $b\geq 2$, and let $x\in\Omega^{\mathbb{N}}$. We fix a positive real number $\lambda$ and define for every $i\in \mathbb{N}_0$ the numbers $p_i=\liminf_{k\rightarrow\infty}Z_{i,k}^{\lambda}(x)$. If the numbers $p_i$ satisfy $\sum_{i\geq 0}ip_i=\lambda$ then $x$ is normal to base $b$.
As a consequence of Theorem 2 we obtain the following:
Corollary 1
Every $\lambda$-Poisson generic sequence is Borel normal, but the two notions do not coincide. The construction in Theorem 1 yields infinitely many Borel normal sequences which are not $\lambda$-Poisson generic.
Trabajo en conjunto con: Verónica Becher (Universidad de Buenos Aires).
Referencias
[1] Nicolás Alvarez, Verónica Becher, and Martín Mereb. Poisson generic sequences. Submitted, February 4, 2022. Preprint https://arxiv.org/abs/2202.01632.
[2] Verónica Becher and Pablo Ariel Heiber. On extending de Bruijn sequences. Information Processing Letters, 111:930–932, 2011.
[3] Verónica Becher and Gabriel Sac Himelfarb. A construction of a $\lambda$ - Poisson generic sequence. Submitted, May 9, 2022. Preprint https://arxiv.org/abs/2205.03981.
[4] David Champernowne. The construction of decimals normal in the scale of ten. Journal of London Mathematical Society, s1-8(4):254–260, 1933.
[5] Benjamin Weiss. Poisson generic points. Jean-Morlet Chair 2020 - Conference: Diophantine Problems, Determinism and Randomness, Centre International de Rencontres Mathématiques, November 23 to 29, 2020. Audio- visual resource: doi:10.24350/CIRM.V.19690103.
[6] Benjamin Weiss. Random-like behavior in deterministic systems, 16 June 2010. Conference at the Institute for Advanced Study Princeton University USA.