Skip to Main content Skip to Navigation
Conference papers

Non Uniform Random Walks

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.
Complete list of metadata

Cited literature [3 references]  Display  Hide  Download

https://hal.inria.fr/hal-01183925
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 12, 2015 - 9:06:57 AM
Last modification on : Wednesday, July 31, 2019 - 3:24:16 PM
Long-term archiving on: : Friday, November 13, 2015 - 11:37:10 AM

File

dmAC0132.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01183925, version 1

Collections

Citation

Nisheeth Vishnoi. Non Uniform Random Walks. Discrete Random Walks, DRW'03, 2003, Paris, France. pp.345-358. ⟨hal-01183925⟩

Share

Metrics

Record views

190

Files downloads

861