---
# System prepended metadata

title: Quick Probability Analysis

---


# Quick Probability Analysis
#### Date: Feb 14, 2023
**Lemma**: Probability that a $t$-step random-walk traverses through all the edges of a cycle of length $\sqrt{\ell}$ is less than $2 \exp (-\ell/(8t))$. 

Here, we are thinking of $t \approx \sqrt{\ell^2} = \ell$. Then, repeating this $\sqrt{\ell}$-times, we get that 
$$ \mathbb{P} \left[ \text{finish cycle with } t \sqrt{\ell} \text{ length rw} \right] \leq \sqrt{\ell} \exp\left(\frac{-\ell}{8t}\right).$$

For every $\sqrt{\ell}$ segmet of a cycle, we are taking $t$-steps. Since there are a total of $\sqrt{\ell}$-segments, we get that 

$$ \mathbb{P}\left[ \text{no return to any high-degree node} \right] \leq t^{-\sqrt{\ell}}.$$

Therefore, we get that for a length $t \sqrt{\ell}$-length random walk 
$$ \begin{align}
\mathbb{P} \left[ \text{finish cycle and no escape} \right] & \leq \sqrt{\ell} \exp\left(\frac{-\ell}{8t}\right) \cdot t^{-\sqrt{\ell}} \\
& \leq \sqrt{\ell} \exp\left(-\frac{\ell}{8t} - \frac{\sqrt{\ell} \ln t}{t}\right) .
\end{align}$$