Skip to main content
2 of 2
edited title
ofer zeitouni
  • 7.5k
  • 1
  • 22
  • 38

How sensitive are the n-th step transition probabilities of the simple random walk to a small perturbation of an infinite graph?

Suppose that $G$ is an infinite, locally finite, connected graph.

Fix a vertex $o$ in the graph and for each $n$ and $x$ let $p(n,o,x)$ be the probability that a simple random walk (at each step a neighbor is chosen uniformly at random) starting at $o$ will reach $x$ after $n$ steps.

Suppose now that one modifies the graph by adding a finite number of vertices and edges (and maybe deleting edges too but keeping the thing connected) within the ball of some radius $r$ centered at $o$.

Letting $q(n,o,x)$ be the new transition probabilities. Can one claim that there exist constants $c$ and $C$ such that $cp(n,o,x) \le q(n,o,x) \le Cp(n,o,x)$ for all $n$ large enough and all $x$ far enough away from $o$?

What information is needed to estimate $c$ and $C$ assuming they do exist?

More generally: What comparison results are known between $p$ and $q$?

I'm willing to assume that the graph $G$ is not positively recurrent (i.e. almost every random walk path returns to the ball of radius $r$ on a set of times with zero density). And also that there are no parity issues (e.g. $p(n,o,x) > 0$ for all $n$ larger than the distance between $o$ and $x$; assume that the graph has an infinite number of triangles in it if this helps).

I've included the functional analysis tag because this situation can be viewed as a finite rank perturbation of a non-negative definite bounded self-adjoint operator on $L^2(G)$ (the operator which averages a function over the neighboring vertices). I know there is a lot of literature on this type of thing but I'm hoping you guys could help me get to the relevant ideas a bit faster.

Pablo Lessa
  • 4.3k
  • 28
  • 37