Thursday, 22 August 2013

Variance of the first return time in a symmetric simple d-dimensional random walk

Variance of the first return time in a symmetric simple d-dimensional
random walk

I am trying to solve this problem....
I have a simple random walk on a $d$-regular finite graph. At each vertex
of the graph, the particle chooses one of $d$ edges equally likely. I need
to calculate the variance of first return time, i.e. the variance (or
second moment) of the time that takes until the particle is at the vertex
it started. I know that for the $i^{th}$ vertex second moment return time
is:
$ w_{ii}=-\frac{1}{\pi_i}+\frac{2z_{ii}}{\pi_i^2} $
where $\pi_i$ is the steady state probability and $z_{ii}$ is $(i,i)$
element of the fundamental matrix (fundamental matrix: $Z=(I-(A-P))^{-1}$,
$A$ is transition probability matrix and $P$ is steady state probability
matrix). I just do not know how to find $z_{ii}$ in terms of $d$. Can
anybody help to find the exact answer or an upper bound?

No comments:

Post a Comment