Given εi ∈ [0,1) for each 1 < i < n, a particle performs the following random walk on {1,2,...,n}:
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 εm it decides to go back, in which case it chooses a point u.a.r. from {m+1,...,n}. With probability 1-ε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 problem arise 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 ε's: εi = (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 ε's. As α varies from infinity to 1, this time goes from Θ(log n) to Θ (n).
Finally we study the behavior of the expected convergence time as a function of ε. It remains an open question to determine whether this quantity increases when all ε's are increased. We give some preliminary results to this effect.