Search Results

The behavior of this model can be inferred from the corresponding continuous-time discrete-space model analyzed in [1]-[4] below. [1] Van den Berg, J., and Harry Kesten. "Asymptotic density in a coale …

The formula you write is correct. Your chain is constrained to go from any node to a node that is one step closer to the sink $t$. This can be thought of as a Doob-transform of the space-time chain $( …

The asymptotic cover time result in [1] (see comment 2 above) works for the grid as well as the torus. See comment 2 on page 28 in https://arxiv.org/pdf/math/0107191.pdf . Further refinements are in …

Expanding the comment above to a complete proof of Noam Elkies' formula: Let $\tau$ be the first meeting time for independent simple random walks $X_t, Y_t$ and $Z_t$ started at the even points $x<y …

If $G$ is a path of length $n$ and the initial node $x$ is an endpoint, then $E(T)=O(\log n)$. More precisely, $$P(T>k)=O(1/k) \; \; \text{for} \; \; k \le n^2 \quad (*) $$ $$ \text{and } \; \; P( …

Note that some conditions are needed: If the matrices $A_i$ are all rotation matrices then no contraction takes place. A relatively easy case is when all the matrices are strictly positive elementwise …

Let $\tau$ be the minimal $t<T$ such that $x(t)>c$, if such $t$ exists; set $\tau=T-1$ if there is no such $t$. Then the event $\{x(\tau)>c\}$ is the disjoint union of two events, $A=\{x(T-1)>c\}$ a …

The inequality you are citing should have a power 2 on the Cheeger constant (a.k.a the bottleneck ratio), so the inequality should read: $$t_{\rm mix} \le C\log\left(\min_{v\in V}\dfrac{1}{\pi(v)}\rig …

Assume that $i<j.$ You can reduce this to the following simpler-looking question: Consider a continuous-time RW on the integers, moving at rate two, started at $k:=j-i$. Let $T$ be the hitting time of …

the limit $L=\lim_{t\to\infty}\frac {\log f(t)}{\log t}$ always exists, in the wide sense. If a transitive graph does not have polynomial growth, then the limit is $-\infty$, while if it has polynomia …

The most powerful and flexible method to prove recurrence or transience for nonreversible walks is the method of Lyapunov functions. One of the origins of the method is Foster's criteria for recurrenc …

For the one dimensional case, a quite nice bound is in Theorem 4.2 of [1]. See also [2]. The dependence on $\epsilon$ that you seek was first shown by Kesten[3]. The combinatorial approach was revive …

You can find this example discussed also in my book with Russ Lyons, "Probability on Trees and networks", http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html As Douglas points out, For any vertex $v$ …

Let $\tau_k$ denote the number of steps for discrete time simple RW on the integers (started at 0) to exit the interval $[-k,k]$. Let $\gamma:=\cos(\frac{\pi}{2k+2})$ so that $\lambda=1-\gamma$. The …

I assume the question pertains to continuous time random walk; the counterexamples are even simpler in discrete time. There is no reason to expect the power law factor $t^{-n/2}$ in this setting. For …