2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ Two question for clarifying: 1. Do you mean "reach $x$ after exactly $n$ steps"? 2. May $c$ and $C$ depend on the modification, on the original graph, and on $o$? $\endgroup$
    – cubic lettuce
    Commented Dec 6, 2015 at 14:50
  • $\begingroup$ Probably this is of help: you can simulate a selfloop at $o$ of arbitrary weight by adding $N$ vertices as additional neighbors to $o$, all of which simply point back to $o$. This arbitrarily pushes down the probability of leaving $o$ to any of its original neighbors, hence, $q(n,o,x) \geq 0 \cdot p(n,o,x)$ with $c=0$ as only possible choice if $c$ is required to be independent of the modification. $\endgroup$
    – cubic lettuce
    Commented Dec 6, 2015 at 14:57
  • $\begingroup$ The comparison constants $c$ and $C$ depend on the modification (otherwise it makes no sense, as you have shown). $\endgroup$
    – Pablo Lessa
    Commented Dec 6, 2015 at 15:20

0

Reset to default

You must log in to answer this question.