Random Walks

Simulation of random walks on various objects

Hitting time of returning to origin is $h_{0,0} = \frac{1}{\pi(0)}$. We also have $\pi(0) = \frac{\deg(0)}{2m}$. Thus, $h_{0,0} = \frac{2m}{\deg(0)}$.

1. Hypercube ($d$ dimensions)
   • $h_{0,0} = \frac{2 \cdot \left( d \cdot 2^{d-1} \right)}{d} = 2^d$
2. Bounded Line ($n$ nodes)
   • $h_{0,0} = \frac{2 \cdot \left( n - 1 \right)}{1} = 2n - 2$
3. Unbounded Line
   • $m = \infty$
   • $h_{0,0} = \frac{2 \cdot \infty}{2} = \infty$
4. Complete ($n$ nodes)
   • $h_{0,0} = \frac{2 \cdot \left( \frac{n(n - 1)}{2} \right)}{n - 1} = n$
5. Complete Bipartite ($\frac{n}{2}$ left nodes)
   • $h_{0,0} = \frac{2 \cdot \frac{n^2}{4}}{\frac{n}{2}} = n$
6. Loop ($n$ nodes)
   • $h_{0,0} = 1 \div \frac{1}{n} = n$