0
$\begingroup$

Consider an infinite undirected graph $G$, like for example $\mathbb{Z}^d$ with edges connecting nearest neighbours sites. Let $X(t)$ be a simple random walk starting from the origin, $o$, define $ B_L := \{ x \in \mathbb{Z}^d \, \, : \, \, d(x,o) \leq L\} $ namely the set of sites whose graph distance from the origin is at most $L$. Let $ E_1 $ be the expected number of steps performed by the simple random walk before leaving the set $B_L$ or returning to the origin, $$ E_1 = E \big ( \sum\limits_{t=0}^{\infty} \mathbb{1}\{ t < \tau_{B_L^c \cup \{o\}} \} \big ), $$ where $\mathbb{1}$ is the indicator function, $E$ is the expectation of the simple random walk, and $\tau_{B_L^c \cup \{o\}}$ is the hitting time of the set $B_L^c \cup \{o\}$, where $B_L^c:= \mathbb{Z}^d \setminus B_L$. Let $E_2$ be the expected number of distinct vertices visited by the simple random walk before leaving $B_L$ or returning to the origin, $$ E_2 = \sum\limits_{x\in B_L}^{\infty} \mathbb{1}\{ \exists t < \tau_{B_L^c \cup \{o\}} \, \, \, s.t. \, \, X_t = x\} $$

Are $E_1$ and $E_2$ of the same order of magnitude in $L$? The answer is easy and positive if the graph is transient, but what about recurrent graphs?

It would be enough for me to receive some hint!

$\endgroup$
0
$\begingroup$

First, note that $E_1 = E(\tau_{B_L^x \cup \{o\}})$, ie is just the expected hitting time.

I expect this can depend a lot on the graph. Take, for example, just $\mathbb Z$. Recall that the expected return time to the origin (for a standard symmetric SRW) is infinite. On the other hand, the expected exit time of $[-L,L]$ is order $L^2$. Given that the walk exits $[-L,L]$ before returning to $0$, it hits precisely $L$ distinct vertices.

Now, a slight caveat: I've said "expected return time to the origin is $\infty$" and "expected exit time of $[-L,L]$ is order $L^2$" -- these are both correct statements, but they don't, a priori, imply that "expected exit time of $[-L,L]$, given that the origin is not returned to, is order $L^2$". However, this should be pretty easy to prove: first walk from $0$ to $L/2$ directly (this is the worst that conditioning on not returning to $0$ can do for the first $L/2$ steps); now hitting $0$ or $L$ is the same as exiting the interval $[L/2 - L/2, L/2 + L/2]$, which is order $(L/2)^2$, ie order $L^2$. I'm sure one can make this rigorous.


Using the fact that a SRW on $\mathbb Z^2$ is just a pair of independent SRWs on $\mathbb Z$ (in continuous time), one can likely extend this result to $\mathbb Z^2$ without too much change or additional ideas.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.