MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 because of the power of the matrix. Can someone help me? Thanks in advance.

share|cite|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
I think the answer is related to the mixing time and mixing rate, but I don't know how to esplicity use them – Rob May 18 '13 at 22:21

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

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

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.