walks on hypercubes Let's say I start at the $(0,0,...,0)$ vertex of $n$-dimensional hypercube. After each unit of time $l$, I either stay where I am with probability $p$, or move to an adjacent vertice with probability $q = \frac{1-p}{n}$. What is the probability I end up back where  I started after $l$ units of time?
Having difficulty wrapping my head around this question... If $p = 0$, then the answer is simply $$ \frac{1}{2^n n^l}\sum \limits_{i = 0}^{n}\binom{n}{i}(n-2i)^l$$
messing around with $n=2$ I found that for general $p$:
$P(0) = 1, P(1) = p, P(2) = p^2 + 2q^2, P(3) = p^3 + 2p^2q + 4pq^2, P(4) = p^3 + 11p^2q^2 + 7q^4$.
I'm not seeing any obvious pattern here, and I'm not sure how to proceed to figure out a closed form for general $n$.
 A: For $n=2$ let the start state ber $A=(0,0)$ and let $B=(0,1),C=(1,0),D=(1,1),$ so that the moves possible besides staying where you are go from $A$ to $B$ or $C$, from $B$ to $A$ or $D$, from $C$ to $A$ or $D$, and from $D$ to $B$ or $C$. If we set up a transition matrix $M$ all the diagonal entries will be $p$ and the other entries corresponding to possible moves are $q$, whereas the impossible diagonal moves across the unit square have $0$ at that entry. For $M$ I got the following:
$$M= \begin{matrix} p & q&q&0 \\ q&p&0&q \\ q&0&p&q\\ 0&q&q&p \end{matrix}.$$
Then the probability of returning to $A$ after $k$ steps is the $(1,1)$ entry of the matrix power $M^k$. I found agreement with your value of $p^2+2q^2$ for a return in two steps, however for three steps when I did the matrix power (using a symbolic calculator) it was $p^3+6pq^2$, and for four steps it was $p^4+12p^2q^2+8q^4.$ (Actually it would surprise me if the four step return had a cubic term in it, as the one in the post did.)
It seems to me the case for general higher $n$ would be quite complex, since even the setup of the transition matrix would be involved, and there would be $2^n$ states to deal with. But one could do $n=3$ this way for example.
