Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Could someone give me some tips?

Let $e_1,e_2,\dots$ be iid normal mean 0 variance 1. Let $X_t := e_1+\cdots+e_t$, for $t=1,2,\dots$ and $X_0 := 0$. (So we have a discrete-time random walk whose steps are iid $N(0,1)$)

Define first-hitting time $T_0 := \inf\{t>0 : X_t <0\}$.

What is the CDF of $T_0$, i.e. what is $\mathbb{P}(T_0 \leq t)$?

And second (probably more difficult) question: what is $\mathbb{E}( X_t \mid T_0 > t )$?

Thank you.

share|cite|improve this question
up vote 2 down vote accepted

Here is an answer for your first question.

This is easier than dealing with simple symmetric random walk. When the steps are diffuse, you don't have to worry about ties or parity.

You are looking at a Brownian motion, evaluated at integer times $t$. Then defining $$T_0=\inf(t > 0, t\in {\mathbb Z}: B_t < 0)$$ and integer $t > 0$ we have $$ P(T_0 > t)=P(B_1 > 0,B_2 > 0,\dots, B_t > 0)={2t\choose t}/4^t.$$

It turns out that the answer is the same for any random walk with symmetric, diffuse increments. This follows from Theorem 9.11 of Kallenberg's Foundations of Modern Probability (2nd edition), for example. (A great book, by the way!)

The key insight is that you should not to try to solve the probability exactly, but rather set up a recursion that the probabilities solve. Setting $p(t)=P(T_0>t)$ for integer $t\geq 0$, you can show that for any $t$ we have $\sum_{j=0}^t p(t-j)p(j)=1$.

The probabilistic justification for the recursion formula is that every path of a diffuse, symmetric, discrete-time random walk can be broken into two positive paths at the time $j$ where it achieves its minimum value.

You may also find Konrad Jacob's book Discrete Stochastics to be useful.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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