Random walk on $n$-dimensional cube 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.
 A: 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\}$:

A: 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).
$$
