Random walk on $n$-dimensional cube

Question

Consider a symmetric random walk along the edges of an $n$-dimensional unit cube. At each time step, a particle located at a particular vertex $(a_1, \ldots, a_n)$ moves to an adjacent neighbor each with equal probability.

For an arbitrary starting point $(a_1, \ldots, a_n)$, how can I compute the probability that we will hit $(1, 1, \ldots, 1)$ before hitting $(0, 0, \ldots, 0)$? This will be a function of $n$.

I thought about making a Markov chain with $2^{n}$ states, but I'm not entirely sure if this is the right approach. Under this representation, I'm pretty sure some state $u = (a_1, \ldots, a_n)$ can move to some other state if and only if we can retrieve the second state by turning a bit off in $u$ or turning a bit on (that is not already on) in $u$. I think this may be the best approach, but I'm a bit stuck.

I wrote an expression for the probability of reaching the state with all ones prior to the state with all zeros for each different starting state, and I also use each temr in the expressions for others (so we need to solve for the variables), but I see no easy way to finish.

A solution is provided here https://arxiv.org/pdf/0711.2675.pdf, but it uses circuits and a less mathematical approach to derive the answer.

Any help is appreciated.

Answer 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\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\}$:

Answer 2

This is to give an alternative solution, which works for three general points of the cube and does not involve lumping.

Let $F_{xy}(z)$ be the probability that the random walk started form $z$ visits $x$ before $y$. Let $P$ be the transition matrix of the walk. Then, by conditioning on the first step of the walk, we see that $F_{xy}$ is a solution to the Dirichlet problem $F_{xy}(x)=1,$ $F_{xy}(y)=0$ and $$ \sum_w P(z,w)F_{xy}(w)=F_{xy}(z),\quad z\neq x,y. $$ In fact, it is determined uniquely by these conditions, as the difference of two solutions cannot have a maximum or minimum at $z\neq x,y$. In fact, we can instead solve the following problem: \begin{equation} \Delta G=\delta_x-\delta_y, \tag{1} \end{equation} where $\Delta=I-P$. Indeed, $\sum_w(\Delta H)(w)=0$ for any $H$, thus, $(\Delta F_{xy})(x)=-(\Delta F_{xy})(y)$, i. e., $\Delta F_{xy}=\alpha(\delta_x-\delta_y)$ for some $\alpha\neq 0$. The solution to (1) is uniquely determined up to an additive constant, so, if $G$ is any such solution, then $$ F_{xy}(z)=\frac{G(z)-G(0)}{G(1)-G(0)}. $$ So far, this is all true for any reversible Markov chain. To solve (1) for the hypercube, we use that the hypercube is an Abelian group and that $\Delta$ commutes with the group action. Concretely, we use the Fourier-Walsh transform. For the hypercube $Q=\{a=(a_1,\dots,a_n):a_i\in\{0,1\}\}$, we have the orthonormal basis of $L^2(Q)$ indexed by $S\subset\{1,\dots,n\}$ given by $$ \xi_S(a)=2^{-\frac{n}{2}}\prod_{j\in S} (-1)^{a_j}. $$ So, we can decompose $G$ in this basis, $G=\sum_S \hat{G}_S \xi_S$. We compute $$ \Delta \xi_S=\left(\frac{1}{n}\sum_{i=1}^n(1-(-1)^{\mathbf{1}_{i\in S}})\right)\xi_S=\frac{2|S|}{n}\xi_S, $$ while $$ \hat{(\delta_x)}_S=\sum_{a\in Q}\xi_S(a)\delta_x(a)=\xi_S(x). $$ Therefore, the equation (1) after the Fourier transform becomes $$ \Delta G=\sum_S\frac{2|S|}{n} \hat{G}_S\xi_S=\sum_S(\xi_S(x)-\xi_S(y))\xi_S. $$ So the solution to (1), up to an additive constant, is given by $$ G(z)=\sum_{S\neq \emptyset}\frac{n}{2|S|}(\xi_S(x)-\xi_S(y))\xi_S(z). $$