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)$?
$\endgroup$
  • 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 '14 at 9:07
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.

$\endgroup$
  • $\begingroup$ Of course these results address the problem in the symmetric case. $\endgroup$ – Achilleas May 25 '15 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 '15 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 '15 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 '15 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 '15 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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