L1.2

# On a probabilistic extension of the Oldenburger-Kolakoski sequence

Chloé Boisson111École Normale Supérieure de Lyon, 15 parvis René Descartes,
F-69342, Lyon, France., Damien Jamet222Université de Lorraine, Loria, UMR
7503, Vandœuvre-lès-Nancy, F-54506, France. and Irène Marcovici333Université
de Lorraine, CNRS, Inria, IECL, F-54000 Nancy, France.
<EMAIL_ADDRESS><EMAIL_ADDRESS>irene.marcovici@univ-
lorraine.fr

###### Abstract

The Oldenburger-Kolakoski sequence is the only infinite sequence over the
alphabet $\\{1,2\\}$ that starts with 1 and is its own run-length encoding. In
the present work, we take a step back from this largely known and studied
sequence by introducing some randomness in the choice of the letters written.
This enables us to provide some results on the convergence of the density of
$1$’s in the resulting sequence. When the choice of the letters is given by an
infinite sequence of i.i.d. random variables or by a Markov chain, the average
densities of letters converge. Moreover, in the case of i.i.d. random
variables, we are able to prove that the densities even almost surely
converge.

##  1 Introduction

The Oldenburger-Kolakoski sequence $122112122122112\dots$ introduced by R.
Oldenburger [12] and lately mentioned by W. Kolakoski [10] is the unique
sequence $x_{1}x_{2}x_{3}\dots$ over the alphabet $\\{1,2\\}$ with $x_{1}=1$
and whose $k$-th block has length $x_{k}$ for $k\in\mathbb{N}^{\star}$.

In [9] M.S. Keane asked whether the density of $1$’s in this sequence is
$1/2$. In [7], V. Chvátal showed that the upper density of $1$’s (resp. $2$’s)
is less than 0.50084. This bound has been slightly improved by M. Rao but
Keane’s question still stands: << Is the density of $1$’s in Oldenburger-
Kolakoski sequence defined and equal to $0.5$? >>

By definition, the Oldenburger-Kolakoski sequence
$\mathcal{O}=(x_{n})_{n\in\mathbb{N}\star}$ is a fixed point of the run-length
encoding operator denoted $\Delta$:

$\displaystyle\stackunder{\mathcal{O}}{\Delta(\mathcal{O})}$
$\displaystyle\stackunder{=}{=}$
$\displaystyle\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{1}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{1}\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{22}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{2}\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{11}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{2}\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{2}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{1}\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{1}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{1}\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{22}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{2}\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{1}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{1}\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{22}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{2}\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{11}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{2}\dots=1^{1}2^{2}1^{2}2^{1}1^{1}2^{2}1^{1}2^{2}1^{2}\dots$
(19) $\displaystyle\mathcal{O}$ $\displaystyle=$ $\displaystyle
1^{x_{1}}2^{x_{2}}1^{x_{3}}2^{x_{4}}1^{x_{5}}2^{x_{6}}1^{x_{7}}2^{x_{8}}1^{x_{9}}=\prod_{n\in\mathbb{N}}(1^{x_{2n+1}}2^{x_{2n+2}})$
(20)

In [12], R. Oldenburger refers to sequences over an alphabet $\Sigma$ as
_trajectories_ and refers to the sequence $\Delta(w)$ as the _exponent
trajectory_ of the trajectory $w$. He stated that << a periodic trajectory is
distinct from its exponent trajectory >> (Theorem 2, [12]) and, therefore, the
Oldenburger-Kolakoski sequence is not periodic.

The Oldenburger-Kolakoski sequence is also connected to differentiable words,
$C^{\infty}$-words and smooth words [2, 4, 8]. A sequence $w$ over the
alphabet $\Sigma\subset\mathbb{N}^{\star}$ is _differentiable_ if and only if
$\Delta(w)$ is also defined over the same alphabet $\Sigma$. The sequence
$\Delta(w)$ is called the _derivative sequence_ of $w$ [8]. A _$C^{\infty}$
-word_, or _smooth word_ , is an infinitely differentiable sequence.
Obviously, the Oldenburger-Kolakoski sequence is a $C^{\infty}$-word since it
is a fixed-point of the run-length encoding operator $\Delta$.

Although not answering Keane’s question fully, F.M. Dekking established
connections between possible combinatorial properties of the Oldenburger-
Kolakoski sequence [8]: if the Oldenburger-Kolakoski sequence is closed by
complementation (that is, if $w$ occurs in $\mathcal{O}$ then so does
$\widetilde{w}$ with $\widetilde{1}=2$ and $\widetilde{2}=1$) then it is
recurrent (any word that occurs in $\mathcal{O}$ does so infinitely often)
(Prop. 1, [8]). Moreover, the Oldenburger-Kolakoski sequence is closed by
complementation if and only if it contains every finite $C^{\infty}$-word
(Prop. 2, [8]).

A few years later, A. Carpi stated that the Oldenburger-Kolakoski sequence
contains only a finite set of squares (words of the form $xx$ where $x$ is not
empty) and does not contain any cube (word of the form $xxx$ where $x$ is not
empty) [6]. Hence, since $\mathcal{O}$ contains only squares of bounded length
then it cannot be the fixed point of a non degenerated morphism: the image of
a square $w=xx$ by such a morphism is still a square longer than $w$.

There exist several ways to extend the definition of the Oldenburger-Kolakoski
sequence, depending on whether one wants to preserve the fixed point property
or to follow the construction scheme without requiring the resulting sequence
to be a fixed point for the run-length encoding operator $\Delta$. For
instance, one can deal with other alphabets and thus construct _Generalized
Oldenburger-Kolakoski_ sequence (GOK-sequence for short) as follows: for any
pair $(a,b)$ of non-zero natural numbers, there exists a unique fixed point
$\mathcal{O}_{a,b}$ of $\Delta$ over the alphabet $\\{a,b\\}$ starting with
$a$. Also, according to this notation, the original Oldenburger-Kolakoski
sequence is $\mathcal{O}_{1,2}$. For instance, if $a=1$ and $b=3$, the first
terms of $\mathcal{O}_{1,3}$ are:

$\mathcal{O}_{1,3}=\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{1}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{1}\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{333}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{3}\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{111}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{3}\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{333}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{3}\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{1}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{1}\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{3}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{1}\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{1}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{1}\mathop{\vtop{\halign{#\cr$\hfil\displaystyle{333}\hfil$\crcr\kern
3.0pt\nointerlineskip\cr$\bracelu\leaders\vrule
height=0.39998pt,depth=0.0pt\hfill\braceru$\crcr\kern
3.0pt\cr}}}\limits_{3}\dots=1^{1}3^{3}1^{3}3^{3}1^{1}3^{1}1^{1}3^{3}\dots$
(21)

A significant result is, unlike the case of the original Oldenburger-Kolakoski
sequence, that the densities of $1$’s in $\mathcal{O}_{1,3}$ and
$\mathcal{O}_{3,1}$ are known and approximately 0.3972 [1].

Generalized Oldenburger-Kolakoski sequences are also connected with smooth
words over arbitrary alphabets [3, 5]. As for the (Generalized) Oldenburger-
Kolakoski sequences, the properties of smooth words are better known for
alphabets with letters of the same parity: for instance, while the frequency
of letters in an infinite smooth word over $\\{1,2\\}$ is still unsolved, in
[5] the authors showed that the frequency of letters for extremal smooth words
(for the lexicographic order) over the alphabet $\\{a,b\\}$, where $a$ and $b$
are both even, is 0.5. They also computed the frequency for extremal smooth
words over alphabets of type $\\{1,b\\}$, where $b$ is odd. Moreover, if $a$
and $b$ have the same parity, then every infinite smooth word over the
alphabet $\\{a,b\\}$ is recurrent [5]. Also, if $a$ and $b$ are both odd, then
every infinite smooth word is closed under reversal but not under
complementation [5]. On the other hand, if $a$ and $b$ are both even, then the
extremal smooth words over the alphabet $\\{a,b\\}$ are neither closed under
reversal nor closed under complementation [5].

For a more detailed survey on the Oldenburger-Kolakoski sequence and on
generalizations over arbitrary two letter alphabets see [13].

##  2 Extending the construction scheme to any directing sequence

###  2.1 Notion of directing sequence.

In the construction scheme of a Generalized Oldenburger-Kolakoski sequence,
the blocks of $\mathcal{O}_{a,b}$ are composed, alternatively, of $a$’s and
$b$’s as shown in (19) when $a=1$ and $b=2$ and in (21) when $a=1$ and $b=3$.
In other words, if $t_{1}=a$ and $t_{2}=b$, then << the $i^{\mathrm{th}}$
block of $\mathcal{O}_{a,b}=(x_{i})_{i\in\mathbb{N}^{\star}}$ is of length
$x_{i}$ and is filled with the letter $t_{i\mod 2}$ >>.

This construction scheme is clearly extendable to any finite sequences
$T=(t_{1},t_{2},\dots)$ over $\\{a,b\\}$ as follows: << the $i^{\mathrm{th}}$
block of $\mathcal{O}_{T}=(x_{i})_{i\in\mathbb{N}^{\star}}$ is of length
$x_{i}$ and is filled with the letter $t_{i}$ >> (see Program 1).

⬇

1def O(T):

2 X = []

3 k = 0

4 for x in T:

5 X += [x] # concatenate ’x’ at the end of X

6 X += [x]*(X[k]-1) # concatenate ’X[k]-1’ copie(s) of x

7 k += 1

8 return X

Program 1: Python function: $\mathcal{O}$ is an operates on sequences over
$\mathbb{N}^{\star}$.

We say that the sequence $\mathcal{O}_{T}$ is _directed_ by the sequence $T$
and the sequence $T$ is a _directing sequence_ of $\mathcal{O}_{T}$. For
instance, the sequence $\mathcal{O}_{a,b}$ is directed by $T=(ab)^{\omega}$
while $\mathcal{O}$ is directed by $(12)^{\omega}$. Notice that the directed
sequence $\mathcal{O}_{T}$ may no longer be a fixed point of the operator
$\Delta$.

Let us now take a closer look at how the construction of $\mathcal{O}_{T}$
provides a little more information than the sequence itself. For instance, let
$T=(t_{n})_{n\in\mathbb{N}^{\star}}=21122\dots$ be a sequence over
$\\{1,2\\}$:

  1. Step 1:

$\mathcal{O}_{t_{1}}=22$ and the second block is of length $2$: hence the 3
and 4 letters are in a same block of length 2. Let us denote
$\mathcal{O}_{t_{1}}=\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{22}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}$.

  2. Step 2:

$\mathcal{O}_{t_{1}t_{2}}=\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{22}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{11}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}$: the 5 and the 6
letter are respectively in blocks of length $1$.

  3. Step 3:

$=\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{22}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{11}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{1}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}$: the 7 letter is in
a block of length $1$.

Roughly speaking, $t_{1}$ gives the length of all the blocks that contain up
to the 4 letter, $t_{1}t_{2}$ gives the length of all the blocks that contain
up the 6 letter and so on… Let $w_{n}=\mathcal{O}_{t_{1}\dots t_{n}}$ for each
$n\in\mathbb{N}^{\star}$ , then $\sum^{|w_{1}|}_{i=1}{[w_{1}]_{i}}=4$ ,
$\sum^{|w_{2}|}_{i=1}{[w_{2}]_{i}}=6$, $\sum^{|w_{3}|}_{i=1}{[w_{3}]_{i}}=7$…

###  2.2 Partitions of the set of directing sequences

We now introduce some subsets of directing sequences that will be crucial in
the following sections. For this purpose, let us classify the sequences $T$
according to the information they provide on the length of the blocks of
$\mathcal{O}_{T}$: let $k$ and $n$ be two integers such that $1\leq k\leq n$
and let $\mathcal{S}_{n,k}$ be the set of sequences
$T=(t_{n})_{n\in\mathbb{N}}$ such that the length of the block of
$\mathcal{O}_{T}$ containing its $n$th letter is known when reading $t_{k}$
but not before. Formally, if $w_{n}=\mathcal{O}_{t_{1}\dots t_{n}}$, then we
have

$\mathcal{S}_{n,k}=\Big{\\{}(t_{1},...,t_{n})\in\\{1,2\\}^{n}:\min\\{j\in\llbracket
1;n\rrbracket,\sum^{|w_{j}|}_{i=1}{[w_{j}]_{i}}\geq n\\}=k\Big{\\}}.$ (22)

Let us give a short example to illustrate the latter definition: let $n=5$ and
let $T=(t_{1},t_{2},t_{3},t_{4},t_{5})=(2,1,1,2,2)$. After the first step and
the reading of $t_{1}$, we only know that $t_{1}=2$ and still do not know the
length of the block that will contain the 5 letter of $\mathcal{O}_{T}$. On
the other hand, after having taken knowledge of the value of $t_{2}$, we know
that the 5 letter of $\mathcal{O}_{T}$ will be written in a block of size 1.
Hence, $T\in\mathcal{S}_{5,2}$. More generally,

  1. Step 1:

$\mathcal{O}_{t_{1}}=\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{22}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}$ and
$T\in\mathcal{S}_{3,1}\cap\mathcal{S}_{4,1}$ since $t_{1}$ provides the length
of the block containing the 3 and the 4 of $\mathcal{O}_{T}$.

  2. Step 2:

$\mathcal{O}_{t_{1}t_{2}}=\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{22}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{11}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}$: the 5 and the 6
letter are respectively in blocks of length $1$. Hence
$T\in\mathcal{S}_{5,2}\cap\mathcal{S}_{6,2}$.

  3. Step 3:

$\mathcal{O}_{t_{1}t_{2}t_{3}}=\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{22}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{11}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{1}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}$ and
$T\in\mathcal{S}_{7,3}$.

  4. Step 4:

$\mathcal{O}_{t_{1}t_{2}t_{3}t_{4}}=\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{22}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{11}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{1}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{2}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}$ and
$T\in\mathcal{S}_{8,4}\cap\mathcal{S}_{9,4}$.

  5. Step 5:

$\mathcal{O}_{t_{1}t_{2}t_{3}t_{4}t_{5}}=\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{22}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{11}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{1}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{2}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{2}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}$ and
$T\in\mathcal{S}_{10,5}\cap\mathcal{S}_{11,5}$.

The set $\\{\mathcal{S}_{n,k}:k\in\llbracket 1;n\rrbracket\\}$ is a partition
of $\\{1,2\\}^{n}$. Indeed, the length of the word $w_{n}$ is at least $n$,
since at each step, after reading $t_{i}$, we write at least one letter of
$\mathcal{O}_{T}$. And each letter is 1 or 2, so
$\sum^{|w_{n}|}_{i=1}{[w_{n}]_{i}}\geq n$.

Let us notice that $\mathcal{S}_{n,n}=\\{(1,...,1),(1,...,1,2)\\}$. Indeed,
the length of $w_{n-1}$ is at least $n-1$, and is exactly $n-1$ if and only if
the written letters are all 1’s. Moreover
$\mathcal{S}_{n,n-1}=\\{(1,...,1,2,1),(1,...,1,2,2)\\}$. Indeed, one easily
check that $(1,...,2,1),(1,...,2,2)\in\mathcal{S}_{n,n-1}$. Reciprocally, if
$(t_{1},\dots,t_{n})\in\mathcal{S}_{n,n-1}$, then there exists $i\in\llbracket
1;n-1\rrbracket$ such that $t_{i}=2$. Let us note that the first $2$ in $T$ is
written twice. Thus, if there were such a $i$ in $\llbracket 1;n-2\rrbracket$
we would have $\sum^{|w_{n-2}|}_{i=1}{[w_{n-2}]_{i}}\geq n$.

###  2.3 Extension of the definition to infinite directing sequences

Now that we have started studying the notions of directing and directed
sequences, a natural question arises: << Can one extend the definition of
$\mathcal{O}_{T}$ sequences to infinite (possibly not periodic) sequences $T$?
>> Let $\mathcal{A}\subseteq\mathbb{N}^{\star}$ be an alphabet and let
$T=(t_{n})_{n\in\mathbb{N}^{\star}}$ be an infinite sequence over
$\mathcal{A}$. By construction, $\mathcal{O}_{t_{1}\dots t_{n}}$ is a prefix
of $\mathcal{O}_{t_{1}\dots t_{n+1}}$for each $n\in\mathbb{N}^{\star}$. One
thus defines $\mathcal{O}_{T}$ as the limit of $\mathcal{O}_{t_{1}\dots
t_{n}}$ when $n$ tends to infinity:
$\mathcal{O}_{T}=\displaystyle\lim_{n\to\infty}\mathcal{O}_{t_{1}\dots
t_{n}}$.

The present work deals with the densities of letters in $\mathcal{O}_{T}$ when
$T=(t_{n})_{n\in\mathbb{N}^{\star}}$ is an infinite sequence over
$\mathcal{A}$. Do these densities exist? If so, how much are they value?

We are especially interested in the case where the directing sequence is
random. Let $\mathbb{T}=(T_{n})_{n\in\mathbb{N}^{\star}}$ be a sequence of
random variables. By definition, the sequence directed by $\mathbb{T}$ is the
random sequence $\mathbb{X}=(X_{n})_{n\in\mathbb{N}^{\star}}$ defined by
$\mathbb{X}=\mathcal{O}_{{\mathbb{T}}}$.

The present paper is organized as follows. In section 3, we consider the case
where the directing sequence is made of independent and identically
distributed (i.i.d.) random variables over a two-letter alphabet. In section
4, we treat the case where the random sequence $\mathbb{X}$ is directed by a
Markov chain.

##  3 Sequence directed by independent random variables

In the present section, $\mathbb{T}=(T_{n})_{n\in\mathbb{N}^{\star}}$ is a
sequence of independent and identically distributed random variables (i.i.d.
for short) over the two-letter alphabet $\mathcal{A}=\\{1,2\\}$, with
$\mathbb{P}(T_{n}=1)=p$ and $\mathbb{P}(T_{n}=2)=1-p$ for each
$n\in\mathbb{N}^{\star}$, where $p$ is a fixed parameter in $]0,1[$. The
sequence $\mathbb{T}$ is thus distributed according to the _product
distribution_ $(p\delta_{1}+(1-p)\delta_{2})^{\otimes{\mathbb{N}^{\star}}}$.
We denote
$\mathbb{T}\sim((p\delta_{1}+(1-p)\delta_{2})^{\otimes{\mathbb{N}^{\star}}}$.

Let $\mathbb{X}=(X_{n})_{n\in\mathbb{N}^{\star}}$ be the sequence directed by
$\mathbb{T}$. The sequence $\mathbb{X}$ is a random sequence with a priori
unknown distribution. Assume that one wants to compute the $n$th letter
$X_{n}$ of $\mathbb{X}$, for some large integer $n$. Unless the sequence
$\mathbb{T}$ begins with a long succession of $1$’s (an event which has a low
probability to occur), one just has to read the first terms
$T_{1},\ldots,T_{k}$ of $\mathbb{T}$, until knowing the length and position of
the block containing $X_{n}$, and to fill that block by $1$’s with probability
$p$, or by $2$’s with probability $1-p$. The resulting value of $X_{n}$
obtained that way will have the desired distribution. This leads to the fact
that $\lim_{n\to\infty}{\mathbb{P}}(X_{n}=1)=p$, and we can even use this
observation to compute more precisely the value of ${\mathbb{P}}(X_{n}=1)$, as
shown in the following proposition.

######  Proposition 1.

If $\mathbb{T}\sim(p\delta_{1}+(1-p)\delta_{2})^{\otimes{\mathbb{N}^{\star}}}$
with $p\in]0,1[$, then for any $n\geq 2$,

$\displaystyle\mathbb{P}{(X_{n}=1)}=p(1-p^{n-2}+p^{n-1}).$

###### Proof.

We will decompose the event $\\{X_{n}=1\\}$ according to the partition
$\\{\mathcal{S}_{n,k}:k\in\llbracket 1;n\rrbracket\\}$ of $\\{1,2\\}^{n}$
introduced in the previous section, and use the observations (LABEL:eq:S1) and
(LABEL:eq:S2). The following two particular cases are obvious:

$\mathbb{P}(X_{n}=1\,|\,(T_{1},...,T_{n})\in\mathcal{S}_{n,n})=p,\quad\mbox{
and }\quad\mathbb{P}(X_{n}=1\,|\,(T_{1},...,T_{n})\in\mathcal{S}_{n,n-1})=0.$

Let us now consider some $(T_{1},...,T_{n})\in\mathcal{S}_{n,k}$, with
$k<n-1$. Let $k^{\prime}$ be the unique integer such that
$|w_{k^{\prime}-1}|<n$ and $|w_{k^{\prime}}|\geq n$. Concretely, the $n$th
letter $X_{n}$ is written during the $k^{\prime}$th step, and it is equal to
$T_{k^{\prime}}$. By definition of $\mathcal{S}_{n,k}$, we have
$k^{\prime}\geq k$. Let us show that $k^{\prime}\neq k$. We reason by
contradiction and assume that $k^{\prime}=k$. Let us now look at what we know
at the end of the $k-1$th step.

  * •

By definition of $k^{\prime}$, $X_{n}$ will be written in the next block to
the right of $w_{k^{\prime}-1}$.

  * •

By definition of $k$, we do not know the length of this block yet.

Consequently, we do not know the length of any (empty) block to the right of
$w_{k^{\prime}-1}$. It directly implies that $w_{k^{\prime}-1}$ is made of 1’s
(and thus, that $w_{k^{\prime}-1}=1^{k^{\prime}-1}$). It follows that
$n\leq|w_{k^{\prime}}|\leq|w_{k^{\prime}-1}|+2=k^{\prime}+1$. Since
$k^{\prime}=k<n-1$, we get a contradiction, which means that $k<k^{\prime}$.

The fact that $(T_{1},...,T_{n})$ belongs to $\mathcal{S}_{n,k}$ only depends
on the beginning $(T_{1},...,T_{k})$ of the sequence. Recall that $\mathbb{T}$
has a product distribution
$(p\delta_{1}+(1-p)\delta_{2})^{\otimes{\mathbb{N}^{\star}}}.$ Since
$k^{\prime}>k$, and $X_{n}=T_{k^{\prime}}$, we deduce that

$\mathbb{P}(X_{n}=1\,|\,(T_{1},...,T_{n})\in\mathcal{S}_{n,k})=p.$

Finally, we use the formula of total probability:

$\displaystyle\mathbb{P}(X_{n}=1)$
$\displaystyle=\sum_{k=1}^{n-2}\;\mathbb{P}((T_{1},...,T_{n})\in\mathcal{S}_{n,k})\times\mathbb{P}(X_{n}=1\,|\,(T_{1},...,T_{n})\in\mathcal{S}_{n,k})$
$\displaystyle\qquad+\mathbb{P}((T_{1},...T_{n-1})=(1,...,1))\times\mathbb{P}(X_{n}=1\,|\,(T_{1},...,T_{n-1})=(1,...,1))$
$\displaystyle\qquad+\mathbb{P}((T_{1},...T_{n-1})=(1,...,2))\times\mathbb{P}(X_{n}=1\,|\,(T_{1},...,T_{n-1})=(1,...,2))$
$\displaystyle=\big{(}1-(p^{n}+2(1-p)p^{n-1}+p^{n-2}(1-p)^{2})\big{)}\times
p+p^{n}\times 1+0$ $\displaystyle=p(1-p^{n-2}+p^{n-1}).$

∎

As a corollary, we obtain the following convergence of the proportion of $1$’s
in $\mathbb{X}$.

######  Corollary 1.

If $\mathbb{T}\sim(p\delta_{1}+(1-p)\delta_{2})^{\otimes{\mathbb{N}^{\star}}}$
with $p\in]0,1[$, then

$\lim_{n\to\infty}\dfrac{\mathbb{E}(|X_{1}\dots X_{n}|_{1})}{n}=p$

###### Proof.

Since $\mathbb{X}$ has values in $\\{1,2\\}$, we have $|X_{1}\dots
X_{n}|_{1}=2n-(X_{1}+...+X_{n}).$ It follows that

$\dfrac{\mathbb{E}(|X_{1}\dots
X_{n}|_{1})}{n}=2-\dfrac{\sum_{k=1}^{n}\mathbb{E}(X_{k})}{n}.$

By Proposition 1, we have $\lim_{n\to\infty}\mathbb{P}(X_{n}=1)=p$ and
$\lim_{n\to\infty}\mathbb{P}(X_{n}=2)=1-p$. We deduce that
$\lim_{n\to\infty}\mathbb{E}(X_{n})=2-p$. By Cesàro lemma, we obtain:

$\lim_{n\to\infty}\dfrac{\mathbb{E}(|X_{1}\dots X_{n}|_{1})}{n}=2-(2-p)=p.$

∎

Each time we run a simulation with
$\mathbb{T}\sim(p\delta_{1}+(1-p)\delta_{2})^{\otimes{\mathbb{N}^{\star}}}$,
the frequency of $1$’s in $\mathbb{X}$ seems to converge to $p$. We thus
expect the sequence ${|X_{1}\dots X_{n}|_{1}}/{n}$ to converge almost surely
to $p$, and not only in expectation. Since the random variables
$(X_{n})_{n\in\mathbb{N}^{\star}}$ are correlated, we can not directly apply
the strong law of large numbers (SLLN) to prove the almost sure convergence of
$(X_{1}+...+X_{n})/n$. However, the correlations being sufficiently weak, we
can apply the following stronger version of the SLLN.

######  Theorem 1 (Lyons [11]).

Let $(Y_{n})_{n\in\mathbb{N^{\star}}}$ be a sequence of real-valued random
variables such that for all $n\in\mathbb{N^{\star}},$ $|Y_{n}|\leq 1$ and

$\forall n,m\in\mathbb{N^{\star}},\
\mathbb{E}(Y_{m}Y_{n})\leq\Phi(|n-m|),\quad\mbox{ with }\Phi\geq 0\mbox{ and
}\sum_{n\geq 1}\frac{\Phi(n)}{n}<\infty.$

Then $\displaystyle\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}Y_{k}=0$ almost
surely.

In order to apply Theorem 1, let us first prove the following lemma.

######  Lemma 1.

If $\mathbb{T}\sim(p\delta_{1}+(1-p)\delta_{2})^{\otimes{\mathbb{N}^{\star}}}$
with $p\in]0,1[$, then for any $m\geq 1$ and any $n\geq m+2$,

$\mathbb{P}(X_{m}=2\mbox{ and~}X_{n}=1)=p\times\mathbb{P}(X_{m}=2).$

###### Proof.

Since $\mathcal{S}_{n,n}\cap(X_{m}=2)=\emptyset$ and
$\mathcal{S}_{n,n-1}\cap(X_{m}=2)=\emptyset$, we have

$\mathbb{P}(X_{m}=2\,\cap\,X_{n}=1)=\sum_{k=1}^{n-2}\mathbb{P}(X_{m}=2\,\cap\,X_{n}=1\,\cap\,(T_{1},...,T_{n})\in\mathcal{S}_{n,k}).$

It follows that

$\displaystyle\mathbb{P}(X_{m}=2\,\cap\,X_{n}=1)$
$\displaystyle=\sum_{k=1}^{n-2}\mathbb{P}((T_{1},...,T_{n})\in\mathcal{S}_{n,k})\times\mathbb{P}(X_{n}=1\
|\ (T_{1},...,T_{n})\in\mathcal{S}_{n,k})$
$\displaystyle\qquad\qquad\times\mathbb{P}(X_{m}=2\ |\
X_{n}=1\,\cap\,(T_{1},...,T_{n})\in\mathcal{S}_{n,k})$

First, observe that for $k\leq n-2$, $\mathbb{P}(X_{n}=1\ |\
(T_{1},...,T_{n})\in\mathcal{S}_{n,k})=p$. Let us now prove that

$\mathbb{P}(X_{m}=2\ |\
X_{n}=1\,\cap\,(T_{1},...,T_{n})\in\mathcal{S}_{n,k})=\mathbb{P}(X_{m}=2\ |\
(T_{1},...,T_{n})\in\mathcal{S}_{n,k}).$

It is equivalent to proving that when $X_{m}=2$ and
$(T_{1},...,T_{n})\in\mathcal{S}_{n,k}$ are not incompatible,

$\mathbb{P}(X_{n}=1\ |\
X_{m}=2\,\cap\,(T_{1},...,T_{n})\in\mathcal{S}_{n,k})=\mathbb{P}(X_{n}=1\ |\
(T_{1},...,T_{n})\in\mathcal{S}_{n,k}).$

Let $i$ be the integer such that the letter $X_{m}$ is given by $T_{i}$. We
can decompose the event $(T_{1},...,T_{n})\in\mathcal{S}_{n,k}$ into the two
following cases.

  1. 1.

If $i>k$, then after reading $(T_{1},\ldots,T_{k})$, we know the size of the
blocks containing $X_{m}$ and $X_{n}$ but not their content:

$\underset{\text{$w_{k}$}}{\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{$\times\times\times\times\times\times\times\times$}\kern
1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}}\
\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\
\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\
\underset{X_{m}}{\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{2}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}}\
\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\
\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\
\underset{X_{n}}{\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}}.$

In this case, the variables giving the values of $X_{m}$ and $X_{n}$ are
independent, thus the additional information that $X_{m}=2$ does not affect
the probability of having $X_{n}=1$.

  2. 2.

If $i\leq k$, then reading $(T_{1},\ldots,T_{k})$ already tells us whether
$X_{m}=2$, but does not give us the content of the block containing $X_{n}$,
which is drawn independently:

$\underset{\text{$w_{k}$ contains $X_{m}$}}{\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{$\times\times\times\times\times\times 2\ \times$}\kern
1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}}\
\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\
\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\
\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\
\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\
\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\
\underset{X_{n}}{\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}}.$

In all cases, we have

$\mathbb{P}(X_{n}=1\ |\
X_{m}=2\,\cap\,(T_{1},...,T_{n})\in\mathcal{S}_{n,k})=\mathbb{P}(X_{n}=1\ |\
(T_{1},...,T_{n})\in\mathcal{S}_{n,k})=p.$

We deduce that

$\displaystyle\mathbb{P}(X_{m}=2\,\cap\,X_{n}=1)$
$\displaystyle=\sum_{k=1}^{n-2}\mathbb{P}(T_{1},...,T_{n})\in\mathcal{S}_{n,k})\times
p\times\mathbb{P}(X_{m}=2\ |\ (T_{1},...,T_{n})\in\mathcal{S}_{n,k})$
$\displaystyle=p\times\mathbb{P}(X_{m}=2).$

∎

We can now state the following theorem.

######  Theorem 2.

If $\mathbb{T}\sim(p\delta_{1}+(1-p)\delta_{2})^{\otimes{\mathbb{N}^{\star}}}$
with $p\in]0,1[$, then

$\lim_{n\to\infty}\dfrac{|X_{1}\dots X_{n}|_{1}}{n}=p\text{ almost surely.}$

###### Proof.

In order to apply Theorem 1, we need to center the random variables
$(X_{n})_{n\in\mathbb{N}^{\star}}$. For $n\in\mathbb{N}^{\star}$, we thus
introduce the random variables $\tilde{X}_{n}=X_{n}-(2-p),$ in order to have
$|\tilde{X}_{n}|\leq 1$ and $\lim_{n\to\infty}\mathbb{E}(\tilde{X}_{n})=0$.
Now, let us exploit Lemma 1 to compute
$\mathbb{E}(\tilde{X}_{m}\tilde{X}_{n})$, for $n\geq m+2$. We have

$\displaystyle\mathbb{P}(\tilde{X}_{m}=p\,\cap\,\tilde{X}_{n}=p-1)=p\times\mathbb{P}(X_{m}=2),$
$\displaystyle\mathbb{P}(\tilde{X}_{m}=p\,\cap\,\tilde{X}_{n}=p)=(1-p)\times\mathbb{P}(X_{m}=2),$
$\displaystyle\mathbb{P}(\tilde{X}_{m}=p-1\,\cap\,\tilde{X}_{n}=p-1)=1-\mathbb{P}(X_{n}=2)-p\,\mathbb{P}(X_{m}=2),$
$\displaystyle\mathbb{P}(\tilde{X}_{m}=p-1\,\cap\,\tilde{X}_{n}=p)=\mathbb{P}(X_{n}=2)-(1-p)\,\mathbb{P}(X_{m}=2).$

Gathering these values and using Proposition 1, we obtain

$\mathbb{E}(\tilde{X}_{n}\tilde{X}_{m})=-(1-p)^{2}p^{n-1}\leq 0.$

Let us define a function $\Phi:\mathbb{N}^{\star}\to{\mathbb{R}}$ by
$\Phi(0)=\Phi(1)=1$ and for all $k\geq 2,\Phi(k)=0$. Then
$\mathbb{E}(\tilde{X}_{m}\tilde{X}_{n})\leq\Phi(|n-m|)$ for all
$m,n\in\mathbb{N}^{\star}$, and $\Phi$ satisfies obviously $\Phi\geq 0$ and
$\sum_{n\geq 1}\frac{\Phi(n)}{n}<\infty$. By Theorem 1, we deduce that

$\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}\tilde{X}_{k}=0\mbox{ almost
surely}.$

Consequently,
$\displaystyle\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}X_{k}=2-p\mbox{
a.s.},$ and

$\lim_{n\to\infty}\dfrac{|X_{1}\dots X_{n}|_{1}}{n}=p\text{ almost surely.}$

∎

To conclude on the case of a directing sequence following a product
distribution, let us mention that the previous results can be extended to
other alphabets. In particular, Proposition 1 is extended as follows.

######  Proposition 2.

Let $a,b\in\mathbb{N}^{\star}$ with $1<a<b$, and let $p\in]0,1[$.

  1. 1.

If $\mathcal{A}=\\{1,a\\}$ and
$\mathbb{T}\sim(p\delta_{1}+(1-p)\delta_{a})^{\otimes{\mathbb{N}^{\star}}}$,
then

$\forall n\geq a,\quad\mathbb{P}(X_{n}=1)=p\left(1-p^{n-a}+p^{n-1}\right)$

  2. 2.

If $\mathcal{A}=\\{a,b\\}$ and
$\mathbb{T}\sim(p\delta_{a}+(1-p)\delta_{b})^{\otimes{\mathbb{N}^{\star}}}$,
then

$\forall n\geq b+1,\quad\mathbb{P}(X_{n}=a)=p.$

###### Proof.

  1. 1.

We use the same partition as in the proof of Proposition 1, but we now
distinguish the sets $\mathcal{S}_{n,k}$ for $n-a+1\leq k\leq n$. We have
$\mathcal{S}_{n,n}=\\{(t_{1},\dots,t_{n})\in\\{1,a\\}^{n}:(t_{1},\dots,t_{n-1})=(1,\dots,1)\\},$
and for $n-a+1\leq k\leq n-1$,

$\mathcal{S}_{n,k}=\\{(t_{1},\dots,t_{n})\in\\{1,a\\}^{n}:(t_{1},\dots,t_{k})=(1,\dots,1,a)\\}.$

If $n-a+1\leq k\leq n-1$, then for the same reason as before,
$\mathbb{P}(X_{n}=1\,|\,(T_{1},\dots,T_{n})\in\mathcal{S}_{n,k})=0$. In all
the other cases,
$\mathbb{P}(X_{n}=1\,|\,(T_{1},\dots,T_{n})\in\mathcal{S}_{n,k})=p$. Thus,

$\mathbb{P}(X_{n}=1)=p(1-p^{n-2}(1-p)-\dots-p^{n-a}(1-p))=p\left(1-p^{n-a}+p^{n-1}\right).$

  2. 2.

Since $a>1$, we have
$\sum_{j=1}^{|w_{k}|}[w_{k}]_{j}-|w_{k}|\geq(a-1)|w_{k}|>0$ for all
$k\in\mathbb{N}^{\star}$. This means that we always know the length of at
least one empty block after the $k$th step. Thus, except if $n\leq b$ (in
which case the $n$th letter might be written during the first step), we are
sure that we will know the length of the block containing the $n$th letter
strictly before filling it. As the $T_{j}$ are independent, we deduce that
$\mathbb{P}(X_{n}=a)=p$.

∎

##  4 Sequence directed by a Markov chain

In order to get closer to the deterministic case where a 1 always follows a 2
and vice versa, we are now interested in the case of directing sequences which
are given by Markov chains.

In the present section, we assume that the directing sequence
$\mathbb{T}=(T_{n})_{n\in\mathbb{N}^{\star}}$ is a Markov chain over the
alphabet $\\{1,2\\}$ with initial value $T_{1}=1$ and whose transition
probability from 1 to 2 (and from 2 to 1) is $p\in]0,1[$. A large value of $p$
encourages the alternation between 1 and 2. The original case of the
Oldenburger-Kolakoski sequence can be viewed as a << limit >> case of a Markov
chain whose transition probability from 1 to 2 (and from 2 to 1) would be
equal to 1.

######  Theorem 3.

Let $p\in]0,1[$ and let $\mathbb{T}$ be a Markov chain over the alphabet
$\\{1,2\\}$ with initial value $T_{1}=1$ and whose transition probability from
1 to 2 (and from 2 to 1) is $p\in]0,1[$. Then

$\displaystyle\lim_{n\to\infty}{\mathbb{P}(X_{n}=1)}=\dfrac{1}{2}.$

###### Proof.

Let us first note that for all integers $s>r\geq 1$, $\mathbb{P}(T_{s}=1\ |\
T_{r}=1)=\frac{1}{2}(1+(1-2p)^{s-r})$ and $\mathbb{P}(T_{s}=1\ |\
T_{r}=2)=\frac{1}{2}(1-(1-2p)^{s-r})$.

Let $\ell\in\mathbb{N}^{\star}$ and let $n\geq 2\ell$. Consider the integer
$k\in\mathbb{N}^{\star}$ such that $(T_{1},...,T_{n})\in\mathcal{S}_{n,k}$. If
we have at least $2\ell$ occurences of $2$ among $T_{1},\dots,T_{\lfloor
n/2\rfloor}$, then we have at least $2\ell$ occurences of 2 among
$(T_{1},\dots,T_{k})$, and thus at least $2\ell$ occurences of 2 in $w_{k}$.
This implies that $n-|w_{k}|\geq 2\ell,$ meaning that when $w_{k}$ is written,
we know the lengths of at least $\ell$ empty blocks between position $|w_{k}|$
and position $n$. Similarly to the proof of Proposition 1, let us consider the
integer $k^{\prime}$ such that $X_{n}$ is given by $T_{k^{\prime}}$. We also
introduce $D=k-k^{\prime}$, as illustrated below (by definition,
$X_{|w_{k}|}=T_{k}$ and $X_{n}=T_{k^{\prime}}$):

$\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{$\times\times\times\times\times\times\times\times$}\kern
1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\
\underset{X_{|w_{k}|}}{\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{$\times$}\kern 1.49994pt}\kern
1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}}\
\underbrace{\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\
\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\
\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\
\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}}_{\text{$D-1$
blocks}}\ \underset{X_{n}}{\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}}.$

By the above observations, we have

$\displaystyle\mathbb{P}(D<\ell)$ $\displaystyle\leq\mathbb{P}(\\{\mbox{ less
that $2\ell$ occurences of $2$ among $T_{1},\dots,T_{\lfloor n/2\rfloor}$
}\\}),$

and the probability on the right goes to $0$ as $n$ goes to $\infty$.
Furthermore,

$\displaystyle\mathbb{P}(X_{n}=1\ |\ D\geq\ell)$ $\displaystyle=$
$\displaystyle\mathbb{P}(T_{k^{\prime}}=1\ |\ D\geq\ell)$ $\displaystyle=$
$\displaystyle\mathbb{P}(T_{k^{\prime}}=1\ |\
D\geq\ell\,\cap\,T_{k}=1)\times\mathbb{P}(T_{k}=1\ |\ D\geq\ell)$
$\displaystyle\quad+\;\mathbb{P}(T_{k^{\prime}}=1\ |\
D\geq\ell\,\cap\,T_{k}=2)\times\mathbb{P}(T_{k}=2\ |\ D\geq\ell)$
$\displaystyle\in\left[\frac{1}{2}(1-|1-2p|^{\ell});\;\frac{1}{2}(1+|1-2p|^{\ell})\right]$

thanks to the remark made at the beginning of the proof. We deduce that

$\underset{n\to\infty}{\limsup}\;\mathbb{P}(X_{n}=1)\leq\frac{1}{2}(1+|1-2p|^{\ell})\quad\mbox{
and
}\quad\underset{n\to\infty}{\liminf}\;\mathbb{P}(X_{n}=1)\geq\frac{1}{2}(1-|1-2p|^{\ell}).$

Then, by letting $\ell$ goes to infinity, we obtain
$\lim_{n\to\infty}\mathbb{P}(X_{n}=1)=\frac{1}{2}$. ∎

As a direct consequence of Theorem 3, we obtain the following result.

######  Corollary 2.

Let $p\in]0,1[$ and let $\mathbb{T}$ be a Markov chain over the alphabet
$\\{1,2\\}$ with initial value $T_{1}=1$ and whose transition probability from
1 to 2 (and from 2 to 1) is $p\in]0,1[$. Then

$\lim_{n\to\infty}\dfrac{\mathbb{E}(|X_{1}\dots X_{n}|_{1})}{n}=\dfrac{1}{2}$

We conjecture that the convergence also holds almost surely but we have been
unable to prove it so far, as the computation of the correlations is much more
intricate in the markovian case.

######  Conjecture 1.

Let $p\in]0,1[$ and let $\mathbb{T}$ be a Markov chain over the alphabet
$\\{1,2\\}$ with initial value $T_{1}=1$ and whose transition probability from
1 to 2 (and from 2 to 1) is $p\in]0,1[$. Then

$\lim_{n\to\infty}\dfrac{|X_{1}\dots X_{n}|_{1}}{n}=\dfrac{1}{2}\text{ almost
surely.}$

Observe that Theorem 3 and Corollary 2 easily extend to other alphabets. In
particular, one obtain an identical result over the alphabet $\\{1,3\\}$: if
$\mathbb{T}$ is a Markov chain with transition probability $0<p<1$ from 1 to 3
(and from 3 to 1), then the average density of $1$’s is $1/2$.

######  Theorem 4.

Let $a\geq 2$ be an integer, let $p\in]0,1[$ and let $\mathbb{T}$ be a Markov
chain over the alphabet $\\{1,a\\}$ with initial value $T_{1}=1$ and whose
transition probability from $1$ to $a$ (and from $a$ to $1$) is $p\in]0,1[$.
Then

$\displaystyle\lim_{n\to\infty}{\mathbb{P}(X_{n}=1)}=\dfrac{1}{2}\text{ and
}\lim_{n\to\infty}\dfrac{\mathbb{E}(|X_{1}\dots X_{n}|_{1})}{n}=\dfrac{1}{2}.$

The statement of Theorem 4 is somewhat surprising and unexpected since we know
that the densities $d_{1}$ and $d_{3}$ of the letters $1$ and $3$ in the
sequences $\mathcal{O}_{1,3}$ and $\mathcal{O}_{3,1}$ are respectively
$d_{1}\approx 0,40$ and $d_{3}\approx 0,60$. [1]. We will come back to this in
the discussion of Section 6.

##  5 Non conservation of the density

In previous sections, we have studied different cases where the directing
sequences are random. In all the cases we considered (sequences of independent
and identically distributed random variables, Markovian sequences), the
densities of letters of the directed sequence obtained are the same as those
in the directing sequence, almost surely.

Simulations also suggest that for any (infinite) periodic sequence $T$, the
density of $1$’s in directed sequence $\mathcal{O}_{T}$ is well-defined and is
equal to the density of $1$’s in $T$, see Figure 1.

Figure 1: Evolution of the density of $1$’s in increasingly large prefixes of
$\mathcal{O}_{T}$ for $T=(122)^{\omega}$ (left) and $T=(2112111)^{\omega}$
(right). The densities seem to converge respectively to $1/3$ and to $5/7$.

On Figure 1, we have chosen to represent only the data on short prefixes of
$\mathcal{O}_{T}$ so that it remains usable, especially to distinguish the
densities in the very first terms of the sequence $\mathcal{O}_{T}$. However,
further experiments have been carried out on a large number of periodic
sequences $T$ and they seem to corroborate our first impression, namely that
if the sequence $T$ is periodic then the densities in $\mathcal{O}_{T}$ would
be the same as those in $T$. This leads us to state the following conjecture,
that extends Keane’s conjecture.

######  Conjecture 2.

For any periodic sequence $T$ over the alphabet $\\{1,2\\}$, the density of
$1$’s in the directed sequence $\mathcal{O}_{T}$ is well-defined and is equal
to the density of $1$’s in $T$.

Then, a natural question arises: does there exist a directing sequence $T$
over $\\{1,2\\}$ for which the density of $1$’s in $T$ is not conserved in
$\mathcal{O}_{T}$? Obviously, because of Conjecture 2, we do not expect to
find such a candidate of directing sequence among the periodic ones.

However, we answer this question partially and positively thanks to the fact
that the left-to-right reading of $\mathcal{O}_{T}$ provides the size of the
blocks even further to the right (see Section 2). In a prospect of building
step by step both sequences $T$ and $\mathcal{O}_{T}$, the knowledge of the
length of not yet filled blocks of $\mathcal{O}_{T}$ could allow us to choose,
in a fully arbitrary way, with which letter we will fill them and it could
give us the opportunity to force the sequence $\mathcal{O}_{T}$ to contain
relatively more 1’s than the sequence $T$.

The main idea of our simultaneous construction scheme of $T$ and
$\mathcal{O}_{T}$ can be summarized as follows: we initialize $T_{1}$ to $2$,
then $\mathcal{O}_{T}=22\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}$ and from now on, by
reading $\mathcal{O}_{T}$ from left to right, we fill its blocks of size 2
with 1’s and its blocks of size 1 with 1’s and 2’s alternatively. The first
steps in the simultaneous construction of $T$ and $\mathcal{O}_{T}$ are thus
as follows (with the notation of Section 2):

  1. Step 1:

We set $\mathrm{T}^{(1)}=(2)$ and then
$\mathcal{O}^{(1)}=\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{22}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}$

  2. Step 2:

    1. (a)

The empty block of $\mathcal{O}^{(1)}$ of size $2$ must be filled with $1$’s:
$\mathcal{O}^{(2)}=\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{22}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{11}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}$

    2. (b)

We set $\mathrm{T}^{(2)}=(2,1)$

  3. Step 3:

    1. (a)

We fill the next block of $\mathcal{O}^{(2)}_{T}$ of size $1$ with $1$ :
$\mathcal{O}^{(3)}=\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{22}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{11}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{1}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}$

    2. (b)

Hence $\mathrm{T}^{(3)}=(2,1,1)$

  4. Step 4:

    1. (a)

We fill the next block of $\mathcal{O}^{(3)}_{T}$ of size $1$ with $2$ :
$\mathcal{O}^{(4)}=\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{22}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{11}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{1}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{2}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{?}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}\,\leavevmode\hbox{\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt\vtop{\hbox{\kern
1.49994pt\hbox{??}\kern 1.49994pt}\kern 1.43515pt\hrule}\kern-0.4pt\vrule
height=2.15277pt,width=0.4pt,depth=1.43515pt\kern-0.4pt}$

    2. (b)

Hence $\mathrm{T}^{(4)}=(2,1,1,2)$

  5. Step 5:

and son on…

For each $n\in\mathbb{N}^{\star}$, we have
$\mathcal{O}^{(n)}=\mathcal{O}_{\mathrm{T}^{(n)}}$. Moreover,
$\mathrm{T}^{(n)}$ is a prefix of $\mathrm{T}^{(n+1)}$ while
$\mathcal{O}^{(n)}$ is a prefix of $\mathcal{O}^{(n+1)}$, then we set
$T=\lim_{n\to\infty}{\mathrm{T}^{(n)}}$. It follows that
$\mathcal{O}_{T}=\lim_{n\to\infty}{\mathcal{O}^{(n)}}$.

Let us denote $T=(t_{i})_{i\in\mathbb{N}}$ and
$\mathcal{O}_{T}=(x_{i})_{i\in\mathbb{N}}$ with $t_{i},x_{i}\in\\{1,2\\}$ for
all $i\in\mathbb{N}$, then:

  1. 1.

$\mathrm{T}^{(n)}=(t_{1},\dots,t_{n})$ and $|\mathrm{T}^{(n)}|=n$.

  2. 2.

$\mathcal{O}^{(n)}=(t_{i}^{x_{i}})_{i\in[\\![1,n]\\!]}$ and
$\mathcal{O}_{T}=(t_{i}^{x_{i}})_{i\in\mathbb{N^{\star}}}$.

  3. 3.

$|\mathrm{T}^{(n)}|_{1}=|x_{1}\dots x_{n}|_{2}-1+\dfrac{1}{2}|x_{1}\dots
x_{n}|_{1}+C_{n}$, with $C_{n}\in\\{0,1\\}$: indeed, the number of $1$’s in
$\mathrm{T}^{(n)}$ is equal to the sum of the number of blocks of size $2$ in
$\mathcal{O}^{(n)}$ (except the first block of $\mathcal{O}^{(n)}$ because of
the initialisation of $\mathcal{O}^{(1)}$) and half of the number of blocks of
size $1$ in $\mathcal{O}^{(n)}$. By construction, the number of blocks of size
$1$ (resp. of size $2$) in $\mathcal{O}^{(n)}$ is equal to the number of $1$’s
(resp. $2$’s) in $x_{1}\dots x_{n}$. The constant $C_{n}$ takes into account
the cases where $x_{n}=1$ and is the first letter of a block of size 2 in
$\mathcal{O}^{(n)}$.

Program 2 provides a Python function for the construction of $\mathcal{O}_{T}$
and $T$.

⬇

1 def Sequences(n) :

2 T = [2]

3 O_T = [2, 2]

4 d = 1 # digit to write in the next block of size 1

5 for i in range(1, n) :

6 if O_T[i] == 2 :

7 T += [1]

8 O_T += [1]*2

9 else :

10 T += [d]

11 O_T += [d]

12 d = 3-d

13 return (T, O_T)

Program 2: Python function for the simultaneous construction of $T$ and
$\mathcal{O}_{T}$.

######  Theorem 5.

Let $T=\lim_{n\to\infty}{\mathrm{T}^{(n)}}$. The following properties hold:

  1. 1.

If the density $d^{T}_{1}$ of $1$’s in $T$ exists, then
$d^{T}_{1}={1+\sqrt{17}\over 8}=0.640\ldots$,
$d_{1}^{\mathcal{O}}={7-\sqrt{17}\over 4}=0.719\ldots$ and so $d^{T}_{1}\neq
d^{\mathcal{O}}_{1}$.

  2. 2.

If the density $d^{T}_{1}$ of $1$’s in $T$ exists, then the sequences $T$ and
$\mathcal{O}_{T}$ are not periodic.

###### Proof.

  1. 1.

For each $n\in\mathbb{N}^{\star}$, we have:

$\Big{|}\;|\mathcal{O}^{(n)}|_{1}-|{\mathrm{T}^{(n)}}|_{2}-2(|{\mathrm{T}^{(n)}}|_{1}-|{\mathrm{T}^{(n)}}|_{2})\;\Big{|}\leq
1$

Indeed, to within one unit, each digit $2$ of ${\mathrm{T}^{(n)}}$ gives rise
to a single $2$ in $\mathcal{O}^{(n)}$, and a same quantity
$|{\mathrm{T}^{(n)}}|_{2}$ of $1$’s gives rise to a single $1$ in
$\mathcal{O}^{(n)}$, while the rest of them (so
$|{\mathrm{T}^{(n)}}|_{1}-|{\mathrm{T}^{(n)}}|_{2}$) give rise to two $1$’s in
$\mathcal{O}^{(n)}$. Moreover the first $2$ of ${\mathrm{T}^{(n)}}$ is the
only one to be written twice in $\mathcal{O}^{(n)}$, so that we always have
exactly $|\mathcal{O}^{(n)}|_{2}=|{\mathrm{T}^{(n)}}|_{2}+1$. Then,

$\displaystyle\dfrac{|\mathcal{O}^{(n)}|_{1}}{|\mathcal{O}^{(n)}|}$
$\displaystyle=$
$\displaystyle\dfrac{|\mathcal{O}^{(n)}|_{1}}{|\mathcal{O}^{(n)}|_{1}+|\mathcal{O}^{(n)}|_{2}}=\dfrac{2|T^{(n)}|_{1}-|T^{(n)}|_{2}+o(n)}{-1+|T^{(n)}|_{2}+2(|T^{(n)}|_{1}-|T^{(n)}|_{2})+|T^{(n)}|_{2}+1+o(n))}$
$\displaystyle=$
$\displaystyle\dfrac{3|T^{(n)}|_{1}-|T^{(n)}|+o(n)}{2|T^{(n)}|_{1}+o(n)}\underset{n\to\infty}{\longrightarrow}\dfrac{3d^{T}_{1}-1}{2d^{T}_{1}}$

We conclude that

$d^{\mathcal{O}}_{1}=\dfrac{3d^{T}_{1}-1}{2d^{T}_{1}}$ (23)

and the density of $1$’s (resp. of $2$’s) in $\mathcal{O}_{T}$ exists.

We noticed above that, for each $n\in\mathbb{N}^{\star}$,
$|\mathrm{T}^{(n)}|_{1}=|x_{1}\dots x_{n}|_{2}-1+\dfrac{1}{2}|x_{1}\dots
x_{n}|_{1}+C_{n}$, with $C_{n}\in\\{0,1\\}$. Moreover, if $d^{T}_{1}$ exists
then so do $d^{O}_{1}$ and $d^{O}_{2}$ and, by tending $n$ towards infinity,
we have:

$d^{T}_{1}=d^{O}_{2}+\dfrac{1}{2}d^{O}_{1}$ (24)

By putting together equations (23) and (24), we deduce
$d_{1}^{T}={1+\sqrt{17}\over 8}$ and $d_{1}^{\mathcal{O}}={7-\sqrt{17}\over
4}$.

  2. 2.

If the sequences $T$ and $\mathcal{O}_{T}$ were periodic, then their densities
of $1$’s and $2$’s would be rational, which is not the case.

∎

Simulations suggest that the densities are indeed converging to these values,
see Figure 2.

Figure 2: Evolution of the densities of $1$’s in $\mathcal{O}_{T}$ (blue) and
$T$ (black), where the two sequences are defined by Program 2.

##  6 Conclusion and discussion

Over the alphabet $\\{1,a\\}$, with $a\in\\{2,3\\}$, we have shown that in
almost all the sequences directed by an infinite sequence
$\mathbb{T}=(T_{n})_{n\in\mathbb{N}^{\star}}$ of i.i.d. random variables with
$\mathbb{P}(T_{n}=1)=p\in]0,1[$ and $\mathbb{P}(T_{n}=a)=1-p$, the density of
$1$’s is equal to $p$. We have also shown that the average density of $1$’s
among all sequences directed by a Markov chain with transition probability
$p\in]0,1[$ from $1$ to $a$ and from $a$ to 1 is equal to $1/2$.

Keane’s conjecture [9] states that this result can be extended to the
deterministic case, namely when $p=1$, over the alphabet $\\{1,2\\}$. On the
other hand, over the alphabet $\\{1,3\\}$ this result is not extendable to the
deterministic case since the density of $1$’s in $\mathcal{O}_{1,3}$ is close
to 0.3972. [1].

When $\mathbb{T}$ is a Markov chain, the closer its transition probability $p$
is to $1$, the more likely the sequence $\mathcal{O}_{T}$ is to share a long
prefix with $\mathcal{O}_{1,3}$. Therefore, the closer the transition
probability $p$ is to 1, the closer the density of 1’s in the sequence
$\mathcal{O}_{T}$ is to that in the sequence $\mathcal{O}_{1,3}$ on a long
prefix. However, computer experiments suggest that when the first
perturbations in the alternation of 1’s and 3’s appear in $\mathbb{T}$, the
density of $1$’s in the prefix of $\mathcal{O}_{\mathbb{T}}$ eventually
approaches 0.5 as this prefix gets longer. See Figure 3 for an illustration
with $p=0.99$.

Figure 3: Evolution of the frequency of $1$’s for a markovian directing
sequence on the alphabet $\\{1,3\\}$ of parameter $p=0.99$: the frequency is
first close to the one of $\mathcal{O}_{1,3}$ then moves away from it to
converge to $1/2$.

This implies it seems difficult to derive information about the original
Oldenburger-Kolakoski sequence $\mathcal{O}_{1,2}$ by letting $p$ tend to $1$
in the Markovian case over the alphabet $\\{1,2\\}$.

Finally, the study of sequences directed by random sequences on alphabets of
more than 2 letters or by random sequences constructed from other
distributions also seems interesting.

## References

  * [1] Michael Baake and Bernd Sing.  Kolakoski-(3, 1) is a (deformed) model set.  Canadian Mathematical Bulletin, 47(2):168–190, 2004.
  * [2] Valérie Berthé, Srecko Brlek, and Philippe Choquette.  Smooth words over arbitrary alphabets.  Theor. Comput. Sci., 341(1-3):293–310, 2005.
  * [3] Valérie Berthé, Srecko Brlek, and Philippe Choquette.  Smooth words over arbitrary alphabets.  Theor. Comput. Sci., 341(1-3):293–310, 2005.
  * [4] Srecko Brlek, Serge Dulucq, A. Ladouceur, and Laurent Vuillon.  Combinatorial properties of smooth infinite words.  Theor. Comput. Sci., 352(1-3):306–317, 2006.
  * [5] Srecko Brlek, Damien Jamet, and Geneviève Paquin.  Smooth words on 2-letter alphabets having same parity.  Theor. Comput. Sci., 393(1-3):166–181, 2008.
  * [6] Arturo Carpi.  Repetitions in the Kolakovski sequence.  Bull. EATCS, 50:194–197, 1993.
  * [7] Vašek Chvátal.  Notes on the Kolakoski sequence.  Technical report, DIMACS Technical Report 93-84, December 1993.
  * [8] F. M. Dekking.  On the structure of selfgenerating sequences.  Séminaire de Théorie des Nombres de Bordeaux, pages 1–6, 1980\.
  * [9] Michael S. Keane.  Ergodic theory and subshifts of finite type.  In Ergodic theory, symbolic dynamics, and hyperbolic spaces. Lectures given at the workshop "Hyperbolic geometry and ergodic theory", held at the International Centre for Theoretical Physics in Trieste, Italy, 17-28 April, 1989, pages 35–70. Oxford etc.: Oxford University Press, 1991.
  * [10] William Kolakoski.  Self-generating runs, problem 5304.  The American Mathematical Monthly, 73(6):681–682, 1966.
  * [11] Russell Lyons.  Strong laws of large numbers for weakly correlated random variables.  Michigan Mathematical Journal, 35(3):353 – 359, 1988.
  * [12] Rufus Oldenburger.  Exponent trajectories in symbolic dynamics.  Transactions of the American Mathematical Society, 46(3):453–466, 1939.
  * [13] Bernd Sing.  More Kolakoski sequences.  Integers, 11B:A14, 2011.