2. Existence of the limiting distribution

To prove the ergodicity of the Markov chain $\{Z_n\}_{n\ge 0}$ , we will make use of the following result.

For each $z=(z_1,z_2\ldots,z_d)\in \mathcal{S}_d$ , we define $z_{0}=1-z_1-z_2-\cdots-z_d$ . Note that the set of all $(z_0,z_1,z_2\ldots,z_d)$ , where $(z_1,z_2\ldots,z_d)\in {\mathcal S}_d$ , constitutes the standard d-simplex in $\mathbb{R}^{d+1}$ .

Figure 1. Illustration of $V_j$ , $j=0,1,2$ in case $d=2$ .

For $j=0,1,\ldots,d$ define

\[V_j= \{z=(z_1,\ldots, z_d)\in\mathcal{S}_d\colon 1-\delta\le z_j\le 1 \}.\]

In particular,

\[V_0=\Bigg\{z=(z_1,\ldots, z_d)\in\mathcal{S}_d\colon \sum_{j=1}^d z_j\le \delta \Bigg\}.\]

For each $x=(x_1,x_2,\ldots,x_d)\in (0,1)^d$ , also define $T\colon (0,1)^d\to\mathcal{S}_d^o$ by setting

\[T(x)=\Bigg(x_1\prod_{j=2}^d (1-x_j),\ x_2\prod_{j=3}^d (1-x_j), \ldots, x_{d-1}(1-x_d),\ x_d\Bigg).\]

Note that T is a homeomorphism from $(0,1)^d$ to $\mathcal{S}_d^o$ , and its inverse $T^{-1}$ for each

\[z=(z_1,\ldots,z_d)\in \mathcal{S}_d^o\]

is given by

\[T^{-1}(z) = \bigg(\dfrac{z_1}{ 1-\sum_{2\leq j\leq d}z_j},\ \dfrac{z_2}{ 1-\sum_{3\leq j\leq d}z_j}, \ldots , \dfrac{z_{d-1}}{1-z_d},\ z_d\bigg).\]

Let $z=(z_1,\ldots,z_d)$ , $u=(u_1,\ldots,u_d)\in\mathcal{S}_d$ , $z_0=1-\sum_{k=1}^d z_k$ , and $u_0=1-\sum_{k=1}^d u_k$ . For each $j=1,2,\ldots,d$ we define the following functions:

\begin{align*}R_j(u)&=(u_0,u_1,\ldots,u_{j-1}, u_{j+1},u_{j+2},\ldots,u_d),\quad j=0,1,\ldots,d,\\*G_z(u)&= (u_0z_1+u_1,u_0z_2+u_2,\ldots,u_0z_d+u_d ).\end{align*}

If $z_0\neq 0$ then the map $G_z$ is invertible; moreover, its inverse can be computed as

\[G_z^{-1}(u)=\bigg( u_1-\dfrac{z_1u_0}{z_0}, u_2-\dfrac{z_2u_0}{z_0},\ldots,u_d-\dfrac{z_d u_0}{z_0} \bigg).\]

For some two real numbers s and t, such that $0<s<t<1$ , define

\begin{align*}K&\coloneqq \Bigg\{ (u_1,\ldots,u_d)\in\mathcal{S}_d\colon s\le\dfrac{u_j}{1-\sum_{l=j+1}^d u_l}\le t, j=1,2,\ldots,d \Bigg\}=T \big([s,t]^d\big).\end{align*}

The proof of the following lemma is given in the Appendix.

Proof. (Step 1) We define

\[V=\bigcup_{j=0}^dV_j.\]

From part (i) of Assumption 1 it follows that $\mathbb{P}(Z_1\in V\mid Z_0=z)\ge \mathbb{P}(\xi\ge 1-\delta)=\eta>0$ for all $z\in \mathcal{S}_d$ . Therefore, for all $z\in \mathcal{S}_d$ , given $Z_0=z$ , the random variable $\tau_{V}=\inf\{n\ge 1\colon Z_n\in V\}$ is stochastically dominated by a geometric random variable with parameter $\eta$ , thus yielding

\[\mathbb{P}(\tau_V>n\mid Z_0=z)\le (1-\eta)^n.\]

Hence conditions (a) and (b) from the statement of Proposition 1 are satisfied.

(Step 2) Throughout the rest of the proof we let Const. denote some positive constant. From the definition of $\{Z_n\}_{n\ge 0}$ , we observe that

\begin{align*}Z_d = \zeta_0 Z_0&+ \zeta_1 \Theta_0+\zeta_2\Theta_1+\cdots + \zeta_d\Theta_{d-1},\end{align*}

where

\begin{align*} (\zeta_{1},\ldots,\zeta_{d})&\coloneqq T(\xi_0,\ldots,\xi_{d-1}),\\* \zeta_0 &\coloneqq \prod_{j=0}^{d-1}(1-\xi_j)=1-\sum_{j=1}^d \zeta_j.\end{align*}

For $1\le k\le d$ and $0\le j_1<j_2<\cdots<j_k\le d$ , define

\[U_{j_1j_2\cdots j_{k}}\coloneqq \{z=(z_1,z_2,\ldots,z_d)\in \mathcal{S}_d \colon z_{j_1}+z_{j_2}+\cdots+z_{j_k}\le \delta \}.\]

Let $B\in \mathcal{B}(\mathcal{S}_d)$ . Then, if $Z_0=z\in V_0$ and $\Theta_{0}=E_1, \Theta_{1}=E_2,\ldots, \Theta_{d-1}=E_d$ , then $Z_{j}\in U_{j+1,j+2,\ldots,d}$ for $j=0,1,\ldots,d$ . Therefore, from part (ii) of Assumption 1 it follows that

(1) \begin{align}&\mathbb{P} (Z_d\in B\mid Z_0=z) \notag \\[5pt] & \quad \ge \mathbb{P} (Z_d\in B\cap K, (\Theta_{0},\Theta_{1},\ldots,\Theta_{d-1})=(E_1,E_2,\ldots,E_d)\mid Z_0=z ) \notag \\[5pt] & \quad \ge\Bigg[\prod_{l=1}^d \inf_{z\in U_{l,l+1,\ldots,d}}\Bigg(\sum_{j=l}^dp_j(z) \Bigg)\Bigg]\times \mathbb{P}(\zeta_0 z + \zeta_1 E_1+\cdots+\zeta_{d} E_{d} \in B\cap K ) \notag \\[5pt] & \quad \ge \varepsilon^d \mathbb{P}((\zeta_0 z_1+\zeta_1, \zeta_0 z_2+\zeta_2,\ldots,\zeta_0 z_d+\zeta_d)\in B\cap K) \notag \\[5pt] & \quad = \varepsilon^d \mathbb{P}((\zeta_1,\ldots,\zeta_d)\in G^{-1}_z(B\cap K))=\varepsilon^d \mathbb{P}((\xi_0,\ldots,\xi_{d-1})\in T^{-1}\circ G^{-1}_z(B\cap K)).\end{align}

(Step 3) For $B\in \mathcal{B}(\mathcal{S}_d)$ and $z\in V_0$ , from part (iii) of Assumption 1 and Lemma 1, we have

(2) \begin{equation}\mathbb{P} ((\xi_0,\xi_1,\ldots,\xi_{d-1})\in T^{-1}\circ G^{-1}_z(B\cap K)) \ge c^d \lambda_d (T^{-1}\circ G^{-1}_z(B\cap K)).\end{equation}

We shall demonstrate below that

(3) \begin{equation} \lambda_d (T^{-1}\circ G^{-1}_z(B\cap K)) \ge \lambda_d(B\cap K).\end{equation}

Indeed, for any injective continuously differentiable map $Q\colon K\to [0,1]^d$ and any measurable subset $A\subset K$ ,

(4) \begin{equation}\lambda_d(Q(A))\ge \inf_{u\in A}\bigg|\det\bigg(\dfrac{\partial}{\partial u} Q(u)\bigg)\bigg|\cdot \lambda_d(A).\end{equation}

We also observe that

\begin{align*}\det\bigg(\dfrac{\partial}{\partial u} G_z^{-1}(u)\bigg) & =\det\begin{pmatrix}1+\dfrac{z_1}{z_0} && \quad \dfrac{z_1}{z_0} && \quad \dfrac{z_1}{z_0}&& \quad \cdots && \quad \dfrac{z_1}{z_0}\\[15pt] \dfrac{z_2}{z_0} && \quad 1+\dfrac{z_2}{z_0} && \quad \dfrac{z_2}{z_0} && \quad \cdots && \quad \dfrac{z_2}{z_0}\\[15pt] \vdots && \quad \vdots && \quad \ddots && \quad \cdots && \quad \vdots \\[15pt] \dfrac{z_{d-1}}{z_0} && \quad \cdots & & \dfrac{z_{d-1}}{z_0} && \quad 1+\dfrac{z_{d-1}}{z_0} && \quad \dfrac{z_{d-1}}{z_0}\\[15pt] \dfrac{z_d}{z_0} && \quad \cdots && \quad \dfrac{z_d}{z_0} && \quad \dfrac{z_d}{z_0} && \quad 1+\dfrac{z_d}{z_0}\end{pmatrix}\displaybreak\\ & =\det\begin{pmatrix}1+\dfrac{z_1}{z_0}& \quad -1 & \quad -1 & \quad -1 & \quad \cdots & \quad -1\\[15pt] \dfrac{z_2}{z_0} & \quad 1 & \quad 0 & \quad 0 & \quad \cdots & \quad 0\\[15pt] \dfrac{z_3}{z_0} & \quad 0 & \quad 1 & \quad 0 & \quad \cdots & \quad 0\\[10pt] \vdots & \quad \vdots & \quad \vdots & \quad \ddots & \quad \cdots & \quad \vdots \\[5pt] \dfrac{z_{d-1}}{z_0} & \quad 0& \quad \cdots & \quad 0 & \quad 1 & \quad 0\\[15pt] \dfrac{z_d}{z_0} & \quad 0 & \quad \cdots & \quad 0 & \quad 0 & \quad 1\end{pmatrix}\\[8pt] & =1+\dfrac{z_1}{z_0}+\dfrac{z_2}{z_0}+\cdots+\dfrac{z_d}{z_0}\\[6pt] & =\dfrac{1}{z_0}\\[6pt] & \ge 1,\end{align*}

where the second matrix is obtained from the first one by subtracting the first column from each of the remaining columns, and then we use the Schur determinant identity, i.e.

\[\det {\begin{pmatrix}C&\quad D\\[3pt] E& \quad F\end{pmatrix}}=\det(F)\cdot \det(C-DF^{-1}E)\]

when F is invertible; here F is the $d-1$ square identity matrix, $C=[1+z_1/z_0]$ , etc. Furthermore,

\begin{align*}& \det\bigg(\dfrac{\partial}{\partial v} T^{-1}(v)\bigg)\\ &\quad =\det\begin{pmatrix}\dfrac{1}{1-\sum_{j=2}^d v_j} & \quad \dfrac{v_1}{\big(1-\sum_{j=2}^d v_j\big)^2} & \quad \dfrac{v_1}{\big(1-\sum_{j=2}^d v_j\big)^2} & \quad \cdots & \quad \dfrac{v_1}{\big(1-\sum_{j=2}^d v_j\big)^2} \\[18pt] 0 & \quad \dfrac{1}{1-\sum_{j=3}^d v_j} & \quad \dfrac{v_2}{\big(1-\sum_{j=3}^d v_j\big)^2} & \quad \cdots & \quad \dfrac{v_2}{\big(1-\sum_{j=3}^d v_j\big)^2} \\[15pt] \vdots & \quad \vdots & \quad \ddots & \quad \cdots & \quad \vdots \\[5pt] 0 & \quad \cdots & \quad 0 & \quad \dfrac{1}{1-v_d} & \quad \dfrac{v_{d-1}}{(1-v_d)^2}\\[15pt] 0& \quad \cdots & \quad 0 & \quad 0 & \quad 1\end{pmatrix}\\[5pt] &\quad=\Bigg[ \prod_{j=1}^d \Bigg(1- \sum_{l=j+1}^d v_l\Bigg)\Bigg]^{-1}\\[5pt] &\quad \ge 1.\end{align*}

Therefore inequality (3) is obtained by applying (4) to the map $Q=T^{-1}\circ G^{-1}_z$ .

Combining (1), (2), and (3), we conclude that for each $B\in \mathcal{B}(\mathcal{S}_d)$ and $z\in V_0$

(5) \begin{equation}\mathbb{P} (Z_d\in B\mid Z_0=z)\ge \text{Const.}\ \lambda_d (B\cap K).\end{equation}

(Step 4) For each $k\in \{1,2,\ldots,d\}$ , $B\in \mathcal{B}(\mathcal{S}_d)$ , and $z\in V_k$ , we have

\begin{align*}& \mathbb{P}(Z_d\in B\mid Z_0=z) \\[5pt] & \quad \ge \mathbb{P}(Z_d\in B\cap (K), (\Theta_{0},\ldots,\Theta_{d-1})= (E_0,E_1,\ldots,E_{k-1},E_{k+1},\ldots, E_{d}) \mid Z_0=z)\\[5pt] & \quad \ge \text{Const.}\ \mathbb{P}(R_k^{-1}\circ G_{R_k(z)}(\zeta_1,\zeta_2,\ldots,\zeta_d) \in B\cap K )\\[5pt] & \quad =\text{Const.}\ \mathbb{P}( (\zeta_1,\ldots,\zeta_{d})\in G_{R_k(z)}^{-1}\circ R_k(B\cap K ) )\\[5pt] & \quad =\text{Const.}\ \mathbb{P}( (\xi_0,\xi_1,\ldots,\xi_{d-1})\in T^{-1} \circ G_{R_k(z)}^{-1}\circ R_k(B\cap K ) ),\end{align*}

where we use the fact that, for $u\in \mathcal{S}_d$ and $z\in V_k$ ,

\[R_k^{-1}(G_{R_k(z)}(u))=({u_0}{z_1} + {u_2}, \ldots ,{u_0}{z_{k - 1}} + {u_k},{u_0}{z_k},{u_0}{z_{k + 1}} + {u_{k + 1}},\ldots,{u_0}{z_d} + {u_d}).\]

Similarly to the inequalities (2) and (3), we have

\begin{align*}\mathbb{P} ( (\xi_0,\xi_1,\ldots,\xi_{d-1})\in T^{-1} \circ G_{R_k(z)}^{-1}\circ R_k(B\cap K) )\ge \text{Const.}\ \lambda_d(B\cap K).\end{align*}

It follows that for each $B\in \mathcal{B}(\mathcal{S}_d)$ , $k=1,2,\ldots,d$ and $z\in V_k$ ,

(6) \begin{equation} \mathbb{P} (Z_d\in B|Z_0=z)\ge \text{Const.}\ \lambda_d (B\cap K ).\end{equation}

Next, we define the probability measure $\varphi$ as

\begin{align*}\varphi(B)=\dfrac{\lambda_d (B\cap K)}{\lambda_d (K )}\end{align*}

for each $B\in \mathcal{B}(\mathcal{S}_d)$ . From (5) and (6), we can conclude that condition (c) in Proposition 1 is verified.

(Step 5) For each $B\in \mathcal{B}(\mathcal{S}_d)$ and $z\in V$ ,

\begin{align*}\mathbb{P}(Z_{d+1}\in B\mid Z_0=z)& \ge \mathbb{P}(Z_{d+1}\in B, Z_1\in V |Z_0=z)\\[3pt] &= \mathbb{P}(Z_{d+1}\in B\mid Z_1\in V,Z_0=z)\cdot \mathbb{P}(Z_1\in V\mid Z_0=z) \\[3pt] &\ge \eta \mathbb{P}(Z_{d+1}\in B\mid Z_1\in V )\\[3pt] &\ge \text{Const.}\ \lambda_d (B\cap K).\end{align*}

Since $\gcd\{d,d+1\}=1$ , condition (d) in Proposition 1 is also fulfilled. □

3. Beta walks with linearly place-dependent probabilities

Suppose that the conditions of Assumption 1 are fulfilled. Since convergence in total variation implies convergence in distribution, as $n\to\infty$ , $Z_n$ converges in distribution to a random vector Z having the invariant measure. By the definition of the invariant measure

(7) \begin{equation}Z\overset{d}{=} (1-\xi) Z + \xi \Theta,\end{equation}

where $\Theta$ is a discrete random vector satisfying

(8) \begin{equation}\mathbb{P}(\Theta= E_j\mid Z=z) = p_j(z),\quad j=0,1,\ldots,d,\end{equation}

and $\xi$ is independent of Z and $\Theta$ .

Lemma 2. Assume that

1. • $p=(p_1,p_2,\ldots, p_d)$ is a Borel-measurable probability choice function and $\Theta$ satisfies (8),

2. • $\xi$ is independent of Z and $\Theta$ ,

3. • Z and $\xi$ have the probability density functions f and g respectively (with respect to Lebesgue measures $\lambda_d$ and $\lambda_1$ ).

Then (7) holds if and only if f and g satisfy the following equation:

(9) \begin{equation}f(z)=\sum_{j=0}^d T_j(z) \quad \lambda_d\hbox{-}{a.e.\ on}\ \mathcal{S}_d,\end{equation}

where

\begin{align*}T_0(z_1,z_2,\ldots,z_d)&=\int_{z_1+z_2+\cdots+z_d}^1\dfrac{1}{u^d}\, f\bigg(\dfrac{z_1}{u},\dfrac{z_2}{u},\ldots,\dfrac{z_d}{u}\bigg)p_0\bigg( \dfrac{z_1}{u},\dfrac{z_2}{u},\ldots,\dfrac{z_d}{u}\bigg)g(1-u)\,\text{d} u,\\[5pt] T_j(z_1,z_2,\ldots,z_d)&=\int_{1-z_j}^1\dfrac{1}{u^d} f\bigg(\dfrac{z_1}{u},\ldots, \dfrac{z_{j-1}}{u},\dfrac{z_j-1+u}{u},\dfrac{z_{j+1}}{u},\ldots,\dfrac{z_d}{u}\bigg)\\[5pt] & \quad\,\times p_j\bigg(\dfrac{z_1}{u},\ldots, \dfrac{z_{j-1}}{u},\dfrac{z_j-1+u}{u},\dfrac{z_{j+1}}{u},\ldots,\dfrac{z_d}{u}\bigg)g(1-u)\,\text{d} u\end{align*}

for $j=1,2,\ldots,d$ . (The integrals above are understood in the Lebesgue sense.)

Proof. Denote $\tilde Z=(1-\xi) Z + \xi \Theta$ . For each $z\in \mathcal{S}_d$ , we have

(10) \begin{align}\mathbb{P}(\tilde Z\le y)& =\int_0^1 \sum_{j=0}^d\mathbb{P}( u Z + ({1-u}) \Theta\le {y}, \Theta=E_j) g(1-u) \,\text{d} u \notag \\*& = \sum_{j=0}^d \int_{\mathcal{S}_d\times [0,1]}\textbf{1}_{\{ z \le {{u}^{-1}}(y-(1-u)E_j) \}}f(z)p_j(z)g(1-u) \,\text{d} z\,\text{d} u,\end{align}

where for $y=(y_1,y_2,\ldots,y_d)$ , $z=(z_1,z_2,\ldots,z_d)\in \mathcal{S}_d$ , we write $z\le y$ if $z_j\le y_j$ for all $j=1,2,\ldots,d$ .

For each $j\in \{0,1,\ldots, d\}$ , $u\in(0,1)$ , and $y\in \mathcal{S}_d^o$ , changing the variable $x=\varphi(z)\coloneqq uz+(1-u)E_j$ we have

(11) \begin{align} &\int_{\mathcal{S}_d}\textbf{1}_{\{z \le{{u}^{-1}}(y-(1-u)E_j) \}}f(z)p_j(z)\,\text{d} z \notag \\[5pt] & \quad =\int_{\varphi(\mathcal{S}_d)}\textbf{1}_{\{ x \le y \}}f(\varphi^{-1}(x))p_j(\varphi^{-1}(x))\textsf{D} \varphi^{-1}(x) \,\text{d} x \notag\\[5pt] &\quad =\int_{\{x\in \mathcal{S}_d \colon 0 \le x\le y, 1-u\le x_j\le 1\}}\dfrac{1}{u^d}f\bigg( \dfrac{1}{u}(x-(1-u)E_j) \bigg)p_j\bigg( \dfrac{1}{u}(x-(1-u)E_j) \bigg) \,\text{d} x,\end{align}

where $\textsf{D}\varphi^{-1}$ denotes the Jacobian of $\varphi^{-1}$ . Combining (10) and (11), and applying Fubini’s theorem, we obtain

\begin{align*} &\mathbb{P}(\tilde Z\le y)\\*&\ =\int_{\{x\in \mathcal{S}_d\ \colon 0\le x\le y \}}\Bigg[\sum_{j=0}^d\int_{1-x_j}^1 \dfrac{1}{u^d}f\bigg( \dfrac{1}{u}(x-(1-u)E_j) \bigg)p_j\bigg( \dfrac{1}{u}(x-(1-u)E_j) \bigg) g(1-u) \,\text{d} u\Bigg] \,\text{d} x.\end{align*}

Therefore

\begin{align*}\tilde{f}(z) \coloneqq \sum_{j=0}^d\int_{1-z_j}^1 \dfrac{1}{u^d} f\bigg( \dfrac{1}{u}(z-(1-u)E_j) \bigg) p\bigg( \dfrac{1}{u}(z-(1-u)E_j) \bigg) g(1-u) \,\text{d} u = \sum_{j=0}^d T_j(z)\end{align*}

is a probability density function of $\tilde Z$ , which is unique up to a set of measure zero. Hence, $f(z)=\tilde f(z)$ for almost all $z\in \mathcal{S}_d$ , and the lemma is thus proved. □

Proof. Let f and g, respectively, be the probability density functions of

\[ \text{Dirichlet}(\beta_1\gamma,\beta_2\gamma,\ldots,\beta_d\gamma,\beta_{d+1}\gamma)\quad\text{and}\quad \text{Beta}(1,\gamma). \]

It suffices to check that f and g satisfy the integral equation (9).

We have

\begin{align*}T_0(z_1,\ldots,z_d) &= \dfrac{\Gamma \big(\gamma \sum_{j = 1}^{d + 1} \beta_j\big)}{\prod_{j = 1}^{d + 1} \Gamma (\beta_j\gamma )}\prod_{j = 1}^d z_j^{\beta _j\gamma - 1}\int_{\sum_{j = 1}^d z_j}^1 \bigg( u - \sum_{j = 1}^d z_j \bigg)^{\gamma\beta_{d + 1} - 1} u^{-\gamma \big(\sum_{j = 1}^{d + 1} \beta_j - 1 \big)-1}\\[6pt] & \quad\, \times\Bigg[\gamma\beta_{d+1} u -\gamma\Bigg(\sum_{j=1}^{d+1}\beta_j-1\Bigg)\Bigg(u-\sum_{j = 1}^d z_j\Bigg)\Bigg]\,\text{d} u\\[6pt] &=\dfrac{\Gamma \big(\gamma \sum_{j = 1}^{d + 1} \beta_j\big)}{\prod_{j = 1}^{d + 1} \Gamma (\beta_j\gamma )} \Bigg(1-\sum_{j=1}^d z_j \Bigg)^{\beta_{d+1}\gamma}\prod_{j=1}^d z_j^{\beta_j\gamma-1},\end{align*}

where we use the fact that

\[\int_z^1 u^{-b-1} (u-z)^{a-1} [a u-b (u-z)] \,\text{d} u=(1-z)^a.\]

Similarly, for $k=1,2,\ldots,d$ , we also obtain that

\[T_k(z_1,\ldots,z_d)=\dfrac{\Gamma\big(\gamma\sum_{j=1}^{d+1}\beta_j\big)}{\prod_{j=1}^{d+1}\Gamma(\beta_j \gamma)}\Bigg(1-\sum_{j=1}^d z_j \Bigg)^{\beta_{d+1}\gamma-1}z_k\prod_{j=1}^d z_j^{\beta_j\gamma-1}.\]

Therefore

\begin{equation*} \sum_{k=0}^dT_k(z_1,\ldots,z_d)=\dfrac{\Gamma\big(\gamma\sum_{j=1}^{d+1}\beta_j\big)}{\prod_{j=1}^{d+1}\Gamma(\beta_j \gamma)}\Bigg(1-\sum_{j=1}^d z_j \Bigg)^{\beta_{d+1}\gamma-1}\prod_{j=1}^d z_j^{\beta_j\gamma-1}=f(z_1,z_2,\ldots,z_d).\end{equation*}

□

We want to conclude this section with the following observations.

1. • If $d=1$ , then $p_1(z)=\beta_1(1-z)+(1-\beta_2)z$ . This is, in fact, the one-dimensional case considered by McKinlay and Borovkov in [Reference McKinlay and Borovkov7].

2. • If $d\ge 1$ and $\sum_{j=1}^{d+1}\beta_j=1$ , then we obtain the model considered by Sethuraman in [Reference Sethuraman10].

4. Random walks in [0, 1] based on urn-type schemes

Let $h\colon [0,1]\to\mathbb{R}_+$ be some non-random measurable function. In this section we will study a random walk on the unit interval $\mathcal{S}_1=[0,1]$ with the following properties.

1. (1) At time $n=0,1,2,\ldots,$ the system is characterized by $Z_n\in [0,1]$ (location of the particle) and two positive numbers $L_n$ and $R_n$ . We assume that $R_0=L_0=1$ .

2. (2) At time $n+1$ , with probability ${{{L_n}/{(L_n+R_n)}}}$ the quantity $L_n$ increases by $h(Z_n)$ , i.e. a function of the distance from 0 to the current position of the particle, and then the particle jumps to a new location $Z_{n+1}$ , which is uniformly distributed on the interval $(0,Z_n)$ . With the complementary probability ${{{R_n}/{(L_n+R_n)}}}$ , the quantity $R_n$ increases by $h(1-Z_n)$ , i.e. a function of the distance from 1 to the current position of the particle, and then the particle jumps to a new location $Z_{n+1}$ , uniformly distributed on the interval $(Z_n,1)$ .

One can think of $L_n$ and $R_n$ as numbers of two different kinds of balls in an urn, and the direction of the walk is governed by the kind of ball that is drawn randomly from the urn at time n. The number of balls of the chosen type then increases by yet another random quantity, depending on the position of the walk. The number of balls in our model can, in general, be non-integer; however, this is allowed for the generalized Pólya urn models.

Formally, we can write the model as the following recursion: let $Z_0\in(0,1)$ be some non-random quantity, and for $n=1,2,\ldots$ let

(12) \begin{equation}\begin{aligned}Z_{n}&= Z_{n-1} \xi_n\cdot \textbf{1}_{\{U_{n}<{{{L_{n-1}}/{(L_{n-1}}}+R_{n-1})}\}}+[Z_{n-1}+(1-Z_{n-1})\,\xi_n]\cdot \textbf{1}_{\{U_n\ge {{{L_{n-1}}/{(L_{n-1}}}+R_{n-1}})\}},\\[5pt] L_n&= L_{n-1} +h(Z_{n-1})\cdot \textbf{1}_{\{U_n<{{{L_{n-1}}/{(L_{n-1}}}+R_{n-1}})\}},\\[5pt] R_n&= R_{n-1}+h (1-Z_{n-1})\cdot \textbf{1}_{\{U_n\ge {{{L_{n-1}}/{(L_{n-1}}}+R_{n-1}})\}},\end{aligned}\end{equation}

where $\{\xi_n,U_n\}_{n=1}^\infty$ is a set of i.i.d. uniform U[0, 1] random variables. Since the probabilities of jumps to the left (and right, respectively) depend on $(L_n, R_n)$ , the distribution of $Z_{n+1}$ is generally dependent on the whole history of the random walk up to time n. Also, let

\begin{align*}\mathcal{F}_n&=\sigma(U_1,\ldots,U_n,\xi_1,\ldots,\xi_n),\\[3pt] \mathcal{G}_n&=\sigma(U_1,\ldots,U_n,\xi_1,\ldots,\xi_{n-1}),\end{align*}

and note that $Z_n$ is $\mathcal{F}_n$ -measurable, while $L_n$ and $R_n$ are $\mathcal{G}_n$ -measurable.

If $h(x)\equiv 0$ , then $L_n$ and $R_n$ do not change with time, and $Z_n$ is a Markov chain satisfying Theorem 2 with $\gamma=1$ and

\[p\equiv p_1\equiv \dfrac{R_0}{L_0+R_0},\]

so $Z_n$ converges in distribution to

\[\text{Beta}\bigg(\dfrac{R_0}{L_0+R_0},\dfrac{L_0}{L_0+R_0}\bigg).\]

If $h(x)\equiv \beta$ for some constant $\beta>0$ , then the process $(L_n,R_n)$ is the classical Pólya urn. We conjecture that under some regularity conditions on the function h, the random walk $Z_n$ converges either almost surely to a Bernoulli random variable, or weakly to some non-trivial distribution with full support on [0, 1] (compare with Section 2.1 in [Reference Diaconis and Freedman3]). Even though we were not able to deal with the general case, there is one non-trivial situation where we have explicit results, as follows.

In the remaining part of this section we consider only the case where

\[h(x)=x,\quad x\in [0,1].\]

It turns out that even in this seemingly ‘simple’ case, there are challenges to rigorously obtaining the limiting distribution (see Theorem 3 below).

Proof. First of all, observe that the probability that the sequence $Z_n$ eventually becomes monotone is zero, namely

\[\mathbb{P}(\exists N\colon Z_{n+1}\le Z_n\ {\text{for all }} n\ge N)=0\quad\text{and}\quad\mathbb{P}(\exists N\colon Z_{n+1}\ge Z_n\ {\text{for all }} n\ge N)=0.\]

Since $R_n$ is non-decreasing in n and $L_n\le L_0+n$ , we have

\[\mathbb{P}(Z_{n+1}\in(Z_n,1)\mid \mathcal{F}_n)=\dfrac{R_n}{L_n+R_n}\ge\dfrac{R_0}{L_n+R_0}\ge\dfrac{R_{0}}{R_0 +L_0+n}.\]

Since

\[\sum_{n=1}^{\infty} \dfrac{R_0}{R_0 +L_0+n}=\infty,\]

by Lévy’s extension to the Borel–Cantelli lemma the event in the above display happens infinitely often with probability 1, hence there are infinitely many ns for which $Z_n$ decreases. By the identical argument, $Z_n$ cannot eventually become increasing.

Let us prove part (a) now. We know that $Z_n$ makes a.s. infinitely many steps to the left as well as to the right. Hence there exists a sequence of finite stopping times with respect to the filtration $\mathcal{G}$ :

\begin{align*}\tau_1&=0,\\[4pt] \eta_i&=\inf\{n>\tau_i\colon Z_n\ge Z_{n-1}\},\\[4pt] \tau_{i+1}&=\inf\{n>\eta_{i}\colon Z_n < Z_{n-1}\},\end{align*}

for $i=1,2,\ldots.$ Moreover,

\[\tau_1<\eta_1<\tau_2<\eta_2<\cdots,\]

$\tau_n,\eta_n\to\infty$ as $n\to\infty$ , and

\begin{align*}Z_{n}&<Z_{n-1}\quad \text{ if } n\in[\tau_i,\eta_i-1],\\[4pt] Z_{n}&\ge Z_{n-1}\quad \text{ if } n\in[\eta_i,\tau_{i+1}-1],\end{align*}

for each $i=2,3,\ldots$ (note that, in fact, the probability of the event $Z_n=Z_{n-1}$ is zero).

Observe that, for each $k\ge 1$ and $1\le \ell\le k-1$ ,

\begin{align*}& \{\eta_i=k,\ \tau_i=k-\ell\}\\[6pt] &\quad =\{Z_k\ge Z_{k-1},\ Z_{k-1}< Z_{k-2}<\cdots<Z_{k-\ell}, \tau_i=k-\ell\}\\[6pt] & \quad =\bigg\{U_k\ge \dfrac{ L_{k-1}}{L_{k-1}+R_{k-1}},\ U_{k-1} \lt \dfrac{ L_{k-2}}{L_{k-2}+R_{k-2}}, \ldots,U_{k-\ell+1} \lt \dfrac{ L_{k-\ell}}{L_{k-\ell}+R_{k-\ell}},\ \tau_i=k-\ell\bigg\}.\end{align*}

However, $L_{k-j}$ and $R_{k-j}$ depend only on $L_{k-j-1}$ , $R_{k-j-1}$ , $Z_{k-j-1}$ , and $U_{k-j}$ , $j=1,2,\ldots,\ell$ (see (12)). Hence the event above is $\sigma(U_1,\ldots,U_k,\xi_1,\ldots,\xi_{k-2})$ -measurable, and it is thus independent of $\xi_{k-1}$ ; as a result $V_{i+1}\coloneqq \xi_{\eta_i-1}$ is independent of

\[\mathcal{H}_i\coloneqq \sigma (U_1,U_2,\ldots,U_{\eta_i},\xi_1,\xi_2,\ldots,\xi_{\eta_i-2} ).\]

On the other hand, since $\eta_{i-1}-1\le \eta_i-2$ , $V_i$ is $\mathcal{H}_i$ -measurable. So $\{V_i\}_{i=1}^\infty$ is an i.i.d. sequence of Uniform[0, 1] random variables.

We have

\[R_{\eta_i}-R_{\eta_i-1}=1-Z_{\eta_i-1}=1-Z_{\eta_i-2} \xi_{\eta_i-1}\ge 1-\xi_{\eta_i-1}=1-V_{i+1},\]

hence, due to the monotonicity of $R_n$ ,

\[R_{\eta_i}\ge \sum_{k=1}^{i} [1-V_{k+1}].\]

By the strong law of large numbers

\[\lim_{k\to\infty} \dfrac 1k \sum_{i=1}^k [1-V_{i+1}]=\dfrac 12\quad \text{a.s.,}\]

hence

\[\liminf_{k\to\infty} \dfrac{R_{\eta_k}}{\eta_k}\ge \dfrac 12\quad\text{a.s.}\]

Next, for $i\in\mathbb{N}$ , we have

\begin{align*}L_{\tau_{i+1}-1}-L_{\eta_i-1}&=0,\\[5pt] L_{\eta_i-1}-L_{\tau_i-1}&=Z_{\tau_i-1}(1+\xi_{\tau_i}+\xi_{\tau_i}\xi_{\tau_i+1}+\cdots+\xi_{\tau_i}\xi_{\tau_i+1}\cdots\xi_{\eta_i-2})\\[5pt] &\le 1+\xi_{\tau_i}+\xi_{\tau_i}\xi_{\tau_i+1}+\cdots+\xi_{\tau_i}\xi_{\tau_i+1}\cdots\xi_{\eta_i-2}\le \tilde V_i,\end{align*}

where

\begin{align*}\tilde V_i&= [1+\xi_{\tau_i}+\xi_{\tau_i}\xi_{\tau_i+1}+\cdots+\xi_{\tau_i}\xi_{\tau_i+1}\cdots\xi_{\eta_i-2} ]\\[5pt] & \quad\, +\xi_{\tau_i}\xi_{\tau_i+1}\cdots\xi_{\eta_i-2}\tilde\xi^{(i)}_{\eta_i-1}+\xi_{\tau_i}\xi_{\tau_i+1}\cdots\xi_{\eta_i-2}\tilde\xi^{(i)}_{\eta_i-1}\tilde\xi^{(i)}_{\eta_i}\\[5pt] &\quad\, +\xi_{\tau_i}\xi_{\tau_i+1}\cdots\xi_{\eta_i-2}\tilde\xi^{(i)}_{\eta_i-1}\tilde\xi^{(i)}_{\eta_i}\tilde\xi^{(i)}_{\eta_i+1}+\cdots\\[5pt] &=1+\sum_{k=\tau_i}^{\eta_i-2} \xi_{\tau_i}\xi_{\tau_i+1}\cdots\xi_{k}+\sum_{k=\eta_i-1}^{\infty}\xi_{\tau_i}\cdots\xi_{\eta_i-2}\cdot\tilde\xi^{(i)}_{\eta_i-1}\tilde\xi^{(i)}_{\eta_i}\cdots\tilde\xi^{(i)}_{k}\end{align*}

and $\tilde\xi^{(i)}_k$ , $i,k\in\mathbb{N}$ are i.i.d. copies of $\xi$ , independent of everything else. By construction, $\tilde V_i$ is a $\tilde{\mathcal{H}_i}$ -measurable random variable, where

\[\tilde{\mathcal{H}_i}\coloneqq \sigma (U_1,U_2,\ldots,U_{\eta_i};\,\xi_1,\xi_2,\ldots,\xi_{\eta_i-2};\,\tilde\xi^{(\ell)}_k, \ell=1,2,\ldots, i,\ k\in\mathbb{N} ).\]

On the other hand, one can easily show that the variables $\xi_{\tau_{i+1}+j}$ , $\tilde{\xi}^{(i+1)}_{j+1}$ , $j=0,1,2,\ldots,$ are independent of $\tilde{\mathcal{H}_i}$ , and therefore $\tilde V_{i+1}$ is independent of $\tilde{\mathcal{H}_i}$ . Consequently, $\tilde V_i$ , $i=1,2,\ldots,$ are independent random variables with expectation

\[\mathbb{E}\Bigg[1+ \sum_{k=1}^{\infty} \Bigg(\prod_{i=1}^k \xi_i\Bigg)\Bigg]=2,\]

and hence by the strong law we have

\[\lim_{k\to\infty} \dfrac 1k \sum_{i=1}^k \tilde V_i=2\quad\text{a.s.,}\]

yielding

(13) \begin{equation}\limsup_{k\to\infty} \dfrac{L_{\eta_k}}{\eta_k}\le 2\quad\text{a.s.}\end{equation}

Combining this with (13), and taking into account that $\eta_i\to\infty$ , we get

\[\limsup_{n\to\infty} \dfrac{L_n}{R_n}\le \dfrac{2}{1/2}={4}\quad\text{a.s.}\]

Due to the symmetry, the complementary inequality can be proved identically.

Let us now prove part (b). From part (a) we obtain that a.s. either both $L_n$ and $R_n$ increase to $\infty$ , or both stay bounded, i.e. $\sup_{n\ge0}L_n<\infty$ and $\sup_{n\ge0}R_n<\infty$ for all n. Let us show that the latter case a.s. cannot happen. Again, from (a) we get that a.s. there exists a (random) N such that, for $n\ge N$ ,

\[\mathbb{P}(Z_{n+1}<Z_n| {\mathcal F}_n)=\dfrac{L_n}{L_n+R_n}=\dfrac{1}{1+R_n/L_n}>\dfrac1{5} , \quad\mathbb{P}(Z_{n+1}>Z_n| {\mathcal F}_n)=\dfrac{R_n}{L_n+R_n}>\dfrac 1{5} .\]

As a result, for $n\ge N$ , we have for $S_n=L_n+R_n$

\begin{align*}& \mathbb{P}\bigg(S_{n+1}-S_n>\dfrac 14\mid {\mathcal F}_n\bigg)\\[4pt] & \quad =\mathbb{P}\bigg(S_{n+1}-S_n>\dfrac 14\mid {\mathcal F}_n, Z_n\le \dfrac12\bigg)+\mathbb{P}\bigg(S_{n+1}-S_n>\dfrac 14\mid {\mathcal F}_n, Z_n> \dfrac12\bigg)\\[4pt] &\quad \geq\mathbb{P}\bigg(R_{n+1}-R_n>\dfrac 14\mid {\mathcal F}_n, Z_n\le \dfrac12\bigg)+\mathbb{P}\bigg(L_{n+1}-L_n>\dfrac 14\mid {\mathcal F}_n, Z_n> \dfrac12\bigg)\\[4pt] &\quad =\mathbb{P}\bigg(R_{n+1}-R_n>\dfrac 14,\ Z_{n+1}>Z_n\mid {\mathcal F}_n, Z_n\le \dfrac12\bigg)\\[4pt] &\quad \quad\, +\mathbb{P}\bigg(L_{n+1}-L_n > \dfrac 14,\ Z_{n+1}<Z_n\mid {\mathcal F}_n, Z_n> \dfrac12\bigg)\\[5pt] &\quad \geq \dfrac 12 \cdot\dfrac 15+\dfrac 12 \cdot\dfrac 15\\[6pt] &\quad =\dfrac 15>0.\end{align*}

Since $S_n$ is non-decreasing for any n, this implies that $S_n\to\infty$ a.s., contradicting the assumption that both $L_n$ and $R_n$ remain bounded. □

Lemma 4.

\[ \zeta_n\coloneqq \dfrac{L_{n}}{L_{n}+R_{n}} \]

converges almost surely to $\zeta_{\infty}\in(0,1)$ as $n\to\infty$ .

Remark 2. Lemma 3 implies only that

\[\dfrac 1{5}\le \liminf_{n\to\infty}\zeta_n\le \limsup_{n\to\infty} \zeta_n\le \dfrac{4}{5}\quad\text{a.s.}\]

Proof of Lemma 4. We introduce the quantity

\[ W_n=\bigg(\dfrac{1}{2}-\dfrac{L_n+Z_{n}}{L_{n}+R_n}\bigg)^2+\dfrac 1{L_n+R_n}\]

which will be shown to be a supermartingale. Indeed,

\begin{align*}& \mathbb{E} (W_{n+1}|\mathcal{F}_n )\\[5pt] &\quad =\dfrac{L_n}{L_n+R_n}\mathbb{E}\bigg(W_{n+1} \mid U_{n+1}<\dfrac{L_{n}}{L_n+R_n},\mathcal{F}_n \bigg)\\[5pt] &\quad\quad\, +\dfrac{R_n}{L_n+R_n}\mathbb{E}\bigg(W_{n+1} \mid U_{n+1}>\dfrac{L_n}{L_n+R_n},\mathcal{F}_n\bigg)\\[5pt] & \quad = \dfrac{L_n}{L_n+R_n}\int_{0}^{Z_n} \dfrac{1}{Z_n}\bigg[ \bigg(\dfrac{1}{2}-\dfrac{L_n+Z_n+u}{L_n+R_n+Z_n} \bigg)^2+\dfrac{1}{L_n+R_n+Z_n}\bigg]\,\text{d} u\\[5pt] & \quad\quad\, + \dfrac{R_{n}}{L_n+R_{n}}\int_{Z_n}^{1} \dfrac{1}{1-Z_n}\bigg[\bigg(\dfrac{1}{2}-\dfrac{L_n+u}{L_n+R_n+1-Z_n} \bigg)^2+\dfrac{1}{L_n+R_n+1-Z_n}\bigg]\,\text{d} u\\[5pt] &\quad = \dfrac{L_n}{L_n + R_n}\dfrac{3 ( {L_n - R_n} )^2 + 12 ( {L_n - R_n} )Z_n + 12 ( {L_n + R_n + Z_n} ) + 13Z_n^2}{12 ( L_n + R_n + Z_n )^2}\\[5pt] &\quad\quad\, + \dfrac{R_n}{L_n + R_n}\dfrac{3 ( {L_n - R_n} )^2 + 12 ( {L_n - R_n} )Z_n + 12 ( {L_n + R_n + Z_n} ) + 13(1-Z_n)^2}{12 ( L_n + R_n + 1-Z_n )^2}.\end{align*}

Substituting

\[\zeta_n=\dfrac{L_n}{L_n+R_n}\quad\text{and}\quad \varepsilon_n=\dfrac{1}{L_n+R_n},\]

or equivalently

\[L_n= \dfrac{\zeta_{n}}{\varepsilon_n}, R_n=\dfrac{1-\zeta_n}{\varepsilon_n},\]

we obtain that

(14) \begin{equation}\mathbb{E} (W_{n+1} -W_n |\mathcal{F}_n,Z_n=z )=\dfrac{\varepsilon_n \big[r_0(\zeta_n,z)+ r_1(\zeta_n,z) \varepsilon_n+\cdots +r_5(\zeta_n,z) \varepsilon_n^5\big]}{6(\varepsilon_n z+1)^2 (1+\varepsilon_n(1-z))^2},\end{equation}

where

\begin{align*}r_0(\zeta,z)&=-24z \zeta^3+36z \zeta^2+12\,\zeta^3-18z\zeta-24\zeta^2+3z+15\zeta-3\\[4pt] &=-3(2\zeta-1)^2(\zeta z+(1-z)(1-\zeta)),\\[4pt] r_1(\zeta,z)&=-30\,{z}^{2}{\zeta}^{2}-12\,z{\zeta}^{3}+30\,{z}^{2}\zeta+24\,z{\zeta}^{2}+6\,{\zeta}^{3}\\[4pt] &\quad\, -7\,{z}^{2}-38\,z\zeta-12\,{\zeta}^{2}+14\,z+13\,\zeta-7,\\[4pt] r_2(\zeta,z)&=10\,{z}^{3}\zeta-12\,{z}^{2}{\zeta}^{2}-5\,{z}^{3}-9\,{z}^{2}\zeta+7\,{z}^{2}-19\,z\zeta+4\,z+6\,\zeta-6,\\[4pt] r_3(\zeta,z)&=-z ( 6\,{z}^{3}{\zeta}^{2}-6\,{z}^{3}\zeta-12\,{z}^{2}{\zeta}^{2}-17\,{z}^{3}-12\,{z}^{2}\zeta\\[4pt] &\quad\, +6\,z{\zeta}^{2}+28\,{z}^{2}+30\,z\zeta-23\,z-6\,\zeta+12 ),\\[4pt] r_4(\zeta,z)&=-6\,{z}^{2} ( 1-z ) (z^2+2z\zeta(1-z)+1 ),\\[4pt] r_5(\zeta,z)&=-6z^4 ( 1- z )^2.\end{align*}

One can show that $\max_{x,y\in [0,1]} r_i(x,y)\le 0$ for $i=0,2,3,4,5$ . From the assertion of Lemma 3, $\varepsilon_n\to 0$ almost surely as $n\to\infty$ , and one can show that $\max_{x,y\in [0,1]} r_0(x,y)+r_1(x,y)\varepsilon \le 0$ for $0\le \varepsilon< 0.5$ . Hence $W_n$ is a supermartingale. Therefore, by Doob’s martingale convergence theorem, a.s. there exists $ W_{\infty}\coloneqq \lim_{n\to\infty} W_n$ . Observe that

\[\zeta_n\in \Bigg\{\dfrac12-\sqrt{W_n-\dfrac1{L_n+R_n}}-\dfrac{Z_n}{L_n+R_n},\dfrac12+\sqrt{W_n-\dfrac1{L_n+R_n}}-\dfrac{Z_n}{L_n+R_n}\Bigg\}.\]

On the other hand, note that

\[|\zeta_{n+1}-\zeta_n|\le \max \bigg\{\dfrac{L_n}{L_n+R_n}.\dfrac{1-Z_n}{L_{n+1}+R_{n+1}},\dfrac{R_n}{L_n+R_n}.\dfrac{Z_n}{L_{n+1}+R_{n+1}} \bigg\}\to 0\]

as $n\to\infty$ . As a result, $\limsup_{n\to\infty} \zeta_n=\liminf_{n\to\infty} \zeta_n=\!:\,\zeta_{\infty}$ almost surely. □

Proof. Suppose $\mathbb{P}(\zeta_{\infty}=1/2)<1$ . Then there exists $\varepsilon>0$ such that $\mathbb{P}(|\zeta_{\infty}-1/2|>\varepsilon)>0$ . Let us denote the stopping time

\[\tau_{m}=\inf\bigg\{n\ge m \colon \bigg|\zeta_{n}-\dfrac12\bigg|<\dfrac{\varepsilon}{2}\bigg\}.\]

Since $\mathbb{P}(|\zeta_{\infty}-1/2|>\varepsilon)>0$ , there exists m such that $\mathbb{P}(\tau_m=\infty)>0$ . Let us consider $Y_{n}=W_{n\wedge \tau_m}$ . $Y_n$ is also a supermartingale, hence there exists $Y_{\infty}=\lim_{n\to\infty}Y_n$ as well. From (14) it follows that

\begin{equation*}\mathbb{E}(W_{n+1} -W_n \mid \mathcal{F}_n)=\dfrac{1}{6}\varepsilon_n (r_0(\zeta_n,Z_n)+\varepsilon_n \rho_n),\end{equation*}

where

\begin{align*}\rho_n &=\dfrac{1}{(1+\varepsilon_n Z_n)^2 (1+\varepsilon_n(1-Z_n))^2}( {r}_1(\zeta_n,Z_n)+{r_2}(\zeta_n,Z_n)\varepsilon_n+\cdots +r_5(\zeta_n,Z_n) \varepsilon_n^4\\[6pt] & \quad\, - (1+(1-Z_n)Z_n\varepsilon_n )(2+\varepsilon_n+(1-Z_n)Z_n\varepsilon_n^2)r_0(\zeta_n,Z_n) ) .\end{align*}

Furthermore, $|\rho_n|$ is bounded by a non-random constant. This fact implies that, for $N>0$ ,

\[\mathbb{E}( W_{m+N} )-\mathbb{E}( W_{m} )=\dfrac{1}{6}\mathbb{E}\Bigg(\sum_{n=m}^{m+N} \varepsilon_n( r_0(\zeta_n,Z_n)+O(\varepsilon_n))\Bigg).\]

Therefore

(15) \begin{equation}\mathbb{E}( Y_{\infty} )-\mathbb{E}( Y_{m} )=\dfrac{1}{6}\mathbb{E}\Bigg(\sum_{n=m}^{\tau_m} \varepsilon_n(r_0(\zeta_n,Z_n)+O(\varepsilon_n))\Bigg).\end{equation}

Note that

\[\bigg|\zeta_{n}-\frac12\bigg|\ge \frac{\varepsilon}{2}\quad\text{for all $n\in[m,\tau_m)$.} \]

Hence, combining with Remark 2, it follows that on the event $\{\tau_m=\infty\}$

\[r_0(\zeta_n,Z_n)=-3 (2 \zeta_n-1)^2 ( Z_n \zeta_n+(1-Z_n)(1-\zeta_n)) \le- 3{\varepsilon^2}\min\{\zeta_n,1-\zeta_n\}\le -\dfrac{3\varepsilon^2}{13}\]

for large enough n. Since $\mathbb{P}(\tau_m=\infty)>0$ and $\varepsilon_n\ge {{{1}/{(2+n)}}}$ , the left-hand side of (15) is finite while the right-hand side is divergent. This contradiction proves the lemma. □

Proof. Let us fix a small $\varepsilon>0$ . By Lemma 5 there exists a (random) N such that

\[\dfrac{1}{2}-\varepsilon\le\dfrac{L_{n}}{L_n+R_n}\le \dfrac{1}{2}+\varepsilon\]

for all $n\ge N$ . Fix a large non-random $N_0$ . For this fixed $N_0$ we couple $\{{Z_n}\}_{n\ge 0}$ with two random walks $\{\tilde{Z_n}\}_{n\ge 0}$ and $\{\hat Z_n\}_{n\ge 0}$ defined as follows.

1. • For $0\le n \le N_0$ , set $\tilde{Z_n} = \hat Z_n =Z_{n}.$

2. • For $n\ge N_0$ , set

   \[\tilde Z_{n+1}=\begin{cases}\xi_{n+1} \tilde Z_n & \text{if} \ U_{n+1}\le \dfrac{1}{2}-\varepsilon,\\[12pt]\tilde Z_n+\xi_{n+1} (1-\tilde Z_n) & \text{if} \ U_{n+1}>\dfrac{1}{2}-\varepsilon,\end{cases}\]
   and
   \[\hat Z_{n+1}=\begin{cases} \xi_{n+1} \hat Z_n & \text{if} \ U_{n+1}\le \dfrac{1}{2}+\varepsilon,\\[12pt]\hat Z_n+\xi_{n+1} (1-\hat Z_n) & \text{if} \ U_{n+1}> \dfrac{1}{2}+\varepsilon.\end{cases}\]

Let $A_{N_0}=\{N\le N_0\}$ .

Assume that for some $n\ge N_0$ , $\hat Z_n\le Z_n\le \tilde Z_{n}$ (this is definitely true for $n=N_0$ ). We observe that on $A_{N_0}$ :

1. • When $\tilde Z_n$ chooses left, $Z_n$ also chooses left since

   \[ U_{n+1}\le \dfrac12-\varepsilon<\dfrac{L_n}{L_n+R_n}. \]
   In this case, $Z_{n+1}=\xi_{n+1}Z_n\le \xi_{n+1}\tilde Z_n = \tilde Z_{n+1}$ . When $\tilde Z_n$ chooses right, $Z_n$ might choose left or right, but we still have
   \[ Z_{n+1}\le Z_n+\xi_{n+1}(1-Z_n)\le \tilde Z_n+\xi_{n+1}(1-\tilde Z_n) = \tilde Z_{n+1}. \]

2. • When $Z_n$ chooses left, $\hat Z_n$ also chooses left since

   \[ U_{n+1}\le \dfrac{L_n}{L_n+R_n} < \dfrac12+\varepsilon. \]
   In this case, $Z_{n+1}=\xi_{n+1}Z_n\ge \xi_{n+1}\hat Z_n = \hat Z_{n+1}$ . When $Z_n$ chooses right, $\hat Z_n$ might choose left or right, but we still have
   \[ \hat Z_{n+1}\le \hat Z_n+\xi_{n+1}(1-\hat Z_n)\le Z_n+\xi_{n+1}(1- Z_n) = Z_{n+1}. \]

By induction, we obtain that on $A_{N_0}$ for all $n\ge 0$ , $\hat Z_{n}\le Z_n\le \tilde Z_{n}$ . Therefore we have

\begin{align*}\mathbb{P}(\tilde Z_n\le x,\ A_{N_0})\le \mathbb{P}(Z_n\le x,\ A_{N_0}) \le \mathbb{P}(\hat Z_n\le x,\ A_{N_0})\\[-16pt]\end{align*}

for all $n\ge0$ and $x\in [0,1]$ . On the other hand, by Theorem 2, $\tilde Z_{n}$ and $\hat Z_{n}$ converge weakly to $\text{Beta}(\frac{1}{2}+\varepsilon,\frac{1}{2}-\varepsilon)$ and $\text{Beta}(\frac{1}{2}-\varepsilon,\frac{1}{2}+\varepsilon)$ respectively, as $n\to\infty$ . Since $\varepsilon$ is arbitrarily small and $\mathbb{P}(A_{N_0})\to 1$ as $N_0\to\infty$ , the theorem is proved. □

Appendix A

Proof of Lemma 1.

(a) For $u=(u_1,\ldots,u_d)\in K$ and $z=(z_1,\ldots,z_d)\in V_0$ , define

\[v=(v_1,v_2,\ldots, v_d)\coloneqq G_z^{-1}(u).\]

Note that $u_0\le 1-u_d\le 1-\delta \le z_0$ , $z_j\le 1-z_0\le \delta$ , and thus

\[s(1-t)^{d-1} -\delta\le u_j - z_j \le v_j=u_j-\dfrac{u_0}{z_0}z_j\le u_j\le t\]

for $j=1,2,\ldots,d$ . Therefore, for $j=1,2,\ldots,d$ , we have

\begin{align*} s(1-t)^{d-1}-\delta & \le v_j\le \dfrac{v_j}{ 1-\sum_{l=j+1}^d v_l}=\dfrac{ u_j-z_j{{{u_0}/{z_0}}}}{ 1-\sum_{l=j+1}^d u_l+\sum_{l=j+1}^d z_l{{{u_0}/{z_0}}}}\\[5pt] & \le \dfrac{u_j}{ 1-\sum_{l=j+1}^d u_l}\le t.\end{align*}

This implies that $v=G_z^{-1}(u)\in K_0$ for each $u\in K$ and $z\in V_0$ , where we denote

\begin{equation*} K_0=\Bigg\{(v_1,\ldots,v_d)\in\mathcal{S}_d\colon s(1-t)^{d-1}-\delta\le\dfrac{v_j}{1-\sum_{l=j+1}^d v_l}\le t, j=1,2,\ldots,d \Bigg\}.\end{equation*}

Observe that $T^{-1}(K_0)=[s(1-t)^{d-1}-\delta,t]^d$ . Thus $T^{-1}\circ G^{-1}_z(K) \subset [s(1-t)^{d-1}-\delta,t]^d$ .

(b) For $u\in K, z\in V_k$ , let

\begin{align*} \hspace*{24pt} v&=(v_1,v_2,\ldots,\ldots,v_k)\\[4pt] & \coloneqq G_{R_k(z)}^{-1}(R_k(u))\\[4pt] &\,\,=\bigg(u_{0}-z_{0}\dfrac{u_k}{z_k}, u_1-z_1\dfrac{u_k}{z_k},\ldots,u_{k-1}-z_{k-1}\dfrac{u_k}{z_k},u_{k+1}-z_{k+1}\dfrac{u_k}{z_k},\ldots, u_{d}-z_{d}\dfrac{u_k}{z_k}\bigg).\end{align*}

Note that $z_l\le 1-z_k \le \delta$ for $l\in\{0,2,\ldots,d\}\setminus \{k\}$ and $u_{k} \le {\max\{u_d,1-u_d\}} \le {1-\delta}\le {z_k}.$ Therefore we observe the following.

1. (i) For $k+1\le j\le d$ ,

   \[\dfrac{v_j}{ 1-\sum_{l=j+1}^d v_l}=\dfrac{ u_j-z_j{{{u_k}/{z_k}}}}{ 1-\sum_{l=j+1}^d u_l+\sum_{l=j+1}^d z_l{{{u_k}/{z_k}}}} \le \dfrac{u_j}{ 1-\sum_{l=j+1}^d u_l}\le t\]

   and

   \begin{align*}\dfrac{v_j}{ 1-\sum_{l=j+1}^d v_l}& \ge v_j = u_j-z_j\dfrac{u_k}{z_k}\ge u_j-z_j\ge s(1-t)^{d-1}-\delta.\end{align*}

2. (ii) For $j=1$ , we have

   \begin{align*} \dfrac{v_{1}}{ 1-\sum_{l=2}^{d} v_l }& =\dfrac{ u_0-z_0{{{u_k}/{z_k}}}}{ u_0+\sum_{l=1}^d z_l{{{u_k}/{z_k}}}}\\[4pt] & =1-\dfrac{{u_k}}{ \big(1-\sum_{l=1}^d u_l\big)z_k+{u_k}\sum_{l=1}^d z_l}\\[4pt] & \le 1-\dfrac{u_k} { \big(1-\sum_{l=k}^d u_l\big)z_k+{u_k}}\\[4pt] & \le 1-\dfrac{u_k} { 1-\sum_{l=k+1}^d u_l }\\[4pt] &\le 1-s\end{align*}

   and

   \begin{align*}& \dfrac{v_{1}}{ 1-\sum_{l=2}^{d} v_l } \ge v_1= u_0-z_0\dfrac{u_k}{z_k}\ge (1-t)^d-\delta.\end{align*}

3. (iii) For $2\le j\le k$ ,

   \[\hspace*{-15pt}s(1-t)^{d-1}-\delta \le v_j \le \dfrac{v_j}{ 1-\sum_{l=j+1}^{d} v_l }=\dfrac{ u_{j-1}-z_{j-1}\ {u_k}/{z_k}}{ 1-\sum_{l=j}^d u_l+\sum_{l=j}^d z_l\ {u_k}/{z_k}} \le \dfrac{u_{j-1}}{ 1-\sum_{l=j}^d u_l}\le t.\]

(c) Therefore

\begin{equation*} \hspace*{78pt} v\in T \big([(1-t)^{d}-\delta,1-s]\times[s(1-t)^{d-1}-\delta,t]^{d-1}\big).\hspace*{78pt}\square\end{equation*}