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.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Not quite sure if I get it. Are you assuming that the question has a solution for the given x? $\endgroup$– AlgernonCommented May 18, 2013 at 13:46
-
$\begingroup$ yes exactly. I have the probability $x$. $\endgroup$– RobCommented May 18, 2013 at 21:17
-
$\begingroup$ I think the answer is related to the mixing time and mixing rate, but I don't know how to esplicity use them $\endgroup$– RobCommented May 18, 2013 at 22:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered May 18, 2013 at 12:39
-
$\begingroup$ uhm...i think it should be much easier... $\endgroup$– RobCommented May 18, 2013 at 22:07