Return to Answer

This answer is a detalization of a comment by Anthony Quas, according to which the problem can be restated as follows.

Consider a Markov chain on the set $[n]_0:=\{0,\dots,n\}$ with transition probabilities $p_{i,j}$ such that for $i\in[n]:=\{1,\dots,n\}$ \begin{equation} p_{i,i+1}=p_i:=\frac{n-i}n, \quad p_{i,i-1}=q_i:=\frac in=1-p_i. \end{equation} For any $j\in[n]_0$, find the probability -- say $u_j=u_{n,j}$ -- that, after starting in the state $j$, the chain will reach the state $n$ before reaching the state $0$.

We have $u_0=0$, $u_n=1$, and \begin{equation} u_j=p_j u_{j+1}+q_j u_{j-1} \tag{1} \end{equation} for $j\in[n-1]$.

Letting $h_j:=u_j-u_{j-1}$, we rewrite (1) as $q_j h_j=p_j h_{j+1}$ or, equivalently, as \begin{equation} h_{j+1}=\frac j{n-j}\,h_j, \end{equation} whence \begin{equation} h_j=h_1\prod_{i=2}^j\frac{i-1}{n-i+1}=h_1\Big/\binom{n-1}{j-1} \end{equation} for $j\in[n]$. So, \begin{equation} 1=u_n-u_0=\sum_{j\in[n]}h_j=h_1\,c_n,\quad c_n:=\sum_{j\in[n]}1\Big/\binom{n-1}{j-1}, \end{equation} and thus $h_1=1/c_n$ and for all $j\in[n]_0$ \begin{equation} u_j=\sum_{i\in[j]}h_i=\frac1{c_n}\,\sum_{i\in[j]}1\Big/\binom{n-1}{i-1}. \end{equation}

Note that for $n\ge4$ \begin{align*} c_n&=1\Big/\binom{n-1}0+1\Big/\binom{n-1}1+1\Big/\binom{n-1}{n-2}+1\Big/\binom{n-1}{n-1}+b_n \\ &=1+\frac1{n-1}+\frac1{n-1}+1+b_n, \end{align*} where \begin{equation} 0\le b_n:=\sum_{j=3}^{n-2}1\Big/\binom{n-1}{j-1}\le(n-4)\Big/\binom{n-1}2\to0 \end{equation} (as $n\to\infty$). So, $c_n\to2$, $h_1=1/c_n\to1/2$, and (by symmetry), $h_n=h_1\to1/2$. Also, for all $j\in[n-1]$ we have $h_1=u_1\le u_j\le u_{n-1}=1-h_n$.

Thus, \begin{equation} u_j=u_{n,j}\to1/2 \end{equation} uniformly over all $j\in[n-1]$.

Here is the discrete graph $\{(j,u_{30,j})\colon j\in[30]_0\}$:

This answer is a detalization of a comment by Anthony Quas, according to which the problem can be restated as follows.

Consider a Markov chain on the set $[n]_0:=\{0,\dots,n\}$ with transition probabilities $p_{i,j}$ such that for $i\in[n]:=\{1,\dots,n\}$ \begin{equation} p_{i,i+1}=p_i:=\frac{n-i}n, \quad p_{i,i-1}=q_i:=\frac in=1-p_i. \end{equation} For any $j\in[n]_0$, find the probability -- say $u_j=u_{n,j}$ -- that, after starting in the state $j$, the chain will reach the state $n$ before reaching the state $0$.

We have $u_0=0$, $u_n=1$, and \begin{equation} u_j=p_j u_{j+1}+q_j u_{j-1} \tag{1} \end{equation} for $j\in[n-1]$.

Letting $h_j:=u_j-u_{j-1}$, we rewrite (1) as $q_j h_j=p_j h_{j+1}$ or, equivalently, as \begin{equation} h_{j+1}=\frac j{n-j}\,h_j, \end{equation} whence \begin{equation} h_j=h_1\prod_{i=2}^j\frac{i-1}{n-i+1} =h_1\frac{1\cdot2\cdots(j-1)}{(n-1)(n-2)\cdots(n-j+1)} =h_1\Big/\binom{n-1}{j-1} \end{equation} for $j\in[n]$. So, \begin{equation} 1=u_n-u_0=\sum_{j\in[n]}h_j=h_1\,c_n,\quad c_n:=\sum_{j\in[n]}1\Big/\binom{n-1}{j-1}, \end{equation} and thus $h_1=1/c_n$ and for all $j\in[n]_0$ \begin{equation} u_j=\sum_{i\in[j]}h_i=\frac1{c_n}\,\sum_{i\in[j]}1\Big/\binom{n-1}{i-1}. \end{equation}

Note that for $n\ge4$ \begin{align*} c_n&=1\Big/\binom{n-1}0+1\Big/\binom{n-1}1+1\Big/\binom{n-1}{n-2}+1\Big/\binom{n-1}{n-1}+b_n \\ &=1+\frac1{n-1}+\frac1{n-1}+1+b_n, \end{align*} where \begin{equation} 0\le b_n:=\sum_{j=3}^{n-2}1\Big/\binom{n-1}{j-1}\le(n-4)\Big/\binom{n-1}2\to0 \end{equation} (as $n\to\infty$). So, $c_n\to2$, $h_1=1/c_n\to1/2$, and (by symmetry), $h_n=h_1\to1/2$. Also, for all $j\in[n-1]$ we have $h_1=u_1\le u_j\le u_{n-1}=1-h_n$.

Thus, \begin{equation} u_j=u_{n,j}\to1/2 \end{equation} uniformly over all $j\in[n-1]$.

Here is the discrete graph $\{(j,u_{30,j})\colon j\in[30]_0\}$:

This answer is a detalization of a comment by Anthony Quas, according to which the problem can be restated as follows.

Consider a Markov chain on the set $[n]_0:=\{0,\dots,n\}$ with transition probabilities $p_{i,j}$ such that for $i\in[n]:=\{1,\dots,n\}$ \begin{equation} p_{i,i+1}=p_i:=\frac{n-i}n, \quad p_{i,i-1}=q_i:=\frac in=1-p_i. \end{equation} For any $j\in[n]_0$, find the probability -- say $u_j=u_{n,j}$ -- that, after starting in the state $j$, the chain will reach the state $n$ before reaching the state $0$.

We have $u_0=0$, $u_n=1$, and \begin{equation} u_j=p_j u_{j+1}+q_j u_{j-1} \tag{1} \end{equation} for $j\in[n-1]$.

Letting $h_j:=u_j-u_{j-1}$, we rewrite (1) as $q_j h_j=p_j h_{j+1}$ or, equivalently, as \begin{equation} h_{j+1}=\frac j{n-j}\,h_j, \end{equation} whence \begin{equation} h_j=h_1\prod_{i=2}^j\frac{i-1}{n-i+1}=h_1\Big/\binom{n-1}{j-1} \end{equation} for $j\in[n]$. So, \begin{equation} 1=u_n-u_0=\sum_{j\in[n]}h_j=h_1\,c_n,\quad c_n:=\sum_{j\in[n]}1\Big/\binom{n-1}{j-1}, \end{equation} and thus $h_1=1/c_n$ and for all $j\in[n]_0$ \begin{equation} u_j=\sum_{i\in[j]}h_i=\frac1{c_n}\,\sum_{i\in[j]}1\Big/\binom{n-1}{i-1}. \end{equation}

Note that for $n\ge4$ \begin{align*} c_n&=1\Big/\binom{n-1}0+1\Big/\binom{n-1}1+1\Big/\binom{n-1}{n-2}+1\Big/\binom{n-1}{n-1}+b_n \\ &=1+\frac1{n-1}+\frac1{n-1}+1+b_n, \end{align*} where \begin{equation} 0\le b_n:=\sum_{j=3}^{n-2}1\Big/\binom{n-1}{j-1}\le(n-4)\Big/\binom{n-1}2\to0 \end{equation} (as $n\to\infty$). So, $c_n\to2$, $h_1=1/c_n\to1/2$, and (by symmetry), $h_n=h_1\to1/2$. Also, for all $j\in[n-1]$ we have $h_1\le u_j\le u_{n-1}=1-h_n$.

Thus, \begin{equation} u_j=u_{n,j}\to1/2 \end{equation} uniformly over all $j\in[n-1]$.

Here is the discrete graph $\{(j,u_{30,j})\colon j\in[30]_0\}$:

This answer is a detalization of a comment by Anthony Quas, according to which the problem can be restated as follows.

Consider a Markov chain on the set $[n]_0:=\{0,\dots,n\}$ with transition probabilities $p_{i,j}$ such that for $i\in[n]:=\{1,\dots,n\}$ \begin{equation} p_{i,i+1}=p_i:=\frac{n-i}n, \quad p_{i,i-1}=q_i:=\frac in=1-p_i. \end{equation} For any $j\in[n]_0$, find the probability -- say $u_j=u_{n,j}$ -- that, after starting in the state $j$, the chain will reach the state $n$ before reaching the state $0$.

We have $u_0=0$, $u_n=1$, and \begin{equation} u_j=p_j u_{j+1}+q_j u_{j-1} \tag{1} \end{equation} for $j\in[n-1]$.

Letting $h_j:=u_j-u_{j-1}$, we rewrite (1) as $q_j h_j=p_j h_{j+1}$ or, equivalently, as \begin{equation} h_{j+1}=\frac j{n-j}\,h_j, \end{equation} whence \begin{equation} h_j=h_1\prod_{i=2}^j\frac{i-1}{n-i+1}=h_1\Big/\binom{n-1}{j-1} \end{equation} for $j\in[n]$. So, \begin{equation} 1=u_n-u_0=\sum_{j\in[n]}h_j=h_1\,c_n,\quad c_n:=\sum_{j\in[n]}1\Big/\binom{n-1}{j-1}, \end{equation} and thus $h_1=1/c_n$ and for all $j\in[n]_0$ \begin{equation} u_j=\sum_{i\in[j]}h_i=\frac1{c_n}\,\sum_{i\in[j]}1\Big/\binom{n-1}{i-1}. \end{equation}

Note that for $n\ge4$ \begin{align*} c_n&=1\Big/\binom{n-1}0+1\Big/\binom{n-1}1+1\Big/\binom{n-1}{n-2}+1\Big/\binom{n-1}{n-1}+b_n \\ &=1+\frac1{n-1}+\frac1{n-1}+1+b_n, \end{align*} where \begin{equation} 0\le b_n:=\sum_{j=3}^{n-2}1\Big/\binom{n-1}{j-1}\le(n-4)\Big/\binom{n-1}2\to0 \end{equation} (as $n\to\infty$). So, $c_n\to2$, $h_1=1/c_n\to1/2$, and (by symmetry), $h_n=h_1\to1/2$. Also, for all $j\in[n-1]$ we have $h_1=u_1\le u_j\le u_{n-1}=1-h_n$.

Thus, \begin{equation} u_j=u_{n,j}\to1/2 \end{equation} uniformly over all $j\in[n-1]$.

Here is the discrete graph $\{(j,u_{30,j})\colon j\in[30]_0\}$:

This answer is a detalization of a comment by Anthony Quas, according to which the problem can be restated as follows.

Consider a Markov chain on the set $[n]_0:=\{0,\dots,n\}$ with transition probabilities $p_{i,j}$ such that for $i\in[n]:=\{1,\dots,n\}$ \begin{equation} p_{i,i+1}=p_i:=\frac{n-i}n, \quad p_{i,i-1}=q_i:=\frac in=1-p_i. \end{equation} For any $j\in[n]_0$, find the probability -- say $u_j=u_{n,j}$ -- that, after starting in the state $j$, the chain will reach the state $n$ before reaching the state $0$.

We have $u_0=0$, $u_n=1$, and \begin{equation} u_j=p_j u_{j+1}+q_j u_{j-1} \tag{1} \end{equation} for $j\in[n-1]$.

Letting $h_j:=u_j-u_{j-1}$, we rewrite (1) as $q_j h_j=p_j h_{j+1}$ or, equivalently, as \begin{equation} h_{j+1}=\frac j{n-j}\,h_j, \end{equation} whence \begin{equation} h_j=h_1\prod_{i=2}^j\frac{i-1}{n-i+1}=h_1\Big/\binom{n-1}{j-1} \end{equation} for $j\in[n]$. So, \begin{equation} 1=u_n-u_0=\sum_{j\in[n]}h_j=h_1\,c_n,\quad c_n:=\sum_{j\in[n]}1\Big/\binom{n-1}{j-1}, \end{equation} and thus $h_1=1/c_n$ and for all $j\in[n]_0$ \begin{equation} u_j=\sum_{i\in[j]}h_i=\frac1{c_n}\,\sum_{i\in[j]}1\Big/\binom{n-1}{i-1}. \end{equation}

Note that for $n\ge4$ \begin{align*} c_n&=1\Big/\binom{n-1}0+1\Big/\binom{n-1}1+1\Big/\binom{n-1}{n-2}+1\Big/\binom{n-1}{n-1}+b_n \\ &=1+\frac1{n-1}+\frac1{n-1}+1+b_n, \end{align*} where \begin{equation} 0\le b_n:=\sum_{j=3}^{n-2}1\Big/\binom{n-1}{j-1}\le(n-4)\Big/\binom{n-1}2\to0 \end{equation} (as $n\to\infty$). So, $c_n\to2$, $h_1=1/c_n\to1/2$, and (by symmetry), $h_n\to1/2$. Also, for all $j\in[n-1]$ we have $h_1\le u_j\le u_{n-1}=1-h_n$.

Thus, \begin{equation} u_j=u_{n,j}\to1/2 \end{equation} uniformly over all $j\in[n-1]$.

This answer is a detalization of a comment by Anthony Quas, according to which the problem can be restated as follows.

Consider a Markov chain on the set $[n]_0:=\{0,\dots,n\}$ with transition probabilities $p_{i,j}$ such that for $i\in[n]:=\{1,\dots,n\}$ \begin{equation} p_{i,i+1}=p_i:=\frac{n-i}n, \quad p_{i,i-1}=q_i:=\frac in=1-p_i. \end{equation} For any $j\in[n]_0$, find the probability -- say $u_j=u_{n,j}$ -- that, after starting in the state $j$, the chain will reach the state $n$ before reaching the state $0$.

We have $u_0=0$, $u_n=1$, and \begin{equation} u_j=p_j u_{j+1}+q_j u_{j-1} \tag{1} \end{equation} for $j\in[n-1]$.

Letting $h_j:=u_j-u_{j-1}$, we rewrite (1) as $q_j h_j=p_j h_{j+1}$ or, equivalently, as \begin{equation} h_{j+1}=\frac j{n-j}\,h_j, \end{equation} whence \begin{equation} h_j=h_1\prod_{i=2}^j\frac{i-1}{n-i+1}=h_1\Big/\binom{n-1}{j-1} \end{equation} for $j\in[n]$. So, \begin{equation} 1=u_n-u_0=\sum_{j\in[n]}h_j=h_1\,c_n,\quad c_n:=\sum_{j\in[n]}1\Big/\binom{n-1}{j-1}, \end{equation} and thus $h_1=1/c_n$ and for all $j\in[n]_0$ \begin{equation} u_j=\sum_{i\in[j]}h_i=\frac1{c_n}\,\sum_{i\in[j]}1\Big/\binom{n-1}{i-1}. \end{equation}

Note that for $n\ge4$ \begin{align*} c_n&=1\Big/\binom{n-1}0+1\Big/\binom{n-1}1+1\Big/\binom{n-1}{n-2}+1\Big/\binom{n-1}{n-1}+b_n \\ &=1+\frac1{n-1}+\frac1{n-1}+1+b_n, \end{align*} where \begin{equation} 0\le b_n:=\sum_{j=3}^{n-2}1\Big/\binom{n-1}{j-1}\le(n-4)\Big/\binom{n-1}2\to0 \end{equation} (as $n\to\infty$). So, $c_n\to2$, $h_1=1/c_n\to1/2$, and (by symmetry), $h_n=h_1\to1/2$. Also, for all $j\in[n-1]$ we have $h_1\le u_j\le u_{n-1}=1-h_n$.

Thus, \begin{equation} u_j=u_{n,j}\to1/2 \end{equation} uniformly over all $j\in[n-1]$.

Here is the discrete graph $\{(j,u_{30,j})\colon j\in[30]_0\}$: