Expected number of return for a random walk on a graph

861 Views Asked by At

Let $G$ be a simple, connected undirected graph of order $n$ and vertex set $\{v_1,\ldots,v_n\}$ and let $P = (p_{i,j})$ be a $n \times n$ matrix where $$p_{i,j} = \left\{ \begin{array}{ll} \frac{1}{d(v_i)} & \mbox{if } v_i \sim v_j \\ 0 & \mbox{otherwise } \end{array} \right.$$

If we let $\pi = \frac{1}{2|E(G)|}(d(v_i), \ldots, d(v_n) )$ then it is not hard to see that $$\pi P = \pi.$$

Let $H_v$ be the expected number of steps for a random walk to reach back $v$ given that it started the random walk in $v.$

Reading through some textbooks it seems like at this point it should easy to infer that $H_v = \frac{2|E(G)}{d(v)}$ yet I do not see why.

As the comments suggest one needs to apply the law of large numbers yet I do not see how to set up the framework for applying the statement of LLN. Hence I am asking

How do we apply the law of large numbers in this context?

1

There are 1 best solutions below

0
On

Your chain is recurrent (since it is a finite state makov chain).

In this context there is a general formula that relates the invariant measure $\nu(\cdot)$ and the expected time of return $\Bbb{E}[\tau_\cdot]$.

Let $X_0 = i$, define $T_1 = \inf\{k>0, X_k = i\}, T_2 = \inf\{k> T_1, X_k = i\}, \ldots$ Those $T_j$ are the times of first return to the site $i$.

Denote $V_n(i)=\#\{\text{visits to the site } i \text{ in $n$ steps of the chain}\}$.

It is a property of the invariant measure that $$\nu(i) = \lim_{n \to \infty} \frac{V_n(i)}{n} $$

Now note that \begin{align}\nu(i) &= \lim_{n \to \infty} \frac{V_{(T_1 + \ldots + T_n)}(i)}{T_1 + \ldots + T_n} \\ & = \lim_{n \to \infty} \frac{1}{\frac{T_1 + \ldots + T_n}{V_{(T_1 + \ldots + T_n)}(i)}} \\\end{align}

Note that $V_{(T_1 + \ldots +T_n)}(i) = n$ and since the $T_i$ are independent and identically distributed (use the law of large numbers here) $$\lim_k \frac{T_1 + \ldots + T_n}{n} \to \Bbb{E}[T_1]$$

Therefore this gives us

$$\nu(i) = \frac{1}{\Bbb{E}[T_1]} $$