6
$\begingroup$

Consider the simplest random walk - $X_0 = 0$ and from there on (i.i.d), $X_i=X_{i-1}+1$ with probability $p$ or $X_{i-1}-1$ otherwise.

Let $Y_N$ be the highest point $X$ have reached on the first $N$ steps and similarly, let $M_N$ be the furthest point, that is: $$Y_N=\max_{i\leq N} X_i\\ M_N=\max_{i\leq N}|X_i|$$

  1. Is there a closed-form formula for the distribution of $Y_N$ and $M_N$?
  2. If not, what is $E(Y_N)$ and $E(M_N)$?
  3. If the answer in (1) is negative, how fast can we compute $\Pr(Y_N = y)$?
Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ I don't know about exact formula for $Y_N$ (except as ugly sums - I would be surprised if there is a nice closed form formula) but a good approximation for large $N$ is for example $2P(S_N>x)\leq P(Y_N>x)\leq 2P(S_N>x)+P(S_N=x)$ (of course, $x\geq 0$ and $S_n$ is your random walk). For $P(M_N<x)$ you can write an equation (for small and intermediate values of $N$ it is not hard to solve numerically). For large values of $N$ good approximations can be obtained by Donsker's invariance principle. $\endgroup$
    – ofer zeitouni
    Dec 27, 2014 at 9:07

1 Answer 1

Reset to default
2
$\begingroup$

We have

$P(Y_{n} = r) = {n \choose [\frac{n-r}{2}]}2^{-n}$.

(for a proof see Theorem 2.4 from RANDOM WALK IN RANDOM AND NON-RANDOM ENVIRONMENTS of Pal Revesz, or Feller Vol I).

A simple expression for $E(Y_{n})$ may also be found in the latter reference.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Of course these results address the problem in the symmetric case. $\endgroup$
    – Achilleas
    May 25, 2015 at 4:36
  • $\begingroup$ It's Thm 1 in III.7 of Feller I. For $p\not={1 \over 2}$ replace $2^{-n}$ with $p^kq^{n-k}$ , $k:=\lceil{n+r+1 \over 2}\rceil$. $\endgroup$
    – esg
    Jul 24, 2015 at 14:57
  • $\begingroup$ Furthermore, regarding the second part of the question, the asymptotic distribution for $M_{N}/\sqrt{N}$, as $N \rightarrow \infty$ is Theorem I in the free access paper: Erdös, P., & Kac, M. (1946). On certain limit theorems of the theory of probability. Bulletin of the American Mathematical Society, 52(4), 292-302. I do not know the exact distribution for fixed $N$ for this however. $\endgroup$
    – Achilleas
    Jul 25, 2015 at 19:28
  • $\begingroup$ Apologies, my statement for $p\not={1/2}$ above is false. (The derivation can be done as in Feller, but the sum doesn't simplify). It seems that only in the symmetric case the distribution of $Y_n$ has a simple expression. $\endgroup$
    – esg
    Jul 27, 2015 at 17:42
  • $\begingroup$ But note that in the asymmetric case $$\mathbb{P}(Y_n\geq r)=\mathbb{P}(X_n\geq r)+({p \over q})^r \mathbb{P}(X_n\leq -(r+1))$$ for $r\geq 0$. Thus for the cdf you essentially only need the cdf of the binomial distribution (incomplete Beta function). $\endgroup$
    – esg
    Aug 23, 2015 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.