Non Uniform Random Walks - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2003

Non Uniform Random Walks

Résumé

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.
Fichier principal
Vignette du fichier
dmAC0132.pdf (122.03 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01183925 , version 1 (12-08-2015)

Identifiants

Citer

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

Collections

TDS-MACS
129 Consultations
699 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More