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

Possible Duplicate:
Proving that 1- and 2-d simple symmetric random walks return to the origin with probability 1

This is a basic question but I was wondering if there was a simple proof (I have a rather complex one).

The problem is: Given a symmetric random walk ($P(X_i=1)=P(X_i=-1)=0.5$) and $S_n = \sum_{i=1}^n X_i$, define $T$ as $T=\inf\{n\geq0:S_n=a\}$, $S_0=0$. Prove that $T$ is almost surely finite, $P(T<\infty)=1$.


share|cite|improve this question

marked as duplicate by Nate Eldredge, Byron Schmuland, Did, Henry, Asaf Karagila Jul 23 '12 at 22:08

This question was marked as an exact duplicate of an existing question.

This is a multi-duplicate (and typical (homework)). You could try to compute $P(T_a\lt T_{-b})$, and let $b\to+\infty$. – Did Jul 23 '12 at 8:53

The symmetric random walk is a recurrent and irreducible Markov Chain, thus by recurrence theorem $f_{ij}=1$ where $f_{ij}$ is the probability that starting from $i$ we have $X_n=j$ for some $n\geq 1$, that is $P(T<\infty)=1$.

share|cite|improve this answer
In other words: $P(T\lt\infty)=1$ because $P(T\lt\infty)=1$. – Did Jul 23 '12 at 16:29

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