4
$\begingroup$

I have a random walk on $\mathbb{Z}$ with starting point $0$ and with length $n$ and possible steps to right, left or stay where you are, all with the same probabilities. I am interested in exact probability that the walk will visit $k$ distinct values.

I think this should be known but I cannot find such result.

Improve this question
$\endgroup$
1
  • 3
    $\begingroup$ Not an answer, but you should check out the reflexion principle for Brownian motion (obviously the analogous result for a simple random walk is also true) since it allows one to calculate the exact distribution of the maximum value of the random walk on an interval (and the minimum, but in principle you would need the joint distribution of both to answer your question). This should give you an idea of what to expect for large $n$ and $k$ of order $\sqrt{n}$. $\endgroup$
    – Pablo Lessa
    Commented May 23, 2016 at 11:57

1 Answer 1

Reset to default
2
$\begingroup$

Just an addition to Pablo Lessa's comment. If probability to stay at a point is zero, then you have a simple random walk and the Reflection Principle is valid. So, your question will follow if you find the joint distribution of the maximum and minimum, as the simple random walk visits all points between them. The exact formula for the joint distribution of the maximum and minimum can be found in e.g. book of Billingsley, Convergence of probability measures, Chapter 2.11. The question can also be reformulated as the distribution of the first exit time from an interval [-a,b]. Then, another reference (for the zero-mean random walk) is this paper http://dx.doi.org/10.1214/aoms/1177706262 of Kemperman, Asymptotic expansions for the Smirnov test for the range of cumulative sums. Ann. Math. Statist. 30 1959 448–462. The more general case (when probability to stay at 0 is greater than 0) can be treated similarly to the above references.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Can you please provide exact number of theorem in Billingsley? Because I see only trigonometric series in 2.11. $\endgroup$
    – user92031
    Commented Jul 20, 2016 at 18:17

You must log in to answer this question.