Classical marked-set hitting bound from a spectral gap

Let $u_U=\mathrm{\mid }U{\mathrm{\mid }}^{-1\mathrm{/}2}{\mathbf{1}}_U$. For the uniform initial law on $U$, [F2] gives $\mathrm{Pr}({\tau }_{\mathcal{M}}>t)=⟨u_U,P_{UU}^t{u}_U⟩$. Since $P_{UU}$ is positive semidefinite, it has eigenvalues in $[0,1-\delta \epsilon ]$ by [F1]; its $t$th power therefore has operator norm at most $(1-\delta \epsilon {)}^t$. [F3] and $\mathrm{\parallel }{u}_U\mathrm{\parallel }=1$ prove the survival bound, including $t=0$.

Put $a=\delta \epsilon$. For $0<a<1$, the nonnegative-integer tail formula in [F2] and the finite geometric partial sums give $\mathbb{E}{\tau }_{\mathcal{M}}={\sum }_{t\ge 0}\mathrm{Pr}({\tau }_{\mathcal{M}}>t)\le {\sum }_{t\ge 0}(1-a{)}^t=1\mathrm{/}a$. For the constant-success bound choose $t=\lceil 1\mathrm{/}a\rceil$. Since $(1-a)(1+a)=1-a^2\le 1$, we have $1-a\le (1+a{)}^{-1}$; the finite binomial expansion gives $(1+a{)}^t\ge 1+ta\ge 2$. Hence $(1-a{)}^t\le (1+a{)}^{-t}\le 1\mathrm{/}2$. If $a=1$, step 1.1 gives zero no-hit probability for every $t\ge 1$, so one step suffices. The case $\mathcal{M}=X$ is immediate from the definition.