6.4 Short-time bounds

The first application is a variant of work of Broder et al [64] discussed further in section 6.8.2.

Remarks. The point is the $\frac{1}{K^{2}}$ dependence on $K$. On the $n$-cycle, for $K\sim\varepsilon n$ it can be shown that initially the largest gap between adjacent walkers is $\Theta(\log n)$ and that $EC^{[K]}=\Theta(\log^{2}n)$, so in this respect the bound is sharp. Of course, for $K\leq\log n$ the bound would be no improvement over Theorem 6.4.

Proof. As usual write $T_{i}$ for the hitting time on $i$ for a single walk, and write $T^{[K]}_{i}$ for the first time $i$ is visited by some walk. Then

by Proposition 6.16 (iii), provided $t\leq n^{2}$. So

The bound becomes $1$ for $t_{0}=\frac{25n^{2}}{K^{2}}\log^{2}n$. So

and the issue is to show that $S_{1}$ and $S_{2}$ are $o(t_{0})$. To handle $S_{2}$, split the set of $K$ walks into subsets of sizes $K-1$ and $1$. By independence, for $t\geq n^{2}$ we have $P(C^{[K]}\geq t)\leq P(C^{[K-1]}\geq n^{2})P(C^{[1]}\geq t)$. Then

To bound $S_{1}$ we start with a calculus exercise: for $u>1$

The sum $S_{1}$ is bounded by the corresponding integral over $[t_{0},\infty)$ and the obvious calculation, whose details we omit, bounds this integral by $2t_{0}/(\log n-1)$.

Our second application is to universal bounds on point probabilities. A quite different universal bound will be given in Chapter yyy.

In discrete time one can get essentially the same result, but with the bounds multiplied by $2$, though we shall not give details (see Notes).

Proof. $P_{i}(X_{t}=i)$ is decreasing in $t$, so

where the last inequality is Proposition 6.16 (iii), whose proof is unchanged in continuous time, and which holds for $t\leq n^{2}$. This gives the first inequality when $i=j$, and the general case follows from Chapter 3 yyy.

For the second inequality, recall the definition of separation $s(t)$ from Chapter 4 yyy. Given a vertex $i$ and a time $t$, there exists a probability distribution $\theta$ such that

Then for $u\geq 0$,

Thus, defining $q(t)=\max_{i,j}\left(P_{i}(X_{t}=j)-\frac{1}{n}\right)$, we have proved

Now $q(n^{2})\leq 4/n$ by the first inequality of the Proposition, and $s(\tau_{1}^{(1)})=e^{-1}$ by definition of $\tau_{1}^{(1)}$ in Chapter 4 yyy, so by iterating (6.26) we have

But by Chapter 4 yyy we have $\tau_{1}^{(1)}\leq K\tau^{*}$ for an absolute constant $K$, and then by Corollary 6.9 we have $\tau_{1}^{(1)}\leq 3Kn^{2}$. The desired inequality now follows from (6.27).

Here we reconsider the cat and mouse game discussed in Chapter 4 section yyy. Recall that the cat performs continuous-time random walk on a $n$-vertex graph, and the mouse moves according to some arbitrary deterministic strategy. Let $M$ be the first meeting time, and let $m^{*}$ be the maximum of $EM$ over all pairs of initial vertices and all strategies for the mouse.

Proof. The proof relies on Proposition 6.18, whose conclusion implies there exists a constant $K$ such that

Consider running the process forever. The point is that, regardless of the initial positions, the chance that the cat and mouse are “together” (i.e. at the same vertex) at time $u$ is at most $p^{*}(u)$. So in the case where the cat starts with the (uniform) stationary distribution,

So

Rearranging, $E\min(M,t)\leq 2Knt^{1/2}$. Writing $t_{0}=(4Kn)^{2}$, Markov’s inequality gives $P(M\leq t_{0})\geq 1/2$. This inequality assumes the cat starts with the stationary distribution. When it starts at some arbitrary vertex, we may use the definition of separation $s(u)$ (recall Chapter 4 yyy) to see $P(M\leq u+t_{0})\geq(1-s(u))/2$. Then by iteration, $EM\leq\frac{2(u+t_{0})}{1-s(u)}$. So appealing to the definition of $\tau_{1}^{(1)}$,

But results from Chapter 4 and this chapter show $\tau_{1}^{(1)}=O(\tau^{*})=O(n^{2})$, establishing the Proposition.