¹

1 Introduction↩︎

Let \(s(n)\) denote the number of ones in the binary expansion of an integer \(n\in\mathbb{N}\), namely, \[\textstyle s(n)=\sum_{k=0}^{m}n_k,\] where: \[\textstyle n=\sum_{k=0}^{m}n_k\cdot 2^k andn_k\in\{0,1\} for k=0,1,\dots,m.\]

Throughout the paper we write \(\mathbb{N}=\{0,1,2,\dots\}\) and \(\mathbb{N}^+=\{1,2,3,\dots\}\). Given any \(t\in\mathbb{N}\) and \(d\in\mathbb{Z}\), let \(\mu_t(d)\) denote the asymptotic density of the set of those natural numbers \(n\) for which \(s(n+t)-s(n)=d\), i.e. \[\label{AL} \mu_t(d)=\lim_{N\to\infty} \frac{1}{N}|\{ n< N \colon s(n+t) -s(n)=d \} |.\tag{1}\] It is well known that the limit 1 exists, and \(\mu_t\) is a properly defined probability measure on \(\mathbb{Z}\). Moreover, all the measures \(\mu_t\) have mean zero, i.e. \(\sum\limits_{k\in\mathbb{Z}}k\cdot\mu_t(k)=0\), and the following recurrence relations are satisfied: \[\label{even} \mu_{2t}(d)=\mu_t(d),\;t\in\mathbb{N},\;d\in\mathbb{Z},\tag{2}\] \[\label{odd} \mu_{2t+1}(d)=\frac{1}{2}\mu_t(d-1)+\frac{1}{2}\mu_{t+1}(d+1),\;t\in\mathbb{N},\;d\in\mathbb{Z}.\tag{3}\] For more details, see Lemma 1 in [1], Lemma 2.1 in [2]. This paper is motivated by the Cusick’s conjecture which states that \[\label{Cc} {\textstyle{\mu_t(\mathbb{N})>\frac{1}{2} for any t\in\mathbb{N}^+.}}\tag{4}\] The simplicity of the above statement is rather deceptive - the full conjecture is still open, although various results on the subject have been established ([2]–[8]). We briefly highlight some of them: paper [2] has shown that for any \(\varepsilon>0\) we have \(|\{t<T\colon \frac{1}{2}<\mu_t(\mathbb{N})<\frac{1}{2}+\varepsilon\}|=T-O(\frac{T}{\log T})\) (the symbol \(O(\cdot)\) stands for big \(O\) notation) which implies that the asymptotic density of the set of \(t\in\mathbb{N}\) which satisfy \(\mu_t(\mathbb{N})>\frac{1}{2}\) equals to one. In [4], a central limit theorem is established for generic sequences \((\mu_{t_k})\) arising by sampling digits of \(t_k\) from the balanced Bernoulli measure. Papers [5] and [8] have generalized this result, and additionally [8] has shown that \(\mu_t(\mathbb{N})>\frac{1}{2}\) for any \(t\) such that \((t)_2\) contains sufficiently many blocks of ones. Recently, [9] has proposed the decomposition of the characteristic functions associated to \(\mu_t\) into the sum of the corresponding components. Finally, we mention that Cusick conjecture has several equivalent formulations, see Section 3 in [2], and is connected to Tu-Deng conjecture [10],[11],[7].

A full proof of Cusick’s conjecture is likely to require a detailed structural understanding of the family \(\{\mu_t\}_{t \in \mathbb{N}}\). We will show that, after reindexing the odd integers via an appropriate partial order \(\preceq\), the family \(\{\mu_t\}_{t\in 2\mathbb{N}+1}\) corresponds to the marginal distributions of a hierarchical martingale defined by a stopped random walk, governed by an explicit recursive dynamics. For convenience we will assume that the random walk starts from zero, that is, we will work with the system of measures \(P_t\) which is related to \(\mu_{t}\) by the convolution: \(\mu_t=\mu_1\ast P_t\). First we will show that the maximal chains of the poset \((2\mathbb{N}+1,\preceq)\) determine the nonautonomous dynamics on pairs of probability measures on \(\mathbb{Z}\) which represents the growth of a planar binary tree, and next we will express it in the language of the stopped random walk. The marginal probability distributions of the associated martingale - namely the measures \(P_t\) - exhibit several rather desirable properties: the monotonicity of the span of the support, the monotonicity of the variance with the explicit bounds (Theorem 8), the symmetries, and clear asymptotic behaviour: the unbounded variance case satisfies the central limit theorem (by [5],[8]) while in the case of bounded variance the trajectories of the martingale are convergent, and the possible asymptotic distributions are exactly the measures \(\mu_{t}\) and their reflections (Theorem 10). At the end of the paper we focus on the median-preserving property of the martingale, and show that the Cusick conjecture is a special case of a more general statement concerning the asymmetric growth of the trees. In the language of binary digits: if \(P_t(\mathbb{N})>\frac{1}{2}\) for any odd \(t=(t_1t_2\dots t_n)_2\) with \(t_2=0\), then \(\mu_t(\mathbb{N})>\frac{1}{2}\) for any \(t\in\mathbb{N}\). We conjecture that the side of the tree that carries mass greater than \(\frac{1}{2}\) at the first step of the growth, remains so throughout the whole process (Conjecture 13). This last claim is supported numerically, and left open.

2 The evolution of sum of digits measures.↩︎

2.1 Order↩︎

Let us start with the sequence \(x_n=s(n+1)-s(n)\), \(n\in\mathbb{N}\), which defines measure \(\mu_1\). Let \[\tau_k=\min\{n\in\mathbb{N}\colon x_n=k\}, where k\in\mathbb{Z}_{\leq 1}=\{d\in\mathbb{Z}\colon d\leq 1\}.\] It is not difficult to establish that \(x_n\) is given by: \[\tau_k=2^{1-k} andx_{\tau_k+i}=x_ifor1\leq i <2^{1-k}, wherek\in\mathbb{Z}_{\leq 1}.\] The first elements of \(\{x_n\}_{n\in\mathbb{N}}\) are:
\[\boldsymbol{1},\;\; \boldsymbol{0}, 1, \;\;\boldsymbol{-1}, 1, 0, 1,\;\;\boldsymbol{-2}, 1, 0, 1, -1, 1, 0, 1,\;\;\boldsymbol{-3},1, 0, 1, -1, 1, 0, 1,-2, 1, 0, 1, -1, 1, 0, 1,\boldsymbol{-4},\dots\\None\]

The above sequence is an elegant representation of a geometric distribution with mean zero, more precisely, the corresponding frequencies lead to the formula: \[\label{mu1} \mu_1(k)=\left(\frac{1}{2}\right)^{2-k} fork=1,0,-1,-2,\dots\tag{5}\]

In this chapter we want to gain good insight into how the measures \(\mu_t\) evolve from \(\mu_1\). By 2 , only odd \(t\) have to be considered. To see that, we will consider an appropriate partial order on the set of odd natural numbers. We start from describing the intuition behind the above idea. Roughly speaking, equations 2 and 3 lead to the following tree-structured decomposition of a natural number \(t\) : If \(t\) is even, divide it by \(2\). If \(t\) is odd and greater than one, split \(t\) into two numbers: \(\frac{t-1}{2}\) and \(\frac{t+1}{2}\). For every number that has appeared, repeat this operation until one is reached. We will reverse time in this decomposition, and omit the even numbers, thereby obtaining a more straightforward evolution of \(\mu_t\).The initial measure \(\mu_1\) is already defined. By 2 and 3 , the \(\mu_3\) is given by:

The further evolution will be analysed with use of the following order.

From now on we will write \[T=2\mathbb{N}+1,\] and we consider this set as equipped with \(\preceq\).

There is a direct relation between the representation 7 and the binary representation of an odd integer. Let \(\beta \colon \{L, R\} \to \{0, 1\}\) be a mapping defined by: \[\beta(L) = 0 and \beta(R) = 1.\]

To prove the above observation it is enough to show by induction that \(t =w_k \circ \cdots \circ w_1(3)\) satisfies: \[t = 2^{k+1} + \sum_{i=1}^{k} \beta(w_i)\, 2^{k+1-i} + 1.\]

Throughout the paper, the set of all finite words \(\{L,R\}^{\star}\) equipped with the standard prefix order will be identified with the set \(T\setminus\{1\}\) with the order induced from \(T\). More precisely, define: \[\{L,R\}^\star =\bigcup\limits_{n\in\mathbb{N}} \{L,R\}^n, where\{L,R\}^0:=\{\varepsilon\} \;\;\; (\varepsilon- an empty word ).\] To the elements of \(\{L,R\}^\star\) we will refer as words rather than sequences, and thus given \(w\in\{L,R\}^\star\) determined by \(w_1,\dots,w_n\in \{L,R\}\) we will write \(w=w_1 \dots w_n\) rather than \(w=(w_1,\dots,w_n)\). The length of the word \(w\) will be denoted by \(\ell(w)\). Given \(t\in T\), we will write: \(tL:=L(t)\) and \(tR:=R(t)\). More generally, given \(w_1\dots w_n\in\{L,R\}^\star\), \[tw_1\dots w_n:=w_n\circ\dots\circ w_1 (t).\] With the above notation, the following identification (a bijection) arises naturally: \[h\colon \{L,R\}^\star\longrightarrow T\setminus\{1\}, where h(\varepsilon):=3 and \] \[h\colon w_1 \dots w_n\longmapsto 3w_1\dots w_n=w_n\circ\dots\circ w_1 (3).\] We will write, for instance, \(RR=15\) and \(RRRLR=123\). With this notation, order \(\preceq\) is consistent with the standard prefix order: \(w_1w_2\dots w_n\preceq v_1v_2\dots v_m\) if and only if \(n\leq m\) and \(w_i=v_i\) for any \(i\leq n\).
Given an infinite sequence \(w=(w_1,w_2,\dots)\in\{L,R\}^{\mathbb{N}}\), we will write \[\label{www} w(-1):=1,\;w(0):=3,\;w(t):=w_1\dots w_t\in T,\;t\in\mathbb{N}^+.\tag{8}\] With the above notation, given any \(w\in\{L,R\}^{\mathbb{N}}\), the sequence \(\{w(t)\}_{t=-1}^{\infty}\) is the maximal chain in \((T,\preceq)\). We will analyze how the sequences \(w\in\{L,R\}^\mathbb{N}\) govern the evolution of: \[\{\mu_{w(t)}\}_{t=-1}^{\infty}.\]

2.2 The dynamics of \(\mu_{w(t)}\)↩︎

The set of all probability measures on \(\mathbb{Z}\) will be identified with the set \(\Delta(\mathbb{Z})\subset l^1(\mathbb{Z})\) given by: \[\Delta(\mathbb{Z})=\{\;(P(k))_{k\in\mathbb{Z}}\;\colon\;P(k)\geq 0 for all k,and\sum\limits_{k\in\mathbb{Z}}P(k)=1\}.\] Set \(\Delta(\mathbb{Z})\) is naturally equipped with the topology of pointwise convergence which coincides with the topology induced from the space \((l^1(\mathbb{Z}),||\cdot||_1)\), where \(||P||_1=\sum\limits_{k\in\mathbb{N}}|P(k)|\). The set of centered probability measures on \(\mathbb{Z}\) will be identified with the set: \[\Delta_0(\mathbb{Z})=\{\;P\in \Delta(\mathbb{Z})\colon\; \sum\limits_{k\in\mathbb{Z}}k\cdot P(k)=0\}.\] Above, by writing \(\sum\limits_{k\in\mathbb{Z}}k\cdot P(k)=0\) we implicitly assume that the first moment exists: \(\sum\limits_{k\in\mathbb{Z}}|k|\cdot P(k)<\infty\). Now, let \(\{\sigma_d\}_{d\in\mathbb{Z}}\) denote the family of shift operators: \[\sigma_d\colon \Delta(\mathbb{Z})\ni (P(k))_{k\in\mathbb{Z}}\longmapsto (P(k-d))_{k\in\mathbb{Z}}\in \Delta(\mathbb{Z}).\] We will write \[\label{SLR} \sigma_L:=\sigma_{-1} and \sigma_R:=\sigma_{1}.\tag{9}\]

Any \(w\in\{L,R\}^\mathbb{N}\) determines the sequence \(\{\mu_{w(n)}\}_{n=-1}^{\infty}\) through the recursion based on the map \(\Phi\). For \(t=2s+1\geq 3\), define: \[\label{dee} \mu^L_{t}=\mu_{s+1} and \mu^R_{t}=\mu_{s},\tag{10}\] so we have, by 3 , \[\label{P} \mu_t=\Phi(\mu^L_t,\mu^R_t).\tag{11}\] For instance, \(\mu^L_3=\mu_2=\mu_1\), and \(\mu^R_3=\mu_1\). Fix \(w\in\{L,R\}^\mathbb{N}\). With notation 8 : \[\mu_3=\mu_{w(0)}=\Phi(\mu^L_{w(0)},\mu^R_{w(0)})=\Phi(\mu_1,\mu_1).\]

Further dynamics is governed by the two mappings: \[\Phi_L, \Phi_R\colon \Delta_0(\mathbb{Z})\times \Delta_0(\mathbb{Z}) \to \Delta_0(\mathbb{Z})\times \Delta_0(\mathbb{Z}),\] where \[\Phi_L(\mu,\nu)=(\Phi(\mu,\nu),\nu) and \Phi_R(\mu,\nu)=(\mu,\Phi(\mu,\nu)).\] Equations 2 and 3 imply that the sequence \((\mu^L_{w(n)},\mu^R_{w(n)})_{n=0}^{\infty}\) is the trajectory of the following nonautonomous dynamical system: \[\label{System} (\Delta_0(\mathbb{Z})\times \Delta_0(\mathbb{Z}), \{\Phi_{w_n}\}_{n\geq1}),\tag{12}\] see below.

Proposition 2 allows us to write shortly: \[\mu_{w(n)}=\Phi_{w(n)}(\mu_1), n\geq 0,\] where \(\Phi_{w(n)}\colon \Delta_0(\mathbb{Z})\to \Delta_0(\mathbb{Z})\) is defined by: \[\Phi_{w(0)}(\mu)=\Phi(\mu,\mu) and\Phi_{w(n)}(\mu):=\Phi\circ\Phi_{w_n}\circ\dots\circ\Phi_{w_1}(\mu,\mu).\]

For convenience, in next sections we will focus on the probability measures: \[\label{Pt} P_{w(n)} = \Phi_{w(n)}(\delta_0),\;n\geq 0,\tag{13}\] rather than on \(\mu_{w(n)}= \Phi_{w(n)}(\mu_1)\), which is justified by Observation 3 and equation 15 . Given \(\mu,\nu\in\Delta(\mathbb{Z})\), let \(\mu\ast\nu\) denote the convolution of measures \(\mu\) and \(\nu\), i.e. : \[(\mu\ast\nu)(d)=\sum\limits_{k\in\mathbb{Z}}\mu(k)\cdot\nu(d-k)=\sum\limits_{k\in\mathbb{Z}}\mu(k)\cdot (\sigma_{k}\nu)(d).\]

One may check by direct computation that the deconvolution formula is: \[\label{dc} P_{w(n)}(d)= 2\cdot\mu_{w(n)}(d+1)-\mu_{w(n)}(d+2),\;d\in\mathbb{Z}.\tag{15}\] Equations 14 and 15 allow us to switch between \(\mu_t\) and \(P_t\) when necessary. The definition of \(P_t\) given by \(\eqref{Pt}\) is consistent with the following system: \[\label{system} P_1=\delta_0,\;P_{2t}=P_t,\;P_{2t+1}=\Phi(P_{t+1},P_t),\tag{16}\] by which we may consider \(\{P_t\}_{t\in\mathbb{N}}\) instead of \(\{P_t\}_{t\in T}\) whenever convenient.

3 Growing trees↩︎

Compared to the standard dynamics behind equations 2 and 3 ( Proposition 2.5 in [4]), the recursion given by Proposition 2 represents the process of growing a tree. We will start from the natural connection between the planar binary trees, [12], and the bounded stopping times, [13]. We will show that measures \(P_{t}\) given by 13 are naturally embedded in the simple symmetric random walk \(S_n\), namely, for any \(t\in T\) there is a finite stopping time \(\tau_t\) such that \(P_t\) is the probability distribution of \(S_{\tau_t}\). A reader interested in the embedding problems related to the simple random walk is referred to [14], see also the original Skorohod embedding problem, [15].

3.1 Assumptions and notation.↩︎

Let \(\mathcal{T}\) be the smallest set satisfying:

1. \(\bullet \in \mathcal{T}\),

2. if \(T_-, T_+ \in \mathcal{T}\), then \([T_-, T_+] \in \mathcal{T}\).

The elements of \(\mathcal{T}\) are full planar binary trees, to which we shall refer simply as trees.. The height of a tree \(T \in \mathcal{T}\), denoted by \(|T|\), is defined by : \(|\bullet| = 0\), and \(|[T_-, T_+]| = \max\{|T_-|, |T_+|\} +1.\) The set of binary trees of height at most \(n\) will be denoted by \[\mathcal{T}_n = \{ T \in \mathcal{T}: |T| \leq n \}\]

The set \(\mathcal{T}\) is partially ordered by the following relation:

1. \(\bullet \sqsubseteq T\) for every \(T \in \mathcal{T}\).

2. \([S_-, S_+] \sqsubseteq [T_-, T_+]\) if and only if \(S_- \sqsubseteq T_-\) and \(S_+ \sqsubseteq T_+\).

Roughly speaking, \(S \sqsubseteq T\) iff \(S\) is obtained from \(T\) by replacing some subtrees with "\(\bullet\)" (with leaves).
From now on, assume that the triple \((\Omega, \mathcal{F}, \mathbb{P})\) is the canonical probability space with the balanced Bernoulli measure:

• \(\Omega=\{-1,1\}^\mathbb{N}\),

• \(\mathcal{F}\) is the \(\sigma-\)algebra of cylinder sets

• \(\mathbb{P}=\bigotimes_{n=1}^{\infty} P_n\) is the product of \(P_n=\frac{1}{2}\delta_{-1}+\frac{1}{2}\delta_1\)

The probability distribution of a random variable \(X\colon\Omega\to\mathbb{Z}\) will be denoted by \(\mathcal{L}(X)\), that is, \(\mathcal{L}(X)\in\Delta(\mathbb{Z})\) is given by: \(\mathcal{L}(X)(d)=\mathbb{P}[X= d]\), \(d\in\mathbb{Z}\). Let \(\xi_i\colon\Omega\to\{-1,1\}\), \(i\in\mathbb{N}^+\), denote the coordinate variables: \(\xi_i(\omega)=\omega_i\), \(\omega\in\Omega\). Obviously \(\{\xi_i\}_{i=1}^\infty\) are independent, with: \[\mathbb{P}[\xi_i = +1] = \mathbb{P}[\xi_i = -1] = \tfrac{1}{2},\;i\in\mathbb{N}^+.\] The simple random walk \(\{S_n\}_{n\in\mathbb{N}}\) is defined by: \[S_0=0 and S_n=\sum\limits_{i=1}^n\xi_i, \;n\in\mathbb{N}^+.\] The natural filtration of the process \(\xi=(\xi_i)_{i\in\mathbb{N}}\) will be denoted by: \[\mathcal{F}_0 = \{\varnothing, \Omega\} and\mathcal{F}_n = \sigma(\xi_1, \ldots, \xi_n) for n \geq 1.\]

A random variable \(\tau \colon \Omega \to \{0, 1, 2, \dots\}\) is a stopping time with respect to \((\mathcal{F}_n)_{n \geq 0}\) iff \(\{\tau \leq n\} \in \mathcal{F}_n\) for every \(n \geq 0\). In other words, \(\tau \colon \{-1,1\}^{\mathbb{N}}\to \mathbb{N}\) is a stopping time if \(\tau\) is a Borel function with the following property: if \(\omega\in\{-1,1\}^\mathbb{N}\) and \(\tau(\omega) = k\), then \(\tau(\omega')=k\) for any \(\omega'\in\{-1,1\}^{\mathbb{N}}\) with \((\omega_1,\dots,\omega_k)=(\omega'_1,\dots,\omega'_k)\). For the set of stopping times bounded by \(N\in\mathbb{N}\) we will write: \[\mathcal{S}_N = \{ \tau\colon\Omega\to\mathbb{N}|\;\tau \text{ is a stopping time with } \tau \leq N \}\]

There is a natural bijection between trees \(\mathcal{T}\) and bounded stopping times, see below.

For any \(n\in\mathbb{N}\), the map \(\mathcal{T}_n\ni T \mapsto \tau_T\in\mathcal{S}_n\) is a bijection between \(\mathcal{T}_n\) and \(\mathcal{S}_n\). Furthermore, by simple induction with respect to the height of a tree it is easy to show that \(S\sqsubseteq T\) implies \(\tau_S\leq\tau_T\) (the pathwise inequality: \(\tau_S(\omega)\leq\tau_T(\omega)\), \(\omega\in\Omega\)). Given a stopping time \(\tau\in \mathcal{S}_N\), the random variable \(S_{\tau}\) is given by: \[S_{\tau}=\sum\limits_{k=0}^{N}S_k\cdot 1_{\{\tau=k\}},\] where \(1_A\colon\Omega\to\{0,1\}\) stands for the characteristic function of the set \(A\in \mathcal{F}\). Finally, we note that \(\tau=\tau\circ (\xi_1,\xi_2,\dots)\), and we will often use notation: \[\tau(\xi_1,\xi_2,\dots):=\tau\circ (\xi_1,\xi_2,\dots).\]

In other words: \(\tau_T=1_{\{-1\}}(\xi_1)+2\cdot 1_{\{1\}}(\xi_1)\), see the illustration:

3.2 Growing trees↩︎

We will now construct the family of trees \(\{T_t\colon t\in 2\mathbb{N}+1\}\subset \mathcal{T}\) such that \(s\preceq t\) implies \(T_s\sqsubseteq T_t\), and the family \(\{P_t\colon t\in 2\mathbb{N}+1\}\) given by 13 satisfies: \[P_t=\mathcal{E}(T_t).\]

We have: \[P_1=\delta_0 and P_3=\Phi(\delta_0, \delta_0)=\frac{1}{2}\delta_{-1} + \frac{1}{2}\delta_{1},\] and \[\mathcal{E}(\bullet)=\mathcal{L}(S_0)= \delta_0=P_1 and \mathcal{E}([\bullet,\bullet])=\mathcal{L}(S_1)=P_3.\] Thus, define \(T_1 = \bullet\) and \(T_3 =[T_3^-,T_3^+]=[\bullet,\bullet]\), so \(\tau_1:=\tau_{T_1}=0\) and \(\tau_3:=\tau_{T_3}=1\) satisfy: \[P_1=\mathcal{L}(S_{\tau_1}) and P_3=\mathcal{L}(S_{\tau_3}).\]

Further construction proceeds by growing trees according to the following recursion: at each step, one subtree is left intact while the other subtree grows to become a copy of the current tree, and the successive letters from \(\{L,R\}\) determine which subtree is left intact and which one grows at each step. So far we have \[T_3=[T_3^-,T_3^+], where T_3^+=T_3^-=T_1=\bullet.\]

Recursive step. Given \(v\in T\setminus\{1\}\) and \[T_v = [T_v^-, T_v^+] \in \mathcal{T},\] define: \[\label{td} T_{vL} = [T_v,\, T_v^+], and T_{vR} = [T_v^-,\, T_v].\tag{17}\]

By the construction, if \(s\preceq t\) then \(T_s\sqsubseteq T_t\). To verify that the recursive step leads to \(\mathcal{E}(T_v) = P_{v}\), \(v\in\{L,R\}^\star\), it is enough to show that \(\mathcal{E}(T_{w(n)}) = P_{w(n)}\), \(n\in\mathbb{N}\), for any sequence \(w\in\{L,R\}^{\mathbb{N}}\). In other words, it is enough to check that 17 matches the recursion from Proposition 2.

The explicit recursive description of the stopping times \(\tau_{v}(\xi_1,\xi_2,\dots)\) goes by: if \[\tau_v(\xi_1,\xi_2,\dots) = 1 + \begin{cases} \tau^L_{v}(\xi_2,\xi_3,\dots) & \text{if } \xi_1 = -1,\\[4pt] \tau^R_{v}(\xi_2,\xi_3,\dots) & \text{if } \xi_1 = +1, \end{cases}\] then: \[\label{stop} \tau_{vL}(\xi_1,\xi_2,\dots)=1 + \begin{cases} \tau_v(\xi_2,\dots)&\text{if } \xi_1= -1 \\ \tau_{v}^R(\xi_2,\dots)&\text{if } \xi_1 = +1 \end{cases},\tag{19}\] and the formula for \(\tau_{vR}\) is analogous. The construction implies that: \(T_w \sqsubseteq T_{wL}\) and \(T_w \sqsubseteq T_{wR}\), and hence: \(\tau_{w}\leq\tau_{wL} and \tau_{w}\leq\tau_{wR}\). Moreover, the height of the tree \(|T_w|=\max(\tau_w)\) increases by at most one at each step and hence \(\tau_w\leq \ell(w)+1\), where \(\ell(w)\) denotes the length of the word \(w\). The dynamics that governs the sequence \(\{T_t\}_{t\in T}\) determines a hierarchical structure exhibiting self-similarity. Let us take a look on a few pictures which illustrate the growth of \(T_{LRLL}\), a tree which determines measure \(P_{41}=P_{LRLL}\).

4 The martingale evolution of \(P_t\)↩︎

We proceed under the notation and the assumptions of the previous sections. We have established: \(s\preceq t \Rightarrow \tau_s\leq\tau_t\), where \(P_{t}=\mathcal{L}(S_{\tau_t})\). For \(w\in\{L,R\}^\mathbb{N}\), define:\[\eta^w_t:=\tau_{w(t)}, \;\;\; t\in\mathbb{Z}_{\geq -1},\] so we have: \(\eta^w_{-1}=0\), \(\eta^w_0=1\). Define: \[\label{XM} X^w_{t}=S_{\eta^w_t},\;t\in\mathbb{Z}_{\geq -1}.\tag{20}\] When \(w\in\{L,R\}^\mathbb{N}\) is fixed, we will often write simply: \(\eta_t=\eta^w_t\) and \(X_t=X_t^w\).

4.1 Martingale property and Wald identities↩︎

Fix \(w\in\{L,R\}^\mathbb{N}\). As we have shown in the previous section, for \(0\leq s<t\) we have \[\eta_s=\tau_{w(s)}\leq\tau_{w(t)}=\eta_t\leq \ell(w_1\dots w_{t})+1=t+1,\] and thus, by Doob’s optional stopping theorem, \(X_t=S_{\eta_t}\) forms a martingale (more precisely, a martingale with respect to the stopped filtration, which forces that \(X_t\) is a martingale with respect to its natural filtration \(F_t=\sigma(X_t,\dots,X_1)\)). Additionally, by the second Wald’s identity, the variance of the measure \(P_t\) equals to the expected number of steps of the stopping time \(\tau_{t}\) which defines the measure \(P_t\) by \(P_t=\mathcal{L}(S_{\tau_t})\).

4.2 Support↩︎

Given \(P\in\Delta(\mathbb{Z})\), let \(\operatorname{supp}(P)=\{d\in\mathbb{Z}\colon P(d)>0\}\). Given \(w=w_1\dots w_n\in\{L,R\}^\star\), let \[\ell_L(w)=\sum\limits_{i=1}^n 1_{\{L\}}(w_i) and\ell_R(w)=\sum\limits_{i=1}^n 1_{\{R\}}(w_i).\] We have \(\operatorname{supp}(P_{\varepsilon})=\operatorname{supp}(P_3)=\{-1,1\}\). Fix \(w\in \{L,R\}^\star\setminus\{\varepsilon\}\). We have \(\max(\tau_w)=\ell(w)+1\). Denote \(\tau_w\wedge n:=\min(\tau_w,n)\). The stopped process \(\{S_{\tau_w\wedge n}\}_{n=0}^{\ell(w)+1}\) takes at most \(|w|_R+1\) steps to the right and \(|w|_L+1\) steps to the left (this follows from the recursive definition, 17 , 19 ). Furthermore: \(\{S_{\tau_w}=|w|_R+1\}=\{\xi_1=1,\dots,\xi_{|w|_R+1}=1\}\) and \(\{S_{\tau_w}=-(|w|_L+1)\}=\{\xi_1=-1,\dots,\xi_{|w|_L+1}=-1\}.\) Hence, \[\min(\operatorname{supp}(P_{w}))=-(|w|_L+1) and \max(\operatorname{supp}(P_{w}))=|w|_R+1,\] and \[\label{PWLR} P_{w}(-(|w|_L+1))=\left(\frac{1}{2}\right) ^{|w|_L+1} and P_{w}(|w|_R+1)=\left(\frac{1}{2}\right)^{|w|_R+1}.\tag{21}\]

4.3 Symmetries.↩︎

Given \(w\in\{L,R\}^\star\), we will write \(\overline{w}\) for the word obtained from \(w\) by interchanging \(L\) and \(R\) (for example, \(\overline{LLR}=RRL\)). By simple induction with respect to the length of the word \(w\), it is easy to see that \(S_{\tau_{\omega}}\stackrel{d}{=}-S_{\tau_{\overline{\omega}}}\), and hence: \[P_w(d)=P_{\overline{w}}(-d),\;d\in\mathbb{Z}.\]

Now, given \(w=w_1\dots w_n\), let \(\overleftarrow{w}\) denote the reversed word: \(\overleftarrow{w}=w_n\dots w_1\) ( \(\overleftarrow{\varepsilon}:=\varepsilon\)). The following symmetry may be a bit surprising: \[\label{sym2} P_w(d)=P_{\overleftarrow{w}}(d),\;w\in\{L,R\}^\star,\;d\in\mathbb{Z}.\tag{22}\] The above follows from the available results: paper [16] has shown that \(\mu_{(t)_2}=\mu_{\overleftarrow{(t)}_2}\), where \(\overleftarrow{(t)}_2\) reverses the digits in the binary representation \((t)_2\). Our representation \(t=w_1\dots w_n\) inherits this reverse property by Observation 1 (also, by the deconvolution formula). In particular, we see that the mapping \(T\ni \to P_t\in\Delta_0(\mathbb{Z})\) is not injective (the map \(T\ni t\to T_t\in\mathcal{T}\) is injective). The following theorem summarizes the symmetries.

In particular, showing \(P_{v^{2n}}(\mathbb{N})\to \frac{1}{2}\) is equivalent to \(P_{v^{2n}}(\{0\})\to 0\). The word \(v^{2n}\) plays crucial role in the variance control.

4.4 Variance analysis↩︎

Given \(P\in\Delta(\mathbb{Z})\), we will write \[E[P]=\int\limits_{\mathbb{Z}}xP(dx) and D^2[P]=\int_{\mathbb{Z}}(x-E[P])^2P(dx).\] Controlling the variance of \(\mu_t\) is a nontrivial problem, important for the analysis of the asymptotics of \(\mu_t\), see for instance [2],[4],[5],[8]. We now show that considering the poset \((T, \preceq)\) allows for very natural variance control. One of the reasons is that \((T, \preceq)\) arranges the measures \(\mu_t\) in such a way that the variance is monotone. First, note that by \(\mu_t=\mu_1\ast P_t\), we have \(D^2[\mu_t]=2+D^2[P_t]\), and we thus focus on \(P_t\). We have: \[\label{monovar} s\preceq t \Longrightarrow D^2(P_s)\leq D^2(P_{t}).\tag{23}\] Within our framework, the above is immediate: \[s\preceq t \Longrightarrow D^2(P_s)=E[\tau_s]\leq E[\tau_{t}]=D^2(P_{t}).\] The monotonicity 23 may be also concluded from the fact that for any \(\mu,\nu\in \Delta_0(\mathbb{Z})\) \[\label{variance} D^2[\Phi(\mu,\nu)]=\frac{1}{2} D^2[\mu]+\frac{1}{2} D^2[\nu]+1\tag{24}\] Define recursively: \(L^{n+1}:=L^nL\) and \(R^{n+1}:=R^nR\). Note that constant words \(L^n\) and \(R^n\) ( \(L^n= 2^{n+1}+1\), \(R^n=2^{n+2}-1\)) have the smallest variance among all \(n\)-letter words: \[\min\limits_{w\in\{L,R\}^n}D^2(P_{w})=D^2(P_{L^n})=D^2(P_{R^n}).\] By 24 , \(D^2[P_{L^{n+1}}]=\frac{1}{2}\cdot D^2[P_{L^n}]+1\), where \(D^2[P_{L^0}]:=D^2[P_{\varepsilon}]=D^2[\frac{1}{2}\delta{-1}+\frac{1}{2}\delta_1]=1\). This yields: \[\label{minD} \min\limits_{w\in \{L,R\}^k} D^2[P_w]=D^2[P_{L^k}]=D^2[P_{R^k}]=2-(\frac{1}{2})^{k}.\tag{25}\] On the other hand, quick analysis of 24 shows that the alternating word \(v^n\) ( \(v^n_{k-1}\neq v^n_{k}\) for \(1<k\leq n\)) satisfies: \[\max\limits_{w\in \{L,R\}^n} D^2[P_w] =D^2[v^n].\] By induction, one may show that: \[\; D^2[P_{v^n}] \;=\; \frac{2n}{3} \;+\; \frac{8}{9} \;+\; \frac{(-1)^{n}}{9\cdot 2^{n}},\;n\geq0, \;( v^0:=\varepsilon).\] Now, we will take a more common approach: controlling the variance by the number of blocks \(\ell_b(w)\) in the word \(w\in\{L,R\}^\star\setminus\{\varepsilon\}\). More precisely, \[\ell_b(w_1^{n_1}w_2^{n_2}...w_k^{n_k})=k, wherew_i\neq w_{i+1} andn_i>0.\] By simple induction we obtain the monotonicity: \[\label{D2} D^2[w_1^{n_1}w_2^{n_2}...w_k^{n_k}]\leq D^2[w_1^{n_1+m_1}w_2^{n_2+m_2}...w_k^{n_k+m_k}], where m_i\geq0,\;i=1,\dots,k .\tag{26}\] Again, the alternating word \(v^n\) plays the fundamental role: \(l_b(v^n)=n\) and, by 26 , \[D^2[P_{v^k}]=\min\limits_{\{w\colon l_b(w)=k\}}D^2(P_w).\]

Recall that \(\lim\limits_{n\to\infty}D^2[P_{L^n}]=\lim\limits_{n\to\infty}D^2[P_{R^n}]=2\). Now, given the alternating word \(v\in\{L,R\}^k\), from 26 , by induction with respect to \(k\), \[\label{limlim} \sup\limits_{\{w\in \{L,R\}^\star \colon \ell_b(w)=k\}}D^2[P_w]=\lim\limits_{n\to\infty} D^2[P_{v_1^nv_2^n\dots v_k^n }]=\underbrace{2 + 2 + \cdots + 2}_{k}=k\cdot 2.\tag{27}\] We summarize this subsection with the following theorem.

4.5 Asymptotic behaviour↩︎

The asymptotic behaviour of \(X^w_t\) depends on whether the variance \(D^2[X^w_t]\) is bounded or tends to infinity. It is shown in [5], [8], that the sequence \(\mu_{t_k}\) satisfies the central limit theorem (CLT) if the number of blocks in the binary representation \((t_k)_2\) goes to infinity. In this section we will put more attention to the complementary scenario \(\sup\limits_{t\in\mathbb{N}}D^2[X^w_t]<\infty\). In this setting, the martingale \(X^w_t\) is almost surely convergent.

Bounded variance. Assume that \(\sup\limits_{t\in\mathbb{N}}D^2[P_{w(t)}]<+\infty\). This is the case of the sequences \(w\in\{L,R\}^{\mathbb{N}}\) that are eventually constant. We have: \(\sup\limits_{t\in\mathbb{N}}E|X^w_t|^2<\infty\), and by Doob theorem, the almost sure limit \(X^w_{\infty}=\lim\limits_{t\to\infty}X^w_t\) exists, and equals to the \(L^2\)- norm limit. The limit can be written explicitly, and the asymptotic distributions form the family \(\{\mu_t\}_{t\in T}\cup \{\hat{\mu}_t\}\), where \(\hat{\mu}_t\) are given by the reflection: \(\hat{\mu}_t(d)=\mu_t(-d)\), \(d\in\mathbb{Z}\).

Unbounded variance. If \(w\in\{L,R\}^\mathbb{N}\) satisfies \(l_b(w_1\dots w_t)\to+\infty\), then, after the renormalization, the sequence \(\mu_{w(t)}\) converges weakly to the standard normal distribution: \[\frac{\mu_{w(t)}}{\sqrt{D^2[\mu_{w(t)}]}}\to N(0,1),\] see [8], [5] for more details. As \(\mu_t=\mu_1\ast P_t\), and \(D^2(\mu_1)=2<\infty\), we get: \[\frac{P_{w(t)}}{\sqrt{D^2[P_{w(t)}]}}\to N(0,1).\] We note that there are various results on the central limit theorem for martingales, [19], and stopped random walks, [20], although this topic is beyond the scope of the present paper.

5 The tree asymmetry and Cusick conjecture.↩︎

Considering the dynamics behind the equations 16 , it is natural to conjecture: \[\label{medP} P_t(\mathbb{N})\geq\frac{1}{2},\;t\in\mathbb{N}.\tag{30}\] Equivalently: \(P_t(-\mathbb{N})\geq\frac{1}{2}\), \(t\in\mathbb{N}\), by the symmetries. The proof of 30 is not obvious. It is worth to mention that conjecture 30 is presented in Section 3.4 of [2] along with numerical verification, and the authors note that 30 implies \(\mu_t(\mathbb{N})\geq\frac{1}{2}\) and \(\mu_t(-\mathbb{N})\geq\frac{1}{2}\) (Lemma 5 in [2]). Within our framework, this observation is the property of the limit: \[\mu_t(\mathbb{N})=\lim\limits_{n\to\infty}P_{tRL^n}(\mathbb{N}) and \hat{\mu}_t(\mathbb{N})=\lim\limits_{n\to\infty}P_{tLR^n}(\mathbb{N}),\] and equation 30 is equivalent to the median-preserving property of the martingale: \[\label{medPP} \mathbb{P}[X^w_t\geq 0]\geq\frac{1}{2} and \mathbb{P}[X^w_t\leq 0]\geq\frac{1}{2}, for w\in\{L,R\}^\mathbb{N},\;t\in\mathbb{N}.\tag{31}\] If the above holds true, then by our hierarchical construction the stopped random walk \(X^w_t\) splits the mass of every node of the tree in such a way that the median of the attached subtree is preserved. Hence, by 21 and by the construction:

The weak inequalities 30 /31 seem to be not sufficient to force the strong inequality from the Cusick problem. Based on the tree dynamics developed in this paper, we propose a natural generalization of Cusick conjecture. Fix \(w\in\{L,R\}^\mathbb{N}\). At the beginning, the tree \(T_{w(0)}=[\bullet,\bullet]\) is symmetric, and \(P_{w(0)}=\frac{1}{2}\delta_{-1}+\frac{1}{2}\delta_1\). Next, the first letter introduces the asymmetry: \[P_{L}(\mathbb{N})=\frac{3}{4}>\frac{1}{2} and P_{R}(-\mathbb{N})=\frac{3}{4}>\frac{1}{2}.\] We conjecture that the above asymmetry persists during the whole evolution process:

In words: once the tree begins to grow, one side becomes heavier than \(\frac{1}{2}\), and it remains so throughout the whole process. The Cusick conjecture is the special case of this claim:

Coming back to the language of binary digits, by Observation 1:

Our numerical experiments support ?? (and 30 ). Let \(T[3,K]:=\{s\in T | 3\leq s\leq K\}\). For \(K=12\;000\;001\), we have verified that the global minima of the function \[V\colon T[3,K] \ni t \longmapsto \sum\limits_{d=0}^{\infty}P_t(\{d\}) \in [0,1]\] satisfy \[V(t)=\frac{1}{2}andW_1(t)=R,\] where \(t=W_1(t)...W_k(t)\in\{L,R\}^\star\). More precisely, the minimum \(V(t)=\frac{1}{2}\) is attained at \(982\) odd integers with \(3\leq t\leq12 000 001\) (and the second digit in the binary representation is always "one"). Below we list the first few minimizers. While the symmetries provide some insight, a general pattern for finding \(t\) with \(V(t)=\frac{1}{2}\) is not obvious.

3pt

References↩︎