Let $E:=\{0,1\}^n$ be the corners of a n-dimensional unit cube. Let $(X_n)_n$ be the symmetric Random Walk on E. A jump from i to j, $i,j\in E$ has probability 1/n if $|i-j|=1$. I am interested in the expecation of
$$T:=\inf\{n\geq 0: X_n=\mathbf 1\}$$
where $\mathbf 1=(1,1,1,\ldots,1)$ is the n-dimensional vector with all ones. In particular, i want to compute the expected traversal time
$$\mathbb E[T\,|\,X_0=\mathbf 0].$$
That is the expected number of steps necessary for the random walk to traverse the unit cube starting in corner $\mathbf 0=(0,0,0,\ldots,0)$ and arriving at the opposite corner $\mathbb 1$ for the first time.
First, I showed that this Markov Chain is exactly lumpable into a Birth-And-Death process with reflecting boundaries, where the forward/backward probabilities at site k (=lumped state containing all n-dimensional vectors with exactly k ones) are
$$p_k^+=\frac{n-k}{n},\qquad p^-_k=\frac{k}{n}.$$
We also have $p^+_0=1$, $p^-_0=0$ and $p^+_n=0$, $p^-_n=1$. Travel times from corner to corner are preserved under exact lumpability.
Usually, i would just solve a set of equations,
$$
\begin{align*}
h(0)&=1+h(1),\\
h(k)&=p^-_k h(k-1)+p^+_kh(k+1)+1,\\
h(n)&=0,
\end{align*}$$
where $h(k):=\mathbb E[T\,|\, X_0=k]$.
Problem: I would need a particular solution of this system of difference equations. Does anyone see how to proceed? It bugs me that the resulting B&A process is so similar to a Moran Process, but the solution does not match.
EDIT: After much persuasion, wolframAlpha gave me a solution. However, it is in terms of regularised hypergeometric functions, which is not a nice result:
$$\mathbb E[T\,|\,X_0=\mathbf 0]=\frac{1}{2^{n+1}}\frac{e^{i\pi(n+1)}\Gamma(n+1)}{\ _2\tilde F_1(1,1;1-n;-1)+\ _2\tilde F_1(1,2;2-n;-1)}$$
Intuitively, I would expect some binomial coefficients here, but i do not see how to simplify it.
EDIT: The answer from Florian Lehner below seems to indicate that
$$\mathbb E[T\,|\,X_0=\mathbf 0]=\frac{1}{2}\sum_{k=0}^{n-1}\frac
{1}{\pi_k\,p^+_k},$$
where $\pi=(\pi_0,\pi_1,\ldots,\pi_n)$ is the stationary distribution of the lumped B&D-process. The stationary distribution is binomial, i.e.
$$\pi_k=\binom{n}{k}2^{-n}.$$
However, guessing a solution of the recurrence above is not straight forward, but maybe it is some version of siefting formula…?
Best Answer
This has a neat answer using electrical networks, for some background on this see chapter 2 of the book
Lyons, Russell; Peres, Yuval, Probability on trees and networks, Cambridge Series in Statistical and Probabilistic Mathematics 42. Cambridge: Cambridge University Press (ISBN 978-1-107-16015-6/hbk; 978-1-108-73272-7/pbk; 978-1-316-67281-5/ebook). xv, 699 p. (2016). ZBL1376.05002.
It is known that the commute time is $2 |E| \mathcal R(\mathbf 0 \leftrightarrow \mathbf 1)$, where $\mathcal R(\mathbf 0 \leftrightarrow \mathbf 1)$ is the effective resistance between the two vertices when the graph is interpreted as an electrical network where all edges are unit resistors (Corollary 2.21 in the book mentioned above).
Due to symmetry, the hitting time you are looking for is just half of the commute time.
It is also known that $\mathcal R(\mathbf 0 \leftrightarrow \mathbf 1)$ is equal to the energy of a unit current flow (eq. (2.7) in the book). Due to symmetry, the unit current flow sends the same amount of current across every edge connecting a vertex of hamming weight $k$ to a vertex of hamming weight $k+1$. There are $\binom {n}{k} (n-k)$ such edges for every $k$, so the flow across each of them is $i(e) = (\binom {n}{k} (n-k))^{-1}$.
Finally, we need to compute the energy of this flow: $$\mathcal E(i) = \sum_{e \in E} i(e)^2 = \sum_{k=0}^{n-1} \left(\binom {n}{k} (n-k)\right)^{-1}$$
So unless I have made a mistake in my computations, the expected traversal time is $$n 2^{n-1}\sum_{k=0}^{n-1} \left(\binom {n}{k} (n-k)\right)^{-1}$$