Forward Jump Random Walk on a Cycle Graph and Its Hitting Time
The problem
Random walks on cycle graphs are useful models for periodic systems, but restricting movement to forward jumps changes arrival and hitting-time behaviour. Exact formulas are needed without relying exclusively on eigenvector methods.
Who benefits:
- Probability and stochastic-process researchers
- Graph-theory and combinatorics specialists
- Network and electrical-circuit analysts
- Educators and simulation developers
Method
On a cycle with d states, each step is an independent uniform forward jump X in {1,...,m}. The paper counts paths to derive the arrival-state probability mass function in complex-root, trigonometric-sum, and combinatorial forms. Recurrences and probability generating functions then yield the first-hitting-time distribution, its exact expected value, and its variance. A twelve-state circular-board experiment illustrates and validates the formulas.
Results
The arrival distribution approaches uniformity faster as the jump limit m or the number of steps n increases, and is uniform immediately when m=d. In the d=12 experiment, the expected hitting time ranges from 7.75 to 12 steps: m=4 is fastest and m=12 is longest. Larger allowed jumps generally increase both the mean and variability of hitting time, while graph size has comparatively little influence in the studied setting.
