Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider the hypercube $Q_4$. I would like to know how to compute the number of steps of a random walk in this graph such that the probability to be at a vertex is a given number $x$. I think I just have to invert the relation of the transition matrix...The probability to be at vertex $i$ should be $p_t(i)=(D^{-1}A)^tp_0$ where $D$ is the diagonal matrix with elements the degrees , $(D)_{ii}=d_i$, $A$ is the adjacency matrix of the graph and p_0 the initial probability distribution. I think I have to find the parameter $t$ such that one entry of the matrix is exactly that given number. The problem is that I can't use just a logarithm beacause of the power of the matrix. Someone can help me? Thanks in advance

share|improve this question
Not quite sure if I get it. Are you assuming that the question has a solution for the given x? –  Algernon May 18 '13 at 13:46
yes exactly. I have the probability $x$. –  Rob May 18 '13 at 21:17

2 Answers 2

The better thing to do is use the Fourier transform for $(Z/2)^n$, which will diagonalize the transition matrix, take powers then do the inverse Fourier transform. See the lecture notes of Diaconis for details http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.lnms/1215467407.

share|improve this answer
uhm...i think it should be much easier... –  Rob May 18 '13 at 22:07

I think the answer is related to the mixing time and mixing rate, but I don't know how to esplicity use them

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.