Non Uniform Random Walks

Nisheeth K. VishnoiDRW 2003 · OpenReview

TL;DR

This paper analyzes a non-uniform random walk on a line where a particle can jump both forward toward a target and backward toward its starting point. The author proves that for a specific family of "back-jump" probabilities, the expected time to reach the target varies from $\Theta(\log n)$ to $\Theta(n)$, providing a theoretical framework for understanding randomized algorithms with "back buttons."

What Problem Does This Paper Address?

In classical one-dimensional random walks, a particle usually moves to adjacent neighbors. However, many problems in Theoretical Computer Science involve "jumpy" behavior. For example, a randomized algorithm searching for the $k$-th smallest element in a list effectively performs a random walk where it jumps to a random smaller sub-problem.

The author investigates a specific model: a particle on the set $\{1, 2, \dots, n\}$.

  • From the far end ($n$), it jumps uniformly at random to any smaller number.
  • From any intermediate point $m$, it has a probability $\epsilon_m$ of jumping "backward" (to a larger number) and a probability $1-\epsilon_m$ of jumping "forward" (to a smaller number).

The core question is: What is the expected time to reach state 1 starting from state $n$? While simple cases (like $\epsilon = 0$) are well-understood, the introduction of non-uniform "back-jumps" makes the analysis significantly more complex.

Methods

The author treats the walk as a Markov Chain. The primary tool used is the fundamental matrix $N = (I - Q)^{-1}$, where $Q$ is the transition matrix of the non-absorbing states. In Markov chain theory, the entries of this matrix $n_{ij}$ represent the expected number of times the process visits state $j$ given that it started in state $i$.

The paper relies on two key technical lemmas (3.5 and 4.1) regarding the structure of this matrix. The author uses clever determinant-based proofs to show that for certain configurations, the expected number of visits to a state $i$ is invariant to the starting position $j$, provided $j$ is "behind" or "ahead" of $i$ in specific ways. This symmetry allows the author to reduce a complex system of linear equations into a manageable $3 \times 3$ system to solve for the expected absorption time.

Datasets

Not discussed in the paper. This is a theoretical mathematics and computer science paper; results are derived through formal proofs rather than empirical testing on datasets.

Key Insights and Ideas

  • Start-Position Independence: A surprising "aha moment" is Lemma 3.5, which shows that the expected number of visits to state $i$ (before reaching 1) is the same regardless of which state $j > i$ the particle starts from. This simplifies the global behavior of the walk into local properties.
  • The Parameterized Family: The author identifies a specific family of probabilities: $$\epsilon_i = \frac{n-i}{n-i + \alpha(i-1)}$$ By tuning the parameter $\alpha$, the walk can be made to mimic different algorithmic behaviors. This parameterization acts as a "dial" that shifts the walk's efficiency.

  • Monotonicity Challenges: Intuitively, if you increase the probability of jumping backward ($\epsilon$), the time to reach the target should increase. However, proving this "obvious" fact is mathematically non-trivial. The author provides preliminary results showing that the expected position of the particle is monotonic under certain conditions, but the general case for absorption time remains a difficult open problem.

Key Results

The paper categorizes the expected time $E[X_n]$ based on the value of $\alpha$:

  1. $\alpha = \infty$ (The "No Back-Jump" Case): This corresponds to $\epsilon_i = 0$. The expected time is $\Theta(\log n)$. This matches the known complexity of optimal randomized selection algorithms.
  2. $\alpha = n$: Even with some back-jumping, if the probability is scaled correctly, the expected time remains $\Theta(\log n)$.
  3. $\alpha = 1$: When back-jumps are more frequent, the expected time slows down significantly to $\Theta(n)$.

These results show that there is a "tipping point" where back-jumps transition the algorithm from logarithmic efficiency to linear slowness.

Limitations and Future Work

  • General $\epsilon$ Vectors: The current analysis relies heavily on the specific parameterized family of $\epsilon_i$. Finding tight bounds for an arbitrary vector of probabilities remains difficult.
  • The Monotonicity Conjecture: The author leaves it as an open question to formally prove that increasing any $\epsilon_i$ always increases the expected absorption time. While it seems intuitive, the "jumpy" nature of the walk makes the standard coupling arguments difficult to apply without restrictions.
  • Concentration of Measure: The paper focuses on the expected time. The author suggests that investigating the distribution of the time $X_n$ (e.g., how much it deviates from the mean) would be a valuable next step.

Summary updated

Abstract

Given $\epsilon _i ∈ [0,1)$ for each $1 < i < n$, a particle performs the following random walk on $\{1,2,...,n\:\}$par If the particle is at $n$, it chooses a point uniformly at random (u.a.r.) from $\{1,...,n-1\}$. If the current position of the particle is $m (1 < m < n)$, with probability $\epsilon _m$ it decides to go back, in which case it chooses a point u.a.r. from $\{m+1,...,n\}$. With probability $1-\epsilon _m$ it decides to go forward, in which case it chooses a point u.a.r. from $\{1,...,m-1\}$. The particle moves to the selected point. What is the expected time taken by the particle to reach 1 if it starts the walk at $n$? Apart from being a natural variant of the classical one dimensional random walk, variants and special cases of this problemarise in Theoretical Computer Science [Linial, Fagin, Karp, Vishnoi]. In this paper we study this problem and observe interesting properties of this walk. First we show that the expected number of times the particle visits $i$ (before getting absorbed at 1) is the same when the walk is started at $j$, for all $j > i$. Then we show that for the following parameterized family of $\epsilon 's: \epsilon _i = \frac{n-i}{n-i+ α · (i-1)}$,$1 < i < n$ where $α$ does not depend on $i$, the expected number of times the particle visits $i$ is the same when the walk is started at $j$, for all $j < i$. Using these observations we obtain the expected absorption time for this family of $\epsilon 's$. As $α$ varies from infinity to 1, this time goes from $Θ (log n) to Θ (n)$. Finally we studythe behavior of the expected convergence timeas a function of $\epsilon$ . It remains an open question to determine whether this quantity increases when all $\epsilon 's$ are increased. We give some preliminary results to this effect.
BibTeX
@inproceedings{vishnoi2003non,
  author = {Nisheeth K. Vishnoi},
  title = {{Non Uniform Random Walks}},
  booktitle = {DRW},
  year = {2003},
  url = {https://openreview.net/forum?id=CnWx4pRJmJr},
}
Figure