# Coupling results and Markovian structures for number representations of
continuous random variables

J. Møller

###### Abstract

A general setting for nested subdivisions of a bounded real set into intervals
defining the digits $X_{1},X_{2},...$ of a random variable $X$ with a
probability density function $f$ is considered. Under the weak condition that
$f$ is almost everywhere lower semi-continuous, a coupling between $X$ and a
non-negative integer-valued random variable $N$ is established so that
$X_{1},...,X_{N}$ have an interpretation as the “sufficient digits”, since the
distribution of $R=(X_{N+1},X_{N+2},...)$ conditioned on $S=(X_{1},...,X_{N})$
does not depend on $f$. Adding a condition about a Markovian structure of the
lengths of the intervals in the nested subdivisions, $R\,|\,S$ becomes a
Markov chain of a certain order $s\geq 0$. If $s=0$ then $X_{N+1},X_{N+2},...$
are IID with a known distribution. When $s>0$ and the Markov chain is
uniformly geometric ergodic, a coupling is established between $(X,N)$ and a
random time $M$ so that the chain after time $\max\\{N,s\\}+M-s$ is stationary
and $M$ follows a simple known distribution. The results are related to
several examples of number representations generated by a dynamical system,
including base-$q$ expansions, generalized Lüroth series, $\beta$-expansions,
and continued fraction representations. The importance of the results and some
suggestions and open problems for future research are discussed.

Keywords:  Approximation; beta-expansion; continued fraction; dynamical
system; Lüroth series; Markov chain; nested partitions; pseudo golden ratio;
read once algorithm; sufficient digits.

##  1 Introduction

Let $X$ be a continuous random variable with digit expansion
$X=0.X_{1}X_{2}...$ in the usual decimal numeral system (base-10) or another
numeral system as described below. This paper shows that under very mild
conditions, a non-negative integer-valued random variable $N$ exists so that
$S=(X_{1},...,X_{N})$ are the “sufficient digits” in the sense that the
distribution of $R=(X_{N+1},X_{N+2},...)$ conditioned on $S=(X_{1},...,X_{N})$
does not depend on the distribution of $X$. Under a further condition ensuring
a Markovian structure of the numeral system, which is satisfied for base-10
and many other other numeral systems, it is also shown that $R\,|\,S$ is a
Markov chain of a certain order $s\geq 0$. When $s=0$, which e.g. is satisfied
for base-10, $X_{N+1},X_{N+2},...$ are shown to be IID with a known
distribution. When $s>0$ and the Markov chain is uniformly geometric ergodic,
a coupling is established between $(X,N)$ and a random time $M$ so that the
chain after time $\max\\{N,s\\}+M-s$ is stationary and $M$ follows a simple
known distribution. Before further presenting these results and the outline of
this paper, the background material on numeral systems presented in Section
1.1 is needed. The importance of the results are wide ranging as discussed
Section 5.

###  1.1 Nested subdivisions

The general setting of nested subdivisions described in this section is
considered throughout the text. Specific constructions and examples are given
in Section 2.

Let $\mathcal{X}$ be a finite or countable set, and denote
$\mathbb{R},\mathbb{N},$ and $\mathbb{N}_{0}$ the sets of real numbers,
positive integers, and non-negative integers, respectively, and
$\mathcal{X}^{\mathbb{N}}$ the set of all sequences $(x_{1},x_{2},...)$ with
elements in $\mathcal{X}$.

Suppose $I=I_{\emptyset}\subset\mathbb{R}$ is a Borel set of Lebesgue measure
$\ell_{\emptyset}=|I|\in(0,\infty)$ and for every $n\in\mathbb{N}$ there is a
subdivision (at level $n$)

$I=\bigcup_{(x_{1},...,x_{n})\in\mathcal{X}^{n}}I_{x_{1},...,x_{n}}\bigcup
D_{n}$ (1)

such the following properties are satisfied. The $I_{x_{1},...,x_{n}}$’s and
$D_{n}$ are pairwise disjoint sets. Each $I_{k}$ with $k\in\mathcal{X}$ is an
open non-empty interval, and for $n>1$, $I_{x_{1},...,x_{n}}$ is an open and
possibly empty interval such that $I_{x_{1},...,x_{n}}\subseteq
I_{x_{1},...,x_{n-1}}$. Each $D_{n}$ is a subset of the endpoints of the non-
empty $I_{x_{1},...,x_{n}}$’s.

Some comments, further notation, and one more assumption are in order.

When $n\geq 2$, $I_{x_{1},...,x_{n}}$ is allowed to be empty, since
restrictions on the digits may be needed in some cases (e.g. Example 2.2
below).

Let $D=\cup_{n=1}^{\infty}D_{n}$ be the set of all endpoints. Since each
$D_{n}$ is finite or countable, $D$ is finite or countable, and so $|D|=0$.

It is only for convenience that each interval $I_{x_{1},...,x_{n}}$ is assumed
to be open. The assumption is of no importance for the probabilistic results
in this paper, since $|D|=0$ and all considered probability distributions on
$I$ will be assumed to be absolutely continuous. Therefore, ignoring Lebesgue
nullsets, the partitions given by (1) for $n=1,2,...$ are said to be nested
subdivisions of $I$.

Let $J=I\setminus D$. Then $|I|=|J|$. Since $D$ and
$\cap_{n=1}^{\infty}\cup_{(x_{1},...,x_{n})\in\mathcal{X}^{n}}I_{x_{1},...,x_{n}}$
are disjoint, $J$ is the limit of the right hand side of (1), i.e.,

$J=\bigcap_{n=1}^{\infty}\bigcup_{(x_{1},...,x_{n})\in\mathcal{X}^{n}}I_{x_{1},...,x_{n}}.$

For every $(x_{1},x_{2},...)\in\mathcal{X}^{\mathbb{N}}$ and $n\in\mathbb{N}$,
let $\ell_{x_{1},...,x_{n}}=|I_{x_{1},...,x_{n}}|$ be the length of
$I_{x_{1},...,x_{n}}$ and assume

$\ell_{x_{1},...,x_{n}}\to 0\quad\mbox{as }n\to\infty.$ (2)

Denote $a_{x_{1},...,x_{n}}$ the left endpoint of $I_{x_{1},...,x_{n}}$. For
$x\in I_{x_{1},...,x_{n}}$, the error $e_{n}(x)$ and the relative error
$u_{n}(x)$ of the approximation $x\approx a_{x_{1},...,x_{n}}$ as compared to
$\ell_{x_{1},...,x_{n}}$ are defined by

$e_{n}(x)=x-a_{x_{1},...,x_{n}},\quad
u_{n}(x)=e_{n}(x)/\ell_{x_{1},...,x_{n}}.$

By (2), $e_{n}(x)\to 0$ as $n\to\infty$. If $x\in J$ then $0<u_{n}(x)<1$.

Define the digits (or coefficients or symbols) of every $x\in J$ as the unique
sequence $(x_{1},x_{2},...)\in\mathcal{X}^{\mathbb{N}}$ such that $x\in
I_{x_{1},...,x_{n}}$ for $n=1,2,...$. The assumption (2) means that
$x=\lim_{n\to\infty}a_{x_{1},...,x_{n}}$ is determined by its digits. Express
this one-to-one correspondence between $x\in J$ and its digits by writing

$x=.x_{1}x_{2}...\quad\mbox{for $x\in J$}.$ (3)

For $n\in\mathbb{N}_{0}$ and $x\in J$, call $x^{[n]}=.x_{n+1}x_{n+2}...$ and
$x_{>n}=(x_{n+1},x_{n+2},...)$ the $n$-th (scaled) remainder of $x$ and the
$n$-th tail of $x$, respectively, where $x^{[0]}=x$. Let
$J_{>0}=\\{x_{>0}\,|\,x\in J\\}$. Then, for any fixed $n\in\mathbb{N}_{0}$,
there is a one-to-one correspondence between $x^{[n]}\in J$ and $x_{>n}\in
J_{>0}$.

###  1.2 Objective and main results

Let $X$ be a random variable with values in $J$ and a probability density
function (PDF) $f$ concentrated on $J$. Denote its digits by
$X=0.X_{1}X_{2}...$, cf. (3). Then $(X_{1},X_{2},...)$ is a stochastic process
with state space $\mathcal{X}$. For $n\in\mathbb{N}$, writing
$A_{n}=a_{X_{1},...,X_{n}}$ and $L_{n}=\ell_{X_{1},...,X_{n}}$, then
$A_{n}<X<A_{n}+L_{n}$ and $L_{n}\to 0$. The aim of this paper is to show how
coupling methods can be used for establishing a number of interesting results
for the distribution of

$X^{[n]}=.{X_{n+1}X_{n+2}...}\quad\mbox{or equivalently}\quad
X_{>n}=(X_{n+1},X_{n+2},...),$ (4)

the distributions of

$E_{n}=e_{n}(X)=X-A_{n}\quad\mbox{and}\quad U_{n}=u_{n}(X)=E_{n}/L_{n},$ (5)

and the distributions of further stochastic variables/processes obtained when
$n\in\mathbb{N}_{0}$ in (4) and (5) is replaced by a random time obtained from
one of the various coupling constructions studied in detail in Sections 3 and
4. These distributions are of interest when considering number representations
of $X$ as in Section 2.3 below as well as many other examples (see [23, 6, 5,
11, 13] and the references therein).

The weak condition (6) below is used when establishing any result in Sections
3 and 4. Recall that lower semi-continuity (LSC) of $f$ at a point $x\in I$
means $\lim\inf_{{x_{n}\to x}}f(x_{n})\geq f(x)$ for any sequence of points
$x_{n}$ converging to $x$. Commonly used PDFs are LSC almost everywhere.
Consider the condition that

$f$ is LSC on a Borel set $H\subseteq J$ where $|J\setminus H|=0$ (6)

(hence $|I\setminus H|=0$). This is indeed a very mild condition – for an
example where it is violated, see Remark 1 in [12].

Assuming (6), there is a useful coupling between $X$ and a non-negative
integer-valued random variable $N$. The coupling construction is detailed in
Theorem 3.1, which is summarized below using the following notation. If $n=0$,
interpret $(x_{1},...,x_{n})$ as the “empty sequence of digits”, which is
denoted $\emptyset$, and set $\mathcal{X}^{0}=\\{\emptyset\\}$ (this notation
is similar to the use of $\emptyset$ for the empty point configuration in
connection to finite point processes [20]). Define

$S=(X_{1},...,X_{N})$ (7)

which becomes a discrete random variable with state space
$\cup_{n=0}^{\infty}\mathcal{X}^{n}$, the set of all finite sequences of
digits including the case of no digits. For $\ell>0$, denote
$\mathrm{Unif}(0,\ell)$ and $\mathrm{Unif}(I)$ the uniform distribution on
$(0,\ell)$ and $I$, respectively. For mathematical convenience, introduce two
random variables $E_{0}$ and $U_{0}$ such that conditioned on $N=0$,
$S\perp\\!\\!\\!\perp E_{0}\sim\mathrm{Unif}(0,\ell_{\emptyset})$ and
$S\perp\\!\\!\\!\perp U_{0}\sim\mathrm{Unif}(0,1)$ where $\perp\\!\\!\\!\perp$
means independence. Define

$E=E_{N},\quad U=U_{N}=E/L\quad\mbox{where }L=\begin{cases}\ell_{N}&\text{ if
}N>0\\\ \ell_{\emptyset}&\text{ if }N=0.\end{cases}$ (8)

Finally, define the residual process by $R=X_{>N}$, i.e.,

$R=(R_{1},R_{2},...)=(X_{N+1},X_{N+2},...).$ (9)

Then $(X,N)$ and $(S,U)$ are in a one-to-one correspondence.

Among other things Theorem 3.1 states that $S\perp\\!\\!\\!\perp
U\sim\mathrm{Unif}(0,1)$; conditioned on $L$, one has $S\perp\\!\\!\\!\perp
E\sim\mathrm{Unif}(0,L)$; and the conditional distribution of $R\,|\,S$ does
not depend on $f$ but is expressible in terms of ratios between the lengths of
the intervals in the nested subdivisions. These results extend those in [11]
which only considered the special case of base-$q$ expansions (with $q>1$ an
integer, cf. Example 2.1 below; see also [3, 4]).

The results in Section 3 are expanded in Section 4, assuming the lengths of
the intervals in the nested subdivisions of $I$ exhibit the following
structure. Set $0/0=0$ and for a given $s\in\mathbb{N}_{0}$, assume that for
any integer $n\geq s+1$ and every $(x_{1},...,x_{n})\in\mathcal{X}^{n}$, the
ratio $\ell_{x_{1},...,x_{n}}/\ell_{x_{1},...,x_{n-1}}$ depends only on
$(x_{n-s},...,x_{n})$, which is written as

$\ell_{x_{1},...,x_{n}}/\ell_{x_{1},...,x_{n-1}}=p_{x_{n-s},...,x_{n}}.$ (10)

Then the lengths of the intervals are said to exhibit a Markovian structure of
order $s$ because $R\,|\,S$ turns out to be a Markov chain of order $s$ as
explained below.

The special case $s=0$ is treated in Section 3.2, where it is shown that
$X_{1},X_{2},...$ are independent identically distributed (IID) with a known
distribution. Suppose $s>0$. Define

$\Omega=\\{(x_{1},...,x_{s})\in\mathcal{X}^{s}\,|\,\ell_{x_{1},...,x_{s}}>0\\}$
(11)

and a matrix $P$ with entries indexed by
$((x_{1},...,x_{s}),(y_{1},...,y_{s}))\in\Omega\times\Omega$ such that

$P_{(x_{1},...,x_{s}),(y_{1},...,y_{s})}=\begin{cases}p_{x_{1},...,x_{s},y_{s}}&\text{if
}y_{i}=x_{i+1}\text{ for }1\leq i<s\\\ 0&\text{otherwise.}\end{cases}$ (12)

For $i\in\mathbb{N}$, let $X^{(s)}_{i}=(X_{i},X_{i+1},...,X_{i+s-1})$ and
$R^{(s)}_{i}=X^{(s)}_{N+i}$, and for $m\in\mathbb{N}_{0}$, let

$\displaystyle X^{(s)}$ $\displaystyle=(X^{(s)}_{1},X^{(s)}_{2},...),\quad
X^{(s)}_{>m}=(X^{(s)}_{m+1},X^{(s)}_{m+1},...),$ (13) $\displaystyle R^{(s)}$
$\displaystyle=(R^{(s)}_{1},R^{(s)}_{2},...),\quad\,\,R^{(s)}_{>m}=(R^{(s)}_{m+1},R^{(s)}_{m+2},...),$
(14)

so $R^{(s)}=X^{(s)}_{>N+m}$. It is shown in Section 4.1 that $R^{(s)}\,|\,S$
is a Markov chain with transition matrix $P$. In particular, if the chain
$R^{(s)}\,|\,S$ is uniformly geometric ergodic, a coupling of $(X,N)$ with a
random time $M$ is established in Section 4.2 such that
$X^{(s)}_{>\max\\{N,s\\}+M-s}$ is stationary and $M$ is independent of the
chain and follows a simple known distribution. This coupling construction is
based on the read once algorithm for perfect simulation developed by Wilson
[25].

###  1.3 Outline

Section 2 discusses various procedures of constructing nested subdivisions and
presents examples used later on. The coupling construction between $X$ and $N$
and related results are given in Section 3. Under various conditions, Section
4 shows that $R^{(s)}\,|\,S$ is a Markov chain, specifies the coupling between
$(X,N)$ and $M$, and establishes related results. Section 5 concludes with a
brief discussion of the importance of the results and some open problems.

##  2 Procedures for nested subdivisions

Assuming the first subdivision of $I$ into the intervals
$I_{k}=(a_{k},a_{k}+\ell_{k})$ with $k\in\mathcal{X}$ is given, it is
explained in Section 2.1 how probability distributions and in Section 2.2 how
dynamical systems may be used to generate nested subdivisions of $I$. Various
illustrative examples are presented in Section 2.3, including generalized
Lüroth series, $\beta$-expansions, and continued fraction representations.

###  2.1 Markovian constructions

Given the subdivision of $I$ into the intervals $I_{k}=(a_{k},a_{k}+\ell_{k})$
with $k\in\mathcal{X}$, an integer $s\geq 0$, and a probability mass function
(PMF) on $\mathcal{X}^{m}$ with $m=s+1$, the following procedure is in
accordance with the Markovian structure in (10).

Consider first the case $s=0$ and define a PMF by
$p_{k}=\ell_{k}/\ell_{\emptyset}$ for all $k\in\mathcal{X}$. In accordance
with (10), for each $(x_{1},...,x_{n})\in\mathcal{X}^{n}$ with
$n\in\mathbb{N}$, let $\ell_{x_{1},...,x_{n}}=p_{x_{1}}\cdots
p_{x_{n}}\ell_{\emptyset}$. Recursively, for $n=1,2,...$, assuming
$a_{x_{1},...,x_{n}}$ has been specified, let the subdivision of
$I_{x_{1},...,x_{n}}$ into the intervals $I_{x_{1},...,x_{n},k}$ with
$k\in\mathcal{X}$ be such that $a_{x_{1},...,x_{n},j}<a_{x_{1},...,x_{n},k}$
if $a_{j}<a_{k}$. This ordering is such that the corresponding
$\ell_{x_{1},...,x_{n},k}$’s are proportional to the $\ell_{k}$’s (the lengths
of the intervals in the first subdivision of $I$). Of course another ordering
could have been used as well.

Consider next the case $s>1$. Let $p_{k}$ be as above and for
$(x_{1},...,x_{n+1})\in\mathcal{X}^{n+1}$ with $1\leq n\leq s$, suppose
$p_{x_{1},...,x_{n},x_{n+1}}$ is a PMF with respect to $x_{n+1}\in\mathcal{X}$
such that $p_{x_{1}}\cdots p_{x_{1},...,x_{m}}$ becomes a PMF with respect to
$(x_{1},...,x_{m})\in\mathcal{X}^{m}$. For
$(x_{1},...,x_{n+1})\in\mathcal{X}^{n+1}$ with $n\in\mathbb{N}$, let

$\ell_{x_{1},...,x_{n+1}}=\ell_{x_{1},...,x_{n}}\times\begin{cases}p_{x_{1},...,x_{n},x_{n+1}}&\text{if
}n\leq s\\\ p_{x_{n-s+1},...,x_{n},x_{n+1}}&\text{if }n>s.\end{cases}$

If $\ell_{x_{1},...,x_{n}}>0$, specify the left endpoints of the intervals in
the subdivision of $I_{x_{1},...,x_{n}}$ as above, i.e.,
$a_{x_{1},...,x_{n},j}<a_{x_{1},...,x_{n},k}$ if $a_{j}<a_{k}$. Thus (10) is
satisfied and the nested subdivisions of $I$ are specified such that the
ordering of the intervals at the first level is reused for the intervals in
the subdivision of any interval at a later level.

###  2.2 Dynamical systems

A common way to construct nested partitions is by using a dynamical system as
follows (see also [23, 6, 5]). Let $T:I\mapsto I$ be a function and
$I=\cup_{k\in\mathcal{X}}\tilde{I}_{k}$ a countable partition such that for
each $k\in\mathcal{X}$, $\tilde{I}_{k}$ is a bounded interval of length
$\ell_{k}>0$ and the restriction of $T$ to $\tilde{I}_{k}$ is a strictly
monotone function which is denoted $T_{k}$. For $n=1,2,...$, let
$T^{n}(x)=T(T^{n-1}(x))$ be the state of the dynamical system at time $n$ when
it is started at $T^{0}(x)=x$, and let the $n$-th digit of $x$ be $x_{n}=k$ if
$T^{n}(x)\in\tilde{I}_{k}$. For every $(x_{1},...,x_{n})\in\mathcal{X}^{n}$
with $n\in\mathbb{N}$, define

$\tilde{I}_{x_{1},...,x_{n}}=\\{x\in
I\,|\,T^{i-1}(x)\in\tilde{I}_{x_{i}},i=1,...,n\\}$

which by induction is seen to be a bounded interval, and let

$I_{x_{1},...,x_{n}}$ agree with $\tilde{I}_{x_{1},...,x_{n}}$ if the
endpoints of $\tilde{I}_{x_{1},...,x_{n}}$ are excluded. (15)

As mentioned in Section 1.1, it is of no importance for the results in this
paper but only for convenience that the endpoints are excluded. In the
dynamical system literature, $\tilde{I}_{x_{1},...,x_{n}}$ is called a
cylinder.

Henceforth, “a setting for a dynamical system” refers to a situation where a
dynamical system as above is given such that (3) holds and each
$I_{x_{1},...,x_{n}}$ is specified by (15). By induction, if
$x=.x_{1}x_{2}...\in J$, then $x^{[n]}=T^{n}(x)\in J$ for $n=0,1,...$. Thus,
since $X\in J$,

$X^{[n]}=T^{n}(X)\in J\quad\mbox{for }n=0,1,...$

Moreover, if each $T_{k}$ is a diffeomorphism on $I_{k}$ except for a Lebesgue
nullset, then for every $n\in\mathbb{N}_{0}$, the distribution of $X^{[n]}$ is
absolutely continuous and has a PDF on $J$ which for almost all
$x=.x_{1}x_{2}...\in J$ is given by

$f^{[n]}(x)=\sum_{(k_{1},...,k_{n})\in\mathcal{X}^{n}:\,\ell_{k_{1},...,k_{n}}>0}{f\left(.k_{1}...k_{n}x_{1}x_{2}...\right)}\left|\left(T_{k_{1}}^{-1}\circ\cdots\circ
T_{k_{n}}^{-1}\right)^{\prime}(x)\right|$ (16)

This follows from the transformation theorem of densities by considering each
case of $X\in I_{k_{1},...,k_{n}}$, and since $T_{k_{1}}^{-1}\circ\cdots\circ
T_{k_{n}}^{-1}(x)=.k_{1}...k_{n}x_{1}x_{2}...$.

By definition, the process $X_{>0}=(X_{1},X_{2},...)$ is stationary if and
only if $X_{>0}$ and $X_{>1}$ are identically distributed, which in the
present setting can be reformulated: Stationarity is equivalent to that
$X=0.X_{1}X_{2}...\sim f$ implies $X^{[1]}=0.X_{2}X_{3}....\sim f$, and for
short $f$ is then said to be shift invariant. In the metric number theory
literature (e.g. [5, 6, 23]), a distribution $\mu$ on $(I,\mathcal{B})$ is
said to be $T$-invariant if $\mu(A)=\mu(T^{-1}(A))$ for all $A\in\mathcal{B}$.
Then $\mu$ being absolutely continuous and $T$-invariant corresponds to that
$f$ is shift invariant.

###  2.3 Examples

Using the approach in Section 2.1, it may not always be obvious to see if the
nested subdivisions could also be constructed using a setting for a dynamical
system as in Section 2.2 – an exception is the case $s=0$ which is treated in
Example 2.1 below. On the other hand, many examples of important number
representations are generated by a dynamical system, and they are not all of
the ‘Markovian type’. A few examples are summarised in this section and used
for illustrative purposes later on in the text. Further examples can be found
in e.g. [23, 6, 5].

In the following Examples 2.1–2.3, first a dynamical system is specified and
second it is understood that nested partitions are constructed as in Section
2.2.

######  Example 2.1.

Suppose that $I$ agrees with $[0,1]$ perhaps except at 0 or 1, and a dynamical
system is given such that (3) holds and for every $k\in\mathcal{X}$, the map
$T_{k}$ restricted to $I_{k}$ is a linear bijection into $(0,1)$ with slope
$t_{k}/\ell_{k}$ where $t_{k}\in\\{\pm 1\\}$. This is the setting for a
generalized Lüroth series (GLS), cf. [2]. Since the signs $t_{k}$ can vary, it
is convenient that it is not needed in the present paper to specify whether
$I$ and $\tilde{I}_{k}$ include or not each of their endpoints. Note that
$T_{x_{n}}\circ\ldots\circ T_{x_{1}}$ restricted to $I_{x_{1},...,x_{n}}$ is a
linear bijection $I_{x_{1},...,x_{n}}\mapsto(0,1)$ with slope
$(t_{x_{1}}/\ell_{x_{1}})\cdots(t_{x_{n}}/\ell_{x_{n}})$. Thus,

$\ell_{x_{1},...,x_{n}}=\ell_{x_{1}}\cdots\ell_{x_{n}}\quad\mbox{for all
}(x_{1},...,x_{n})\in\mathcal{X}^{n},$

and so the Markovian structure in (10) is satisfied when $s=0$. Moreover, the
left endpoints of the intervals in the subdivision of $I_{x_{1},...,x_{n}}$
are ordered in the same way as in Section 2.1 if $t_{x_{1}}\cdots
t_{x_{n}}=1$, and in the reverse order if $t_{x_{1}}\cdots t_{x_{n}}=-1$
(i.e., $a_{x_{1},...,x_{n},j}>a_{x_{1},...,x_{n},k}$ if $a_{j}<a_{k}$).
Consequently, if $t_{k}=1$ for all $k\in\mathcal{X}$, the construction from
Section 2.1 results in the same nested partitions, and the construction can be
modified so that it works in any case: For the subdivision of
$I_{x_{1},...,x_{n}}$, use the same procedure as in Section 2.1 except if
$t_{x_{1}}\cdots t_{x_{n}}=-1$, in which case the left endpoints should appear
in the reverse order.

One important and well-known case occurs when $q\geq 2$ is an integer,
$I=[0,1)$, $\mathcal{X}=\\{0,1,...,q-1\\}$, and for each $k\in\mathcal{X}$,
$\tilde{I}_{k}=[k/q,(k+1)/q)$ and $T_{k}(x)=qx-k$. Then every $x\in[0,1)$ has
a base-$q$ expansion

$x=\sum_{i=1}^{\infty}x_{i}q^{-i}\quad\mbox{with }x_{i}=\lfloor
qT^{i-1}(x)\rfloor,\ i=1,2,...,$ (17)

and $J$ is the set of those $x$ where the sum is not finite and there exists
no $n\in\mathbb{N}$ so that $x_{n}=x_{n+1}=....=q-1$. Here, $\lfloor a\rfloor$
is the integer part of $a\geq 0$. Moreover,
$a_{x_{1},...,x_{n}}=\sum_{i=1}^{n}x_{i}q^{-i}$,
$\ell_{x_{1},...,x_{n}}=q^{-n}$, and
$T^{n}(x)=\sum_{i=1}^{\infty}x_{i+n}q^{-i}$.

Another special case is an ‘original’ Lüroth series where $I=(0,1)$ and
$\mathcal{X}=\\{2,3,...\\}$, and where Lüroth [18] showed that any $x\in(0,1)$
has a series

$x=\frac{1}{x_{1}}+\frac{1}{x_{1}(x_{1}-1)x_{2}}+...+\frac{1}{x_{1}(x_{1}-1)\cdots
x_{n-1}(x_{n-1}-1)x_{n}}+...$ (18)

with $(x_{1},x_{2},...)\in\mathcal{X}^{\mathbb{N}}$ (sometimes in the
literature, e.g. in [6], 0 is included into $I$ but again this is of no
importance for the present paper). Defining for each $k\in\mathcal{X}$,
$\tilde{I}_{k}=[1/k,1/(k-1))$ and $T_{k}(x)=(k-1)kx-k+1$, it turns out that
each digit $x_{n}$ is uniquely given by $x_{n}=k$ if $1/k<T^{n}(x)<1/(k-1)$
(expressions of $T^{n}(x)$ and technical details for the case $T^{n}(x)=1/k$
are given in [6]; fortunately this case can be ignored in the present paper).
It follows that $J$ is the set of those $x$ where the sum in (18) is not
finite.

######  Example 2.2.

Let $\beta>1$, $I=[0,1)$, and $T(x)=\beta x-\lfloor\beta x\rfloor$. If
$\beta=q\in\\{2,3,...\\}$, then define $\mathcal{X}$ as in the case of the
base-$q$ expansion above. Else let
$\mathcal{X}=\\{0,1,...,\lfloor\beta\rfloor\\}$,
$\tilde{I}_{k}=[k/\beta,(k+1)/\beta)$ if $0\leq k<\lfloor\beta\rfloor$, and
$\tilde{I}_{\lfloor\beta\rfloor}=[\lfloor\beta\rfloor/\beta,1)$. Rényi [22]
showed that every $x\in[0,1)$ has a so-called $\beta$-expansion

$x=\sum_{i=1}^{\infty}x_{i}\beta^{-i}\quad\mbox{with }x_{i}=\lfloor\beta
T^{i-1}(x)\rfloor,\ i=1,2,...$ (19)

which of course agrees with (17) when $\beta\in\\{2,3,...\\}$. The convergence
of the series in (19) implies that (3) holds.

Denote the set of all admissible sequences by

$\mathcal{A}_{\beta}=\\{(\lfloor\beta T^{0}(x)\rfloor,\lfloor\beta
T^{1}(x)\rfloor,...)\,|\,0\leq x<1\\},$

referring to [21, 6] for the detailed description of $\mathcal{A}_{\beta}$.
Clearly, $J_{>0}\subset\mathcal{A}_{\beta}$. For instance, if
$\beta=q\in\\{2,3,...\\}$, then $A_{\beta}=\mathcal{X}^{\mathbb{N}}$ and
$\mathcal{A}_{\beta}\setminus J_{>0}$ is the set of base-$q$ fractions, i.e.,
numbers $x$ where the sum in (17) is finite.

Another tractable case is the following. Let $s\in\mathbb{N}$, $m=s+1$, and
$\beta=\beta_{m}>1$ be the pseudo golden mean of order $m$, that is, the
positive root of $z^{m}-z^{m-1}-...-z-1=0$. Then
$\beta_{2}<\beta_{3}<...<\lim_{n\to\infty}\beta_{n}=2$, where
$\beta_{2}=(1+\sqrt{5})/2$ is the golden mean. So $\mathcal{X}=\\{0,1\\}$.
Using (19) and induction for $n=1,2,...$, it is straightforwardly verified
that for any $(x_{1},...,x_{n})\in\mathcal{X}^{n}$, $\ell_{x_{1},...,x_{n}}$
is equal to

$\displaystyle\beta^{-n}\times\begin{cases}0&\text{if }n>s,\
x_{i}=...=x_{i+s}=1,\ 1\leq i\leq n-s\\\ 1&\text{else if }x_{n}=0\\\
\beta^{i}-\sum_{j=0}^{i-1}\beta^{j}&\text{else if }x_{n-i}=0,\
x_{n-i+1}=...=x_{n}=1,\ 1\leq i\leq s,\ i<n\\\
\beta^{n}-\sum_{j=0}^{n-1}\beta^{j}&\text{else if }x_{1}=...=x_{n}=1,\ s\geq
n.\end{cases}$

Thus, the admissible sequences of 0’s and 1’s are those with at most $s$
consecutive 1’s (in accordance with [21]). It is easily seen that (10) holds
with $p_{x_{1},...,x_{s},1}=1-p_{x_{1},...,x_{s},0}$ and

$p_{x_{1},...,x_{s},0}=\begin{cases}{1}/{\beta}&\text{if }x_{s}=0\\\
{1}/{(\beta^{i+1}-\sum_{j=1}^{i}\beta^{j})}&\text{if }x_{s-i}=0,\
x_{s-i+1}=...=x_{s}=1,\ 1\leq i<s\\\ 1&\text{if
}x_{1}=\ldots=x_{s}=1.\end{cases}$ (20)

Finally, $\Omega=\mathcal{X}^{s}$.

######  Example 2.3.

Recall the following about continued fractions [15]. Let $I=(0,1]$,
$\mathcal{X}=\mathbb{N}$, $\tilde{I}_{k}=(1/(k+1),1/k]$ for $k\in\mathcal{X}$,
and $T(x)=1/x-\lfloor 1/x\rfloor$ be the Gauss map [9]. A rational number in
$I$ has a (regular) finite continued fraction representation

$[0;x_{1},...,x_{n}]=\frac{1}{x_{1}+\frac{1}{x_{2}+\frac{1}{\ddots\frac{1}{x_{n}}}}}\in(0,1]$

and each irrational number $x\in(0,1)$ has a unique infinite continued
fraction representation

$x=[0;x_{1},x_{2},...]=\lim_{n\to\infty}[0;x_{1},...,x_{n}],$

with $x_{1},x_{2},...\in\mathbb{N}$. So $J$ consists of all irrational numbers
between 0 and 1, and

$\tilde{I}_{x_{1},...,x_{n}}=\begin{cases}\left[\,[0;x_{1},...,x_{n}],[0;x_{1},...,x_{n}+1]\,\right)&\text{for
$n=2,4,6,...$}\\\
\left(\,[0;x_{1},...,x_{n}+1],[0;x_{1},...,x_{n}]\,\right]&\text{for
$n=1,3,5,...$}\end{cases}$

For any $x=[0;x_{1},x_{2},...]\in J$, the continued fraction remainder is
given by $T^{n}(x)=[0;x_{n+1},x_{n+2},...]\in J$. Defining
$q_{n}=x_{n}q_{n-1}+q_{n-2}$ for $n\in\mathbb{N}$ with $q_{-1}=0$ and
$q_{0}=1$, then $q_{n}$ is a strictly increasing function of $n$ and
$\ell_{x_{1},...,x_{n}}^{-1}={q_{n}(q_{n}+q_{n-1})}$, so
$\ell_{x_{1},...,x_{n+1}}/\ell_{x_{1},...,x_{n}}={q_{n}(q_{n}+q_{n-1})}/[{q_{n+1}(q_{n+1}+q_{n})}]$
depends on every digit $x_{1},...,x_{n+1}$. Thus, (10) cannot be satisfied for
any $s\in\mathbb{N}_{0}$.

##  3 The sufficient digits

The following Theorem 3.1 establishes the coupling between $X$ and a non-
negative integer-valued random variable $N$ under the weak assumption that $f$
is almost everywhere LSC, cf. (6). As noticed after Theorem 3.1,
$S=(X_{1},...,X_{N})$ becomes a sufficient statistic (if $N=0$ then $S$ is
interpreted as the empty set). Therefore, $X_{1},...,X_{N}$ are called the
sufficient digits (though it is of course not meant that the approximation
$X\approx A_{n}$ does not improve when $n>N$).

###  3.1 Coupling construction between $X$ and $N$

Some notation is needed. Assume (6) and recall the definition of $H$. For
$n\in\mathbb{N}$ and $(x_{1},...,x_{n})\in\mathcal{X}^{n}$, let
$c_{\emptyset}=i_{\emptyset}=\inf_{H}f$ and

$c_{x_{1},...,x_{n}}=i_{x_{1},...,x_{n}}-i_{x_{1},...,x_{n-1}}$

where

$i_{x_{1},...,x_{n}}=\begin{cases}\inf_{H\cap I_{x_{1},...,x_{n}}}f&\text{if
}H\cap I_{x_{1},...,x_{n}}\not=\emptyset\\\ 0&\text{if }H\cap
I_{x_{1},...,x_{n}}=\emptyset.\end{cases}$

If $n=0$, interpret $(x_{1},...,x_{n})\in\mathcal{X}^{n}$ as
$\emptyset\in\\{\emptyset\\}$, $c_{x_{1},...,x_{n}}$ as $c_{\emptyset}$, and
$\ell_{x_{1},...,x_{n}}$ as $\ell_{\emptyset}$. Let $\nu$ be the product
measure on $H\times\mathbb{N}_{0}$ given by the product of Lebesgue measure on
$H$ and counting measure on $\mathbb{N}_{0}$.

######  Theorem 3.1.

Assuming (6) and recalling the notation in (5) and (7)–(9), the following
items (A)–(D) hold.

  1. (A)

There is a coupling of $X$ with a non-negative integer-valued random variable
$N$ such that the distribution of $(X,N)$ is absolutely continuous with
respect to $\nu$, with density for any $(x,n)\in H\times\mathbb{N}_{0}$ given
by

$f(x,n)=c_{x_{1},...,x_{n}}\quad\mbox{if }x=.x_{1}x_{2}...$ (21)

  2. (B)

For any $n\in\mathbb{N}_{0}$, $(x_{1},...,x_{n})\in\mathcal{X}^{n}$, and $x\in
H$ with $f(x)>0$,

$\displaystyle\mathrm{P}(S=(x_{1},...,x_{n}))$
$\displaystyle=c_{x_{1},...,x_{n}}\ell_{x_{1},...,x_{n}},$ (22)
$\displaystyle\mathrm{P}(N\leq n\,|\,X=x)$
$\displaystyle=i_{x_{1},...,x_{n}}/f(x),$ (23) $\displaystyle\mathrm{P}(N\leq
n)$
$\displaystyle=\sum_{(x_{1},...,x_{n})\in\mathcal{X}^{n}}i_{x_{1},...,x_{n}}\ell_{x_{1},...,x_{n}}.$
(24)

  3. (C)

One has

$S\perp\\!\\!\\!\perp U\sim\mathrm{Unif}(0,1)$ (25)

and $R$ conditioned on $S=(x_{1},...,x_{n})$ has finite dimensional
distributions

$\mathrm{P}(R_{1}=x_{n+1},...,R_{m}=x_{n+m}\,|\,S=(x_{1},...,x_{n}))=\ell_{x_{1},...,x_{n+m}}/\ell_{x_{1},...,x_{n}}$
(26)

when $(x_{1},...,x_{n+m})\in\mathcal{X}^{n+m}$ with $m\in\mathbb{N}$,
$n\in\mathbb{N}_{0}$, and $\mathrm{P}(S=(x_{1},...,x_{n}))>0$, i.e., provided
$c_{x_{1},...,x_{n}}\ell_{x_{1},...,x_{n}}>0$.

  4. (D)

Conditioned on $L$, one has $S\perp\\!\\!\\!\perp E\sim\mathrm{Unif}(0,L)$.

###### Proof.

The theorem is an extension of results in [11] for the special case of
base-$q$ expansions (with $q>1$ an integer, cf. Example 2.1). A general,
different, and shorter proof is given below.

Let $x=.x_{1}x_{2}...\in H$. Then,

$f(x)=\lim_{n\to\infty}i_{x_{1},...,x_{n}}=\lim_{n\to\infty}\left(i_{\emptyset}+\sum_{i=1}^{n}c_{x_{1},...,x_{i}}\right)=\sum_{n=0}^{\infty}c_{x_{1},...,x_{n}}$

where the first equality follows since $f$ is LSC at $x\in H$ and $x$ is in
the interior of $I_{x_{1},...,x_{n}}$, and the second equality follows from
the definition of $i_{x_{1},...,x_{n}}$. Clearly, $c_{x_{1},...,x_{n}}\geq 0$
and

$\int\sum_{n=0}^{\infty}c_{x_{1},...,x_{n}}\,\mathrm{d}x=\int
f(x)\,\mathrm{d}x=1,$

so (21) specifies a well-defined distribution on $H\times\mathbb{N}_{0}$.
Thereby the existence of the coupling with density (21) follows, and so (A) is
verified.

From (21) follows immediately (22). A straightforward calculation gives first
(23) using (21) and second (24) using (23). This proves (B).

Since $(X,N)$ and $(S,U)$ are in a one-to-one correspondence, combining (21)
and (22) shows that for $u\in(0,1)$ and $\mathrm{P}(S=(x_{1},...,x_{n}))>0$,

$\displaystyle\mathrm{P}(U\leq u\,$
$\displaystyle|\,S=(x_{1},...,x_{n}))=\frac{\mathrm{P}(a_{x_{1},...,x_{n}}<X\leq
a_{x_{1},...,x_{n}}+\ell_{x_{1},...,x_{n}}u,N=n)}{\mathrm{P}(S=(x_{1},...,x_{n}))}$
$\displaystyle=\frac{\int_{a_{x_{1},...,x_{n}}}^{a_{x_{1},...,x_{n}}+u\ell_{x_{1},...,x_{n}}}c_{x_{1},...,x_{n}}\,\mathrm{d}x}{c_{x_{1},...,x_{n}}\ell_{x_{1},...,x_{n}}}=u.$

Thus, $U|S\sim\mathrm{Unif}(0,1)$ and hence (25) follows. Furthermore, (21)
and (22) give

$\displaystyle\mathrm{P}(R_{1}=x_{n+1},...,R_{m}=x_{n+m}\,|\,S=(x_{1},...,x_{n}))$
$\displaystyle=\,$
$\displaystyle\frac{\mathrm{P}(X_{1}=x_{1},...,X_{n}=x_{n},X_{n+1}=x_{n+1},...,X_{n+m}=x_{n+m},N=n)}{\mathrm{P}(S=(x_{1},...,x_{n}))}$
$\displaystyle=\,$
$\displaystyle\frac{\int_{I_{x_{1},...,x_{n+m}}}c_{x_{1},...,x_{n}\,\mathrm{d}x}}{c_{x_{1},...,x_{n}}\ell_{x_{1},...,x_{n}}}=\ell_{x_{1},...,x_{n+m}}/\ell_{x_{1},...,x_{n}}$

whereby (26) is proven. Finally, (D) is immediately obtained from (25), which
completes the proof. ∎

Various comments on Theorem 3.1 are in order.

The joint distribution of $(X,N)$ is specified by $X\sim f$. Since $N$ is not
a function of $X$, it may be treated as a latent variable. Suppose a
statistical model class for the PDF $f$ is given (so that $f$ is LSC almost
everywhere on $J$). Since $(X,N)$ is in a one-to-one correspondence with
$(S,U)$, where $S\perp\\!\\!\\!\perp U\sim\mathrm{Unif}(0,1)$, it follows that
$S$ is a sufficient statistic and $U$ is an ancillary statistic when imagining
$N$ is observable, cf. [1]. Some suggestions on how to construct models for
$S$ appear in Section 5.

The distribution of $N$ depends on the choice of $H$, that is, the version of
the PDF $f$. In brief, to make $N$ small, pick $H$ in (6) as small as
possible, cf. (23).

It is remarkable that the conditional distribution of $R$ given $S$, depends
not on $f$ but only on the ratios between the lengths of the intervals, cf.
(26). Therefore, for any $n\in\mathbb{N}_{0}$, conditioned on $N\leq n$, the
distribution of $X_{>n}$ (or equivalently $X^{[n]}$) depends only on these
ratios. This property is exploited further in Section 4.

###  3.2 Corollaries

From (24) one easily gets the following corollary.

######  Corollary 3.2.

Assume (6). Then, for any fixed $n\in\mathbb{N}_{0}$,

$P(N\leq n)=1$ (27)

if and only if for every $(x_{1},...,x_{n})\in\mathcal{X}^{n}$,

$f(x)$ is constant for almost all $x\in I_{x_{1},...,x_{n}}$. (28)

In particular, $N=0$ almost surely if and only if $X\sim\mathrm{Unif}(I)$.

######  Example 3.3.

For continued fraction representations, where $T$ is the Gauss map given in
Example 2.3, it is well-known that

$f_{\mathrm{G}}(x)=\frac{1}{\ln 2}\frac{1}{1+x},\quad 0<x\leq 1,$ (29)

is the PDF of the unique $T$-invariant distribution, see e.g. [5]. By
Corollary 3.2, $N$ is unbounded when $X\sim f_{\mathrm{G}}$.

The simplest case of (10) happens when $s=0$. Defining the PMF

$\pi_{\mathrm{inv}}(k)=\ell_{k}/\ell_{\emptyset}\quad\mbox{for
}k\in\mathcal{X},$

then (10) with $s=0$ is equivalent to

$\ell_{x_{1},...,x_{n}}=\pi_{\mathrm{inv}}(x_{1})\cdots\pi_{\mathrm{inv}}(x_{n})/\ell_{\emptyset}\quad\text{whenever
}n\geq 2\text{ and }(x_{1},...,x_{n})\in\mathcal{X}^{n}.$ (30)

######  Corollary 3.4.

Assuming (6) and (30), the following items (A)–(D) hold.

  1. (A)

The following statements (I)–(III) are equivalent.

    1. (I)

$X_{1},X_{2},...$ are IID with PMF $\pi_{\mathrm{inv}}$.

    2. (II)

$X\sim\mathrm{Unif}(I)$.

    3. (III)

$N=0$ almost surely.

  2. (B)

$S\perp\\!\\!\\!\perp R$ and $R_{1},R_{2},...$ are IID with PMF
$\pi_{\mathrm{inv}}$.

  3. (C)

$S\perp\\!\\!\\!\perp X^{[N]}\sim\mathrm{Unif}(I)$.

  4. (D)

For every $n\in\mathbb{N}_{0}$, conditioned on $N\leq n$, one has
$X^{[n]}\sim\mathrm{Unif}(I)$ and $X_{n+1},X_{n+2},...$ are IID with PMF
$\pi_{\mathrm{inv}}$.

###### Proof.

Let $(x_{1},...,x_{n+m})\in\mathcal{X}^{n+m}$, $m\in\mathbb{N}$, and
$n\in\mathbb{N}_{0}$. For $\mathrm{P}(S=(x_{1},...,x_{n}))>0$ or equivalently
$c_{x_{1},...,x_{n}}\ell_{x_{1},...,x_{n}}>0$, cf. (22), it follows from (26)
and (30) that

$\mathrm{P}(R_{1}=x_{n+1},...,R_{m}=x_{n+m}\,|\,S=(x_{1},...,x_{n}))=\pi_{\mathrm{inv}}(x_{1})\cdots\pi_{\mathrm{inv}}(x_{n}).$

Thus (B) is verified. It is straightforwardly seen that (A) holds because of
the following equivalences: From (B) and (III) follow (I); (II) implies (III);
and (I) and (II) are equivalent. Finally, since $X^{[N]}=.R_{1}R_{2}...$, both
(C) and (D) follow from (A) and (B). ∎

For instance, (30) is satisfied in the setting for a generalized Lüroth series
(GLS), including e.g. base-$q$ expansions, cf. Example 2.1. For the GLS
setting, the fact that (II) implies (I) in Corollary 3.4 also follows from
Lemma 1 in [2].

Let $Q^{[n]}$ be the probability distribution of $X^{[n]}$, $\mu$ a
probability measure on the measure space $(I,\mathcal{B})$ where $\mathcal{B}$
is the class of Borel sets included in $I$, and
$\|Q^{[n]}-\mu\|_{\mathrm{TV}}=\sup_{A\in\mathcal{B}}|Q^{[n]}(A)-\mu(A)|$ the
total variation distance of the signed measure $Q^{[n]}-\mu$. It is well-known
that if $\mu$ has PDF $h$ and $X^{[n]}$ has PDF $f^{[n]}$, then

$\|Q^{[n]}-\mu\|_{\mathrm{TV}}=\frac{1}{2}\int_{I}|f^{[n]}(x)-h(x)|\,\mathrm{d}x.$

For instance, $f^{[n]}$ may be given by (16), and in the following corollary,
$h=1/\ell_{\emptyset}$.

######  Corollary 3.5.

Assume (6) and (30), and let $\mu_{\mathrm{inv}}=\mathrm{Unif}(I)$. Then there
is a coupling between $(X,N)$ and a random variable $Y\sim\mu_{\mathrm{inv}}$
such that $X^{[n]}=Y^{[n]}\sim\mu_{\mathrm{inv}}$ when $N\leq n$, and so

$\|Q^{[n]}-\mu_{\mathrm{inv}}\|_{\mathrm{TV}}\leq\mathrm{P}(N>n)\to
0\quad\mbox{as }n\to\infty.$ (31)

###### Proof.

In consistence with (A) and (B) in Corollary 3.4, let $S\perp\\!\\!\\!\perp
Y=.Y1Y2...\sim\mu_{\mathrm{inv}}$ and $R_{1}=Y_{N+1},R_{2}=Y_{N+2},...$.
Conditioned on $N\leq n$, one has $X^{[n]}=Y^{[n]}\sim\mu_{\mathrm{inv}}$, cf.
(D) in Corollary 3.4. Thus the inequality in (31) follows immediately from the
coupling inequality (see e.g. [24]). Since $N$ is finite, the convergence to 0
in (31) is obvious. ∎

##  4 Markov chains

This section treats the case of the Markovian structure in (10). The special
case $s=0$ has been treated in Section 3.2. Throughout this section, let
$s\in\mathbb{N}$ be given, let $X\sim f$ where $f$ satisfies (6), and let
$S,N,R$ be as in Theorem 3.1.

###  4.1 When the residual process is Markov

Recall the notation in (11)–(14). Note that (10) with $n=s+1$ gives

$p_{x_{1},...,x_{s},x_{s+1}}={\ell_{x_{1},...,x_{s+1}}}/{\ell_{x_{1},...,x_{s}}}\quad\mbox{for
$(x_{1},...,x_{s})\in\Omega$ and $x_{s+1}\in\mathcal{X}$}.$ (32)

######  Theorem 4.1.

Assume (6) and (10). Consider any $n\in\mathbb{N}_{0}$ and
$(x_{1},...,x_{n})\in\mathcal{X}^{n}$ with
$\mathrm{P}(S=(x_{1},...,x_{n}))>0$, that is,
$c_{x_{1},...,x_{n}}\ell_{x_{1},...,x_{n}}>0$, cf. (22). Conditioned on
$S=(x_{1},...,x_{n})$, $R^{(s)}$ is a time-homogeneous Markov chain with
transition matrix $P$ and initial distribution

$\displaystyle\mathrm{P}(R_{1}=x_{n+1},...,$ $\displaystyle
R_{s}=x_{n+s}\,|\,S=(x_{1},...,x_{n}))$
$\displaystyle=\begin{cases}\prod_{j=n+1-s}^{n}p_{x_{j},...,x_{j+s}}&\text{if
}n\geq s\\\
(\ell_{x_{1},...,x_{s}}/\ell_{x_{1},...,x_{n}})\prod_{j=1}^{n}p_{x_{j},...,x_{j+s}}&\text{if
}n<s\end{cases}$ (33)

where $\prod_{j=1}^{0}\cdots$ is interpreted as 1.

###### Proof.

By (12) and (32), $P$ is a transition matrix, since its entries are non-
negative and each row sums to 1. For any $m\in\mathbb{N}_{0}$ and
$(x_{1},...,x_{n+m+s})\in\mathcal{X}^{n+m+s}$ with
$c_{x_{1},...,x_{n}}\ell_{x_{1},...,x_{n}}>0$,

$\displaystyle\mathrm{P}(R_{1}=x_{n+1},...,R_{m+s}=x_{n+m+s}\,|\,S=(x_{1},...,x_{n}))$
$\displaystyle=$
$\displaystyle\,{\ell_{x_{1},...,x_{n+m+s}}}/{\ell_{x_{1},...,x_{n}}}$ (34)
$\displaystyle=$
$\displaystyle\,\begin{cases}\prod_{i=0}^{m+s-1}{\ell_{x_{1},...,x_{n+i+1}}}/{\ell_{x_{1},...,x_{n+i}}}&\text{if
}n\geq s\\\
(\ell_{x_{1},...,x_{s}}/\ell_{x_{1},...,x_{n}})\prod_{i=s}^{n+m+s-1}(\ell_{x_{1},...,x_{i+1}}/\ell_{x_{1},...,x_{i}})&\text{if
}n<s\end{cases}$ $\displaystyle=$
$\displaystyle\,\begin{cases}\left(\prod_{i=0}^{s-1}p_{x_{n+i+1-s},...,x_{n+i+1}}\right)\left(\prod_{i=s}^{m+s-1}p_{x_{n+i+1-s},...,x_{n+i+1}}\right)&\text{if
}n\geq s\\\
\frac{\ell_{x_{1},...,x_{s}}}{\ell_{x_{1},...,x_{n}}}\left(\prod_{i=s}^{n+s-1}p_{x_{i+1-s},...,x_{i+1}}\right)\left(\prod_{i=n+s}^{n+m+s-1}p_{x_{i+1-s},...,x_{i+1}}\right)&\text{if
}n<s\end{cases}$ (35) $\displaystyle=$
$\displaystyle\,\begin{cases}\left(\prod_{j=n+1-s}^{n}p_{x_{j},...,x_{j+s}}\right)\left(\prod_{j=n+1}^{n+m}p_{x_{j},...,x_{j+s}}\right)&\text{if
}n\geq s\\\
({\ell_{x_{1},...,x_{s}}}/{\ell_{x_{1},...,x_{n}}})\left(\prod_{j=1}^{n}p_{x_{j},...,x_{j+s}}\right)\left(\prod_{j=n+1}^{n+m}p_{x_{j},...,x_{j+s}}\right)&\text{if
}n<s\end{cases}$ (36)

where (34) is obtained from (26), $0/0=0$, and (35) follows from (10) and
(32). From (36) with $m=0$ follows (4.1). If $m>0$, then

$\displaystyle\mathrm{P}(R_{m+s}=x_{n+m+s}\,|\,S=(x_{1},...,x_{n}),R_{1}=x_{n+1},...,R_{m+s-1}=x_{n+m+s-1})$
$\displaystyle=$
$\displaystyle\,\frac{\mathrm{P}(R_{1}=x_{n+1},...,R_{m+s}=x_{n+m+s}\,|\,S=(x_{1},...,x_{n}))}{\mathrm{P}(R_{1}=x_{n+1},...,R_{m+s-1}=x_{n+m+s-1}\,|\,S=(x_{1},...,x_{n}))}$
$\displaystyle=$ $\displaystyle\,p_{x_{n+m},...,x_{n+m+s}}$

where (36) is used in the last equality. So $R^{(s)}\,|\,S=(x_{1},...,x_{n})$
is a time-homogeneous Markov chain with transition matrix $P$. ∎

The following will be needed in Corollary 4.2 below.

To any PMF $\pi=(\pi_{x_{1},...,x_{s}})_{(x_{1},...,x_{s})\in\Omega}$
corresponds a PDF $f_{\pi}$ on $H$ which is defined for every
$x=.x_{1}x_{2}...\in H$ by

$f_{\pi}(x)=\begin{cases}{\pi_{x_{1},...,x_{s}}}/{\ell_{x_{1},...,x_{s}}}&\text{if
}(x_{1},...,x_{s})\in\Omega\\\ 0&\text{otherwise}.\end{cases}$ (37)

Clearly, $f_{\pi}$ is LSC on $H$. Conversely, from any PDF $f$ on $H$ which is
constant almost everywhere on each interval $I_{x_{1},...,x_{s}}$ with
$(x_{1},...,x_{s})\in\Omega$, one obtains a PMF $\pi$ on $\Omega$ such that
(37) is satisfied with $f=f_{\pi}$.

Assume (10) and $X\sim f_{\pi}$. Then $f_{\pi}$ is shift invariant if and only
if $\pi$ is invariant with respect to $P$ (or for short $P$-invariant) which
means that for every $(x_{1},...,x_{s})\in\Omega$,

$\sum_{k:\,(k,x_{1},....,x_{s-1})\in\Omega}\pi_{k,x_{1},....,x_{s-1}}p_{k,x_{1},...,x_{s}}=\pi_{x_{1},...,x_{s}}.$
(38)

For $s=1$, this is interpreted as
$\sum_{k\in\mathcal{X}}\pi_{k}p_{k,x_{1}}=\pi_{x_{1}}$.

######  Corollary 4.2.

Assume (10) and $X\sim f_{\pi}$ where $\pi$ is $P$-invariant. Then $N\leq s$
almost surely and $X^{(s)}$ is a stationary Markov chain with initial
distribution $(X_{1},...,X_{s})\sim\pi$ and transition matrix $P$. Conditioned
on $(X_{1},...,X_{s})$, one has $N\perp\\!\\!\\!\perp X_{>s}$.

###### Proof.

By (37), from $X\sim f_{\pi}$ follows $(X_{1},...,X_{s})\sim\pi$, and $N\leq
s$ almost surely, cf. Corollary 3.2. By Theorem 4.1, conditioned on both $N$
and $(X_{1},...,X_{s})$, or equivalently, conditioned on $S$ and on those (if
any) $R_{i}$ with $N<i\leq s-N$, $X^{(s)}$ is a Markov chain with transition
matrix $P$ and the distribution of $X_{>s}$ depends only on
$(X_{1},...,X_{s})$ (and not on $N$). Therefore, conditioned on
$(X_{1},...,X_{s})$, one has $N\perp\\!\\!\\!\perp X_{>s}$, and since
$(X_{1},...,X_{s})\sim\pi$, the distribution of the chain
$X^{(s)}=\\{X^{(s)}_{i}\\}_{i=1,2,...}$ is invariant under left shifts. The
proof is completed. ∎

It is well-known that there exists a unique $P$-invariant PMF if and only if
$P$ is irreducible. The notation $\pi_{\mathrm{inv}}$ will be used to indicate
that this is the unique $P$-invariant PMF. Letting
$f_{\mathrm{inv}}=f_{\pi_{\mathrm{inv}}}$, one gets:

######  Corollary 4.3.

Assume (10) and $P$ is irreducible. Then $f_{\mathrm{inv}}$ is the unique
shift invariant PDF (up to equivalence of PDFs).

The condition in Corollary 4.3 that $P$ is irreducible translates by (10) into
the condition that for any distinct
$(x_{1},...,x_{s}),(y_{1},...,y_{s})\in\Omega$, there exist $s+k-1\geq 1$
elements $x_{s+1},...,x_{2s+k-1}\in\mathcal{X}$ with
$x_{s+k}=y_{1},...,x_{2s+k-1}=y_{s}$ and
$\ell_{x_{1},...,x_{s+1}}>0,...,\ell_{x_{s+k-1},...,x_{2s+k-1}}>0$. In the
setting of a dynamical system (Section 2.2), Corollary 4.3 is in line with the
well-known result that if $T$ is ergodic with respect to Lebesgue measure and
$f$ specifies a $T$-invariant distribution, then $f$ specifies the unique
$T$-invariant distribution (in fact, in all specific examples of $T$ given in
this paper, $T$ is ergodic with respect to Lebesgue measure, see e.g. [23,
5]).

######  Example 4.4.

In continuation of Example 2.2 when $\beta$ is the pseudo golden mean of order
$s+1$, it follows by Theorem 4.1 that $R^{(s)}\,|\,S$ is a Markov chain. Since
the transition probabilities are given by (20), the chain is seen to be
irreducible. Thus, by Corollary 4.3, $f_{\mathrm{inv}}$ specifies the unique
shift invariant PDF or equivalently $T$-invariant probability measure where
$T(x)=\beta x-\lfloor\beta x\rfloor$. In fact, for any value of $\beta>1$,
Gelfond [10] and Parry [21] have independently obtained the $T$-invariant
distribution such that the corresponding PDF can be derived in closed form.

###  4.2 Coupling construction between $(X,N)$ and $(M_{1},M_{2})$

Some notation is needed for the following theorem. For every $z\in\Omega$ and
$i\in\mathbb{N}$, let $Y_{i}^{(s)}(z)=(Y_{i}(z),...,Y_{i+s-1}(z))$ and suppose
$Y^{(s)}(z)=\\{Y_{i}^{(s)}(z)\\}_{i=1,2,...}$ is a Markov chain on $\Omega$
with transition matrix $P$ and $Y_{1}^{(s)}(z)$ following the PMF given by row
$z$ in $P$. For $i\in\mathbb{N}$, denote $P_{i}^{(s)}(z)$ the distribution of
$Y_{i}^{(s)}(z)$, and $P^{i}$ the $i$-step transition matrix of $Y^{(s)}(z)$,
i.e., $P^{i}$ is the product of $P$ with itself $i$-times. Let $P^{i}_{z,w}$
be entry $(z,w)$ of $P^{i}$ and $\|\cdot\|_{\mathrm{TV}}$ the total variation
distance for signed finite measures on $\Omega$. Recall that uniform geometric
ergodicity of a Markov chain with transition matrix $P$ means that there is a
unique invariant PMF $\pi_{\mathrm{inv}}$ with respect to $P$ and for some
constants $\alpha$ and $\beta<1$ and for all $(z,i)\in\Omega\times\mathbb{N}$,

$\|P_{i}^{(s)}(z)-\Pi_{\mathrm{inv}}\|_{\mathrm{TV}}=\frac{1}{2}\sum_{w\in\Omega}|P^{i}_{z,w}-\pi_{\mathrm{inv}}(w)|\leq\alpha\beta^{i}$
(39)

where $\Pi_{\mathrm{inv}}$ is the probability measure on $\Omega$ with PMF
$\pi_{\mathrm{inv}}$. If $\Omega$ is finite, then uniform geometric ergodicity
is equivalent to irreducibility and aperiodicity of the chain. When $\Omega$
is countable, see Section 16.2.1 in [19] for conditions of uniform geometric
ergodicity. These criteria of uniform geometric ergodicity translate into
conditions on the lengths of the intervals at level $s+1$. This was
illustrated in the remark after the proof of Corollary 4.3 when discussing
irreducibility. Aperiodicity holds if e.g. $\ell_{x_{1},...,x_{2s}}>0$ and
$\ell_{x_{1},...,x_{2s+1}}>0$ for all
$(x_{1},...,x_{2s+1})\in\mathcal{X}^{2s+1}$.

######  Theorem 4.5.

Assume (6), (10), and (39), and let $\pi_{\mathrm{inv}}$ be the unique
$P$-invariant PMF and $f_{\mathrm{inv}}$ the corresponding shift invariant
PDF. Then there is a time $t\in\mathbb{N}$, a positive probability
$\epsilon_{t}>0$ (given by (43) below), and a coupling of $(X,N)$ with two
independent geometrically distributed random variables $M_{1}$ and $M_{2}$
with the same mean $1/\epsilon_{t}$ and support $\mathbb{N}$ such that the
following items (A)–(C) hold. Let $b=t+s-1$, $M=b(M_{1}+M_{2}-1)$, and
$K=\max\\{N,s\\}+M-s$. Then:

  1. (A)

$(X_{1},...,X_{\max\\{N,s\\}},N)$ is independent of both $X^{[K]}\sim
f_{\mathrm{inv}}$ and $X^{(s)}_{>K}$ which is a stationary Markov chain with
initial PMF $\pi_{\mathrm{inv}}$ and transition matrix $P$.

  2. (B)

For any $n\in\mathbb{N}_{0}$, conditioned on $K\leq n$, one has $X^{[n]}\sim
f_{\mathrm{inv}}$.

  3. (C)

$(X_{1},...,X_{\max\\{N,s\\}},N)\perp\\!\\!\\!\perp(M_{1},M_{2})$.

Theorem 4.5 and the following corollary are proved and exemplified in Section
4.4.

######  Corollary 4.6.

Assume (6), (10), and (39), let $f_{\mathrm{inv}}$ and $K$ be as in Theorem
4.5, and let $\mu_{\mathrm{inv}}$ be the probability measure with PDF
$f_{\mathrm{inv}}$. Then there is a coupling between $(X,K)$ and a random
variable $Z\sim\mu_{\mathrm{inv}}$ such that $X^{[n]}=Z^{[n]}$ when $K+s\leq
n$, and so

$\|Q^{[n]}-\mu_{\mathrm{inv}}\|_{\mathrm{TV}}\leq\mathrm{P}(K>n)\to
0\quad\mbox{as }n\to\infty.$ (40)

Theorem 4.5 and Corollary 4.6 are discussed together with Corollaries 3.4 and
3.5 in Section 5.2.

###  4.3 Read once algorithm

The proof in Section 4.4 of Theorem 4.5 is based on the read once algorithm
developed by Wilson [25]. The algorithm is stated below for the setting used
in the present paper.

The Markov chain $Y^{(s)}(z)$ can be specified as a stochastic recursive
sequence (SRS) so that

$Y_{i}(z)=g(Y_{i-s}(z),...,Y_{i-1}(z),V_{i}),\quad i=1,2,...,$ (41)

where $V_{1},V_{2},...$ are IID random variables,
$(Y_{1-s}(z),...,Y_{0}(z))=z$, and there are many possible choices of the
updating function $g$ and for the distribution of $V_{1}$: Without loss of
generality, assume $\mathcal{X}\subset\mathbb{R}$ is countable, and for
specificity, let $V_{1}\sim\mathrm{Unif}(0,1)$, and for
$(x_{1},...,x_{s})\in\Omega$, let

$(0,1)\ni v\mapsto g(x_{1},...,x_{s},v)=F^{-}(v\,|\,x_{1},...,x_{s})$ (42)

be the generalized inverse of the CDF

$F(x\,|\,x_{1},...,x_{s})=\sum_{k:\,k\leq
x,\,(x_{2},...,x_{s},k)\in\Omega}p_{x_{1},...,,x_{s},k},\quad x\in\mathbb{R},$

where $(x_{2},...,x_{s},k)$ is interpreted as $k$ if $s=1$. Note that all the
chains $Y^{(s)}(z)$ with $z\in\Omega$ are coupled via $(V_{1},V_{2},...)$.

For an integer $t\geq s$, letting $b=t+s-1$, then

$B=B(V_{1},...,V_{b})=\\{(Y_{1}(z),...,Y_{b}(z))\,|\,z\in\Omega\\}$

is called a block of length $b$. The block agrees with
$\\{(Y^{(s)}_{1}(z),...,Y^{(s)}_{t}(z))\,|\,z\in\Omega\\}$ and the notation
$B(V_{1},...,V_{b})$ is used to stress that the block depends only on
$V_{1},...,V_{b}$. Let $O(z,V_{1},...,V_{b})=Y^{(s)}_{t}(z)$, which is
interpreted as the output of $B$ when $z$ is the input in $B$. Call $B$ a
coalescent block with common output $O(V_{1},...,V_{b})=O(z,V_{1},...,V_{b})$
if this is the same for all $z\in\Omega$. Let

$\epsilon_{t}=\mathrm{P}(B\mbox{ is a coalescent block}),$ (43)

which is an increasing function of $t$. Suppose $\epsilon_{t}>0$, and consider
the sequence of blocks

$B_{i}=B_{i}(V_{(i-1)b+1},...,V_{ib}),\quad i=1,2,...,$

which are IID copies of $B$. Now, Wilson’s read once algorithm consists of
three steps:

  1. (A)

Draw $B_{1},...,B_{M_{1}},B_{M_{1}+1},...,B_{M_{1}+M_{2}}$ where $B_{M_{1}}$
and $B_{M_{2}}$ are the first and second coalescent blocks. Let
$O_{M_{1}b}=O(V_{(M_{1}-1)b+1},...,V_{M_{1}b})$ be the common output of
$B_{M_{1}}$.

  2. (B)

If $M_{2}\geq 2$, for $i=0,...,M_{2}-2$, use the output $O_{(M_{1}+i)b}$ of
$B_{M_{1}+i}$ as the input in the following block, which gives the output
$O_{(M_{1}+i+1)b}=O(O_{(M_{1}+i)b},V_{(M_{1}+i)b+1},...,V_{(M_{1}+i)b+b})$ in
$B_{M_{1}+i+1}$.

  3. (C)

Return $O=O_{M}$ where $M=(M_{1}+M_{2}-1)b$.

It follows from [8, 25] that the existence of a $t\in\mathbb{N}$ such that
$\epsilon_{t}>0$ is equivalent to (39), and it has already been noticed that
(39) implies the unique existence of the invariant PMF $\pi_{\mathrm{inv}}$.
Thus, the following lemma follows from [25].

######  Lemma 4.7.

Assume (10) and (39), and let $\pi_{\mathrm{inv}}$ be the unique $P$-invariant
PMF. Then $O\sim\pi_{\mathrm{inv}}$.

###  4.4 Proofs and example

###### Proof.

To prove Theorem 4.5, assume (39) and let $\pi_{\mathrm{inv}}$ be the unique
$P$-invariant PMF and $f_{\mathrm{inv}}$ the corresponding shift invariant
PDF. Using Theorem 3.1, $X=0.X_{1}X_{2}...\sim f$ and $N$ can be generated as
follows. First, generate $(X_{1},...,X_{N})$ from the PMF (22). If $N<s$ then
generate $(X_{N+1},...,X_{s})$ such that $(X_{N+1},...,X_{s})$ conditioned on
$(X_{1},...,X_{N})=(x_{1},...,x_{n})$ has PMF

$p(x_{n+1},...,x_{s}\,|\,x_{1},...,x_{n})=\ell_{x_{1},...,x_{s}}/\ell_{x_{1},...,x_{n}}\quad\mbox{whenever
$\ell_{x_{1},...,x_{n}}>0$.}$

This is in accordance with (26). Second, independent of
$(X_{1},...,X_{\max\\{N,s\\}},N)$, generate IID
$V_{1},V_{2},...\sim\mathrm{Unif}(0,1)$ and use the SRS (41) when generating

$X_{>{\max\\{N,s\\}}}=Y^{(s)}(X_{\max\\{N,s\\}-s+1},...,X_{\max\\{N,s\\}}).$

Thus $(X_{1},...,X_{\max\\{N,s\\}},N)$ is independent of the output $O$ of the
read once algorithm. By Lemma 4.7,

$X^{(s)}_{\max\\{N,s\\}+M-s+1}=\left(X_{\max\\{N,s\\}+M-s+1},...,X_{\max\\{N,s\\}+M}\right)=O\sim\pi_{\mathrm{inv}}.$

Combining these facts with Corollaries 4.2 and 4.3, (A) in Theorem 4.5
follows. From (A) follows (B). Finally, since
$(X_{1},...,X_{\max\\{N,s\\}},N)\perp\\!\\!\\!\perp(V_{1},V_{2},...)$, (C)
follows from the read once algorithm. Hence the proof of Theorem 4.5 is
completed. ∎

###### Proof.

To prove Corollary 4.6, imagining that the first block starts just after time
$\max\\{N,s\\}$. Then $\max\\{N,s\\}+M$ is the time at which the output of the
read once algorithm has been produced. Hence, using (A) in Theorem 4.5, along
similar lines as in the proof of Corollary 3.5, Corollary 4.6 is obtained. ∎

######  Example 4.8.

Consider again Example 2.2 when $\beta$ is the pseudo golden mean of order
$s+1$. Since $\Omega$ is finite and a Markov chain with transition matrix $P$
given by (20) is irreducible and aperiodic, $\epsilon_{t}>0$ for all
sufficiently large $t$. So for large $t$, the assumptions in Theorem 4.5 are
satisfied, and hence the results in Theorem 4.5 and Corollary 4.6 apply.

Consider the case $s=1$. Solving (38) to obtain $\pi_{\mathrm{inv}}$ and then
using (37) together with the fact that $\beta^{2}=\beta+1$, one gets

$\pi_{\mathrm{inv}}=\left(\frac{\beta^{2}}{1+\beta^{2}},\frac{1}{1+\beta^{2}}\right),\quad
f_{\mathrm{inv}}(x)=\begin{cases}(1+2\beta)/(2+\beta)&\text{if }0<x<1/\beta\\\
(1+\beta)/(2+\beta)&\text{if }1/\beta<x<1.\end{cases}$

Choosing the updating function $g$ as in (42) and letting
$V\sim\mathrm{Unif}(0,1)$, then

$\epsilon_{1}=P(F^{-}(V\,|\,0)=F^{-}(V\,|\,1))=P(V\leq\beta^{-1})=\beta^{-1}=0.6180...$

This is for the case $t=1$, so the block length is just $b=1$ and the expected
running time of the read once algorithm is just

$\mathrm{E}(M_{1}+M_{2})=2/\epsilon_{1}=\sqrt{5}+1=3.2361...$

So it may be expected that $R_{n}\sim f_{\mathrm{inv}}$ for small values of
$n$.

##  5 Concluding remarks

This section concludes with a discussion of the main results of this paper,
including some open problems for future research.

Assuming only almost everywhere lower semi-continuity of $f$, Theorem 3.1
establishes the general results of this paper. In my opinion, the two most
important general results are that $S\perp\\!\\!\\!\perp
U\sim\mathrm{Unif}(0,1)$ and $R\,|\,S$ follows a distribution which does not
depend on $f$ but it is specified by ratios of the lengths of intervals in the
nested subdivisions, cf. (26). The first result leads to a discussion in
Section 5.1 of statistical modelling, and the importance of the latter result
is discussed in Section 5.2.

###  5.1 Statistical models

After Theorem 3.1 it was noticed that $S=(X_{1},...,X_{N})$ is a sufficient
statistic when $N$ is treated as a latent variable. Hence, for likelihood
based statistical inference, no matter if it is in a classical/frequentist or
Bayesian setting, the likelihood function based on $(X,N)$ is equivalent to
the likelihood based on the discrete random variable $S$, cf. [1]. So a
natural question is how to specify the distribution of $S$.

Statistical models where $N$ is expected to be small would possibly suffice in
many applications: For the case of base-$q$ expansions, specific examples of
PDFs $f$ in [12] show that $N$ will be small when $q$ is not small and $f$
does not deviate much from $f_{\mathrm{inv}}=1$.

Since $S$ is a (discrete) random variable of varying dimension, one modelling
approach could be inspired by the construction of point process models [7,
20]. For example, in analogy with the use of Janossy densities when specifying
finite point process densities, by specifying the distribution of first $N$
and next $S\,|\,N$. Or, in the same spirit as when Gibbs distribution models
for finite point process are defined, specifying the distribution of $S$ with
respect to some natural reference measure under which e.g.
$X_{1},...X_{N}\,|\,N$ are IID and independent of $N$.

In connection to Bayesian inference, another question is how to construct a
random PDF $f(\cdot\,|\,Y)$, assuming $Y$ is a stochastic process such that
$\mathrm{P}(X\in B\,|\,Y)=\int_{B}f(x\,|\,Y)\,\mathrm{d}x$ for any
$B\in\mathcal{B}$ (the class of Borel sets included in $I$). One possibility
is the mixture of finite Polya tree distributions given by (44) below which is
obtained as follows. Let $I$ be the unit interval and $\mathcal{X}=\\{0,1\\}$.
Denote $B(\alpha_{0},\alpha_{1})$ the beta-distribution with shape parameters
$\alpha_{0}\geq 0$ and $\alpha_{1}\geq 1$ such that $\alpha_{0}+\alpha_{1}>0$,
where if $k\in\\{0,1\\}$ and $\alpha_{k}=0$ then $B(\alpha_{0},\alpha_{1})$ is
concentrated at the point $k-1$ and hence the value of $\alpha_{1-k}>0$ plays
no role. Suppose
$Y=\\{Y_{x_{1},...,x_{n}}\,|\,(x_{1},...,x_{n})\in\\{0,1\\}^{n},\,n\in\mathbb{N}\\}$
where the $Y_{x_{1},...,x_{n-1},0}$’s (interpreted as $Y_{0}$ if $n=0$) are
independent
$B(\alpha_{x_{1},...,x_{n-1},0},\alpha_{x_{1},...,x_{n-1},1})$-distributed,
$Y_{x_{1},...,x_{n-1},1}=1-Y_{x_{1},...,x_{n-1},0}$, and
$\alpha_{x_{1},...,x_{n}}=0$ if $\ell_{x_{1},...,x_{n-1}}>0$ and
$\ell_{x_{1},...,x_{n}}=0$. Let $N$ be a non-negative integer-valued random
variable which is independent of $Y$. Conditioned on $(Y,N)$, for $n=0,...,N$,
let the $X_{n}$’s be independent and let $Y_{X_{1},...,X_{n-1},0}$ be the
probability that $X_{n}=0$. Thereby, conditioned on $Y$, $S=(X_{1},...,X_{N})$
has been generated. In accordance with Theorem 3.1, conditioned on $S$,
independent of $Y$, if $N=0$ then generate $X\sim\mathrm{Unif}(I)$ else
generate $E\sim\mathrm{Unif}(0,\ell_{X_{1},...,X_{N}})$ and set
$X=a_{X_{1},...,X_{N}}+E$. Thus, conditioned on $Y$ and $N=n$ with
$\mathrm{P}(N=n)>0$, $X$ follows a random PDF $f(\cdot\,|\,Y,N=n)$ which for
$x\in I_{x_{1},...,x_{n}}$ is given by

$f(x\,|\,Y,N=n)=\prod_{j=1}^{n}Y_{x_{1},...,x_{j-1},0}^{1-x_{j}}Y_{x_{1},...,x_{j-1},1}^{x_{j}}$

where $\prod_{j=1}^{0}\cdots$ is interpreted as 1. This random PDF, where
$N=n$ is fixed, specifies a finite Polya tree distribution in the sense of
Lavine [17]; if $N$ was replaced by $\infty$ when generating $X_{1},X_{2},...$
above, the random probability distribution given by
$\mathrm{P}(0.X_{1}X_{2}...\in B\,|\,Y)$ with $B\in\mathcal{B}$ would be a
Polya tree distribution as defined by Lavine [16]. Arguments for considering
instead a finite Polya tree distribution can be found in [17, 26]. For
instance, a Polya tree distribution (in contrast to the finite Polya tree
distribution) is not always absolutely continuous (unless the $\alpha$’s
increase sufficiently rapidly which leads to problems of robustness, cf.
[17]), and if it is absolutely continuous then the random PDF is almost surely
discontinuous almost everywhere. Note that $X\,|\,Y$ specifies a random
probability distribution $\mathcal{P}$ on $\mathcal{B}$ which is absolutely
continuous with random PDF

$f(x\,|\,Y)=\sum_{n=0}^{\infty}f(x\,|\,Y,N=n)\mathrm{P}(N=n)$ (44)

(setting $f(x\,|\,Y,N=n)=0$ if $\mathrm{P}(N=n)=0$). The use of $\mathcal{P}$
for statistical modelling and a comparison with other ways of imposing random
stopping rules in a Polya tree distribution (including allowing optional
stopping as in [26]) should be investigated in another paper.

Yet another interesting question is how to model random nested partitions? For
instance, if $I$ is a unit interval and $\mathcal{X}=\\{0,1\\}$ is binary, one
may consider a distribution of the lengths
$\\{\ell_{x_{1},...,x_{n}}\,|\,(x_{1},...,x_{n})\in\\{0,1\\},n\in\mathbb{N}\\}$
which is of a similar type as for $Y$ above and is independent of $(N,Y)$, and
then proceed in a similar way as above when specifying a model for $S$
conditioned on both $Y$ and the random nested partitions. How should this be
extended to multi-variate cases (where the ideas behind randomized
partitioning schemes in [26] may be a source of inspiration)? How should one
create random models for the intervals used to define the Markovian
constructions in Section 2.1, including the case of generalized Lüroth series
in Example 2.1? These questions are also left for future research.

###  5.2 How important is the Markovian structure?

Birkhoff’s ergodic theorem is a major tool in metric number theory when
studying ergodic dynamical systems in connection to stationary digit systems
$X_{1},X_{2},...$, see e.g. [5, 6, 23]. Birkhoff’s theorem is in close
agreement with Corollaries 3.4 and 3.5, Theorem 4.5, and Corollary 4.6,
although there are differences. To see this, suppose $X_{>0}$ is stationary
and ergodic. Here, ergodicity means that $\mathrm{P}(X\in A)\in\\{0,1\\}$
whenever $A\subseteq I$ is a Borel set such that $.x_{1}x_{2}...\in A$ implies
$.x_{2}x_{3}...\in A$. Let $h:I\mapsto\mathbb{R}$ be a Borel function where
the mean $\mathrm{E}h(X)$ exists. Then Birkhoff’s theorem states that “the
time average converges to the space average”:

$\frac{1}{m}\sum_{n=1}^{m}h(X^{[n]})\to\mathrm{E}h(X)\quad\mbox{as
}m\to\infty.$

On the other hand, the results in the present paper state that under certain
regularity conditions, but without assuming $X_{>0}$ is stationary, it is not
possible to distinguish between the distributions of the remainders
$X^{[n]},X^{[n+1]},...$ when $n$ is larger than a certain random time: At the
random time $N+1$ (under the conditions given in Corollary 3.4) or
$\max\\{N,s\\}+M$ (under the conditions given in Theorem 4.5) and further on
in time, the remainders are exactly following the shift-invariant PDF
$f_{\mathrm{inv}}$. Moreover, under the conditions given in Corollaries 3.5
and 4.6, the distribution of $X^{[n]}$ converges towards the invariant
distribution with respect to the total variation distance.

For this convergence result the assumption that $f$ is LSC almost everywhere
may be replaced by other assumptions: For a general PDF $f$, if there is only
one PDF invariant under the shift, namely $f_{\mathrm{inv}}$, and if
$\int_{I}|g^{[n]}-f_{\mathrm{inv}}|\to 0$ for a PDF $g^{[n]}$ corresponding to
a smooth PDF $g$ (using a similar notation as for $f^{[n]}$ and $f$ in Section
3.2), the triangle inequality and the inequality
$\int_{I}|f^{[n]}-g^{[n]}|\leq\int_{I}|f-g|$ give the convergence result.
Moreover, bounds for the rate of convergence are given in [11] for the case of
base-$q$ expansions (Example 2.1), in [13] for $\beta$-expansions when $\beta$
is the golden mean (Example 2.2), and in [14] when $\beta$ is the pseudo
golden mean (Example 2.2). For these cases the assumption that $f$ is LSC
almost everywhere is indeed not needed.

For cases where the Markovian structure (10) is not satisfied for any
$s\in\mathbb{N}_{0}$, it would of course also be interesting to establish
similar convergence results, to study the distribution of $R\,|\,S$ given by
(26) (which do not depend on $f$), and if possible to establish a coupling
between $X$ and a random time $K$ (depending on $f$) so that $X^{[K]}\sim
f_{\mathrm{inv}}$. Here, one particular interesting case is continued fraction
representations, cf. Example 2.3, where $f_{\mathrm{inv}}=f_{\mathrm{G}}$ is
given by (29).

## Acknowledgements

Supported by The Danish Council for Independent Research — Natural Sciences,
grant DFF – 10.46540/2032-00005B. I am grateful to Anne Marie Svane and Ira
Herbst for a careful reading of a draft of this paper and their useful
comments. Discussions with Charlene Kalle and Simon Kristensen on various
details, including continued fractions, are appreciated. I thank Mario Beraha
for pointing my attention to Polya tree distributions.

## References

  * [1] Barndorff-Nielsen, O.E. (1978). Information and Exponential Families in Statistical Theory. Wiley, Chichester.
  * [2] Barrionuevo, J., Burton, R.M., Dajani, K. and Kraiikamp, C. (1996). Ergodic properties of generalized Lüroth series. Acta Arith. 74, 311–327.
  * [3] Cornean, H., Herbst, I., Møller, J., Støttrup, B.B. and Studsgaard, K.S. (2022). Characterization of random variables with stationary digits. J. Appl. Prob. 59, 931–947.
  * [4] Cornean, H., Herbst, I., Møller, J., Støttrup, B.B. and Studsgaard, K.S. (2023). Singular distribution functions for random variables with stationary digits. Methodol. Comput. Appl. Probab. 25, article no. 31. Available at arXiv:2201.01521.
  * [5] Dajani, K. and Kalle, C. (2021). A First Course in Ergodic Theory. Chapman and Hall/CRC.
  * [6] Dajani, K. and Kraaikamp, C. (2002). Ergodic Theory of Numbers. Mathematical Association of America.
  * [7] Daley, D.J. and Vere-Jones, D. (2003). An Introduction to the Theory of Point Processes. Volume I: Elementary Theory and methods. Springer-Verlag, New York.
  * [8] Foss, S.G. and Tweedie, R.L. (1998). Perfect simulation and backward coupling. Stoch. Models 14, 187–203.
  * [9] Gauss, C.F. (1976). Mathematisches Tagebuch 1796–1814. Akademische Verlagsgesellschaft, Geest & Portig K.G., Leipzig.
  * [10] Gelfond, A.O. (1959). A common property of number systems. Izv. Akad. Nauk. SSSR. Ser. Mat. 23, 809–814.
  * [11] Herbst, I.W., Møller, J. and Svane, A.M. (2024). How many digits are needed? Methodol. Comput. Appl. Probab., 26, article no. 5.
  * [12] Herbst, I.W., Møller, J. and Svane, A.M. (2023). How many digits are needed? Extended version of [11] available at arXiv:2307.06685.
  * [13] Herbst, I.W., Møller, J. and Svane, A.M. (2023). The asymptotic distribution of the remainder in a certain base-$\beta$ expansion. Submitted for journal publication. Available at arXiv:2312.09652.
  * [14] Herbst, I.W., Møller, J. and Svane, A.M. (2024). The asymptotic distribution of the scaled remainder for pseudo golden ratio expansions of a continuous random variable. Submitted for journal publication. Available at arXiv:2404.08387.
  * [15] Khintchine, A.Y. (1963). Continued Fractions. Noordhoff, Groningen.
  * [16] Lavine, M. (1992). Some aspects of Polya tree distributions for statistical modelling. The Annals of Statistics, 20, 1222–1235.
  * [17] Lavine, M. (1994). More aspects of Polya tree distributions for statistical modelling. The Annals of Statistics, 22, 1161–1176.
  * [18] Lüroth, J. (1883). Ueber eine eindeutige Entwickelung von Zahlen in eine unendliche Reihe. Math. Annalen 21, 411–423.
  * [19] Meyn, S.P. and Tweedie, R.L. (1993). Markov Chains and Stochastic Stability. Springer Verlag, London.
  * [20] Møller, J. and Waagepetersen, R.P. (2004). Statistical Inference and Simulation for Spatial Point Processes. Chapman & Hall/CRC, Boca Raton.
  * [21] Parry, W. (1960). On the $\beta$-expansions of real numbers. Acta Math. Acad. Sci. Hungar. 11, 401–416.
  * [22] Rényi, A. (1957). Representations for real numbers and their ergodic properties. Acta Math. Acad. Sci. Hungar. 8, 477–493.
  * [23] Schweiger, F. (1995). Ergodic Theory of Fibered Systems and Metric Number Theory. Clarendon Press, Oxford.
  * [24] Thorisson, H. (2000) Coupling, Stationarity, and Regeneration. Springer, New York.
  * [25] Wilson, D.B. (2000). How to couple from the past using a read-once source of randomness. Random Structures Algorithms 16, 85–113.
  * [26] Wong, W.H. and Ma, L. (2010). Optional Pólya tree and Bayesian inference. The Annals of Statistics 38, 1433–1459.