Green's function for random walks on a network

541 Views Asked by At

My question comes from section 9.4. of the book "Markov Chains and Mixing Times (2nd edition)" written by David A.Levin and Yuval Peres. Specifically, in page 119, the author defines the $\color{blue}{\text{Green's function}}$ for a random walk (on a network) stopped at a stopping time $\tau$ via $$G_\tau(a,x):= \mathbb{E}_a(\text{number of visits to $x$ before $\tau$}) = \mathbb{E}_a\left(\sum_{t=0}^\infty \mathbf{1}_{\{X_t=x,\tau >t\}}\right).$$ Then in the (very short) proof of Lemma 9.6. in the same page the author says "The number of visits to $a$ before visiting $z$ has a geometric distribution with parameter $\mathbb{P}_a\{\tau_z < \tau^+_a\}$."

Here $\tau_z$ is the first hitting time ($\geq 0$) for the process to hit $z$ and $\tau^+_a$ is the first return time ($\geq 1$) for the process starting at $a$ to return to $a$. However, I really didn't see why the statement in red holds, because isn't the event $\{\tau_z < \tau^+_a\}$ implies the process hits $z$ before returning to $a$ (and not that the process visits $a$ before visiting $z$)? Thanks for any help!

2

There are 2 best solutions below

0
On BEST ANSWER

Each time the chain starts from $a$ we have an independent experiment where success means visiting $z$ before returning to $a$. The number of experiments until the first success (inclusive) is a geometric random variable $X$ with parameter $p=\mathbb{P}_a\{\tau_z < \tau^+_a\}$ taking values in $1,2,...$. See https://en.wikipedia.org/wiki/Geometric_distribution

The number of visits to $a$ before $\tau_z$ is exactly $X$ because we count the visit at time zero.

0
On

Yes, that looks like a typo. Like you argued, you should flip the inequality. I checked the PDF to see if they corrected/used the lemma later; it seems they used it (uncorrected) in the proof of proposition 10.6, so that probably needs a correction as well (since you seem to have emailed them before, you might want to mention that).