# Expectation of first positive value in random walk

Let $p$ be a parameter in $]0,1[$. Let $(X_k)_{k\geq 0}$ be an independent, identically distributed sequence of random variables, such that each $X_k$ takes values only in $\lbrace -1, \frac{1-p}{p} \rbrace$ and $P(X_k=-1)=1-p$ (so that $X_k$ has mean $0$). Let $S_n=X_1+X_2+ \ldots +X_n$ for $n\geq 1$ and let $N$ denote the smallest integer such that $S_{N} > 0$ (it is well known that $N$ exists almost surely). What is the expectation of $S_{N}$ ?

If $p$ is of the form $1-\frac{1}{k}$ where $k$ is an integer, it is easily seen that $S_{N}$ is constant and equal to $\frac{1}{k-1}$.

Update 10/26/2010: In general, $S_N$ can only take a finite number of values, so the expectation is finite, as noted in the comments below. It seems that the distribution of $S_N$ should be computable using some simple algebra, but I was unable to do this. The finite-set of values property allows one however to compute $E(S_N)$ to a reasonable acurracy for a given $p$. For $p=\frac{1}{3}$, the expectation is larger than 1 and does not seem to be rational.

• There is an obvious typo: if $p$ is of the form $1−1/k$ where $k$ is an integer, then $S_N$ is equal to $1/(k−1)$ – Shai Covo Oct 26 '10 at 15:05
• JBL: In the case $p = 1/3$, $X_k$ is $-1$ with probability $2/3$ and $2$ with probability $1/3$. So $S_n$ is positive-integer-valued for all $n$. In particular $S_N$ only takes the values $1$ or $2$, and therefore has expectation at least $1$. – Michael Lugo Oct 26 '10 at 16:37
• @ Shai : corrected the typo, thanks. – Ewan Delanoy Oct 27 '10 at 8:23
• @JBL : For $p=\frac{1}{3}$ I can show that the expectancy is greater than 1. – Ewan Delanoy Oct 27 '10 at 8:24
• OK. I meant that $S_n$ is integer-valued for all $n$, and so $S_N$ always takes positive integer values. – Michael Lugo Oct 27 '10 at 17:04

## 2 Answers

You are looking for the "mean ladder height" of a random walk. There is a (not very tractable) formula due to Spitzer that gives the answer:

$$E(S_N)={\sigma\over\sqrt{2}} \exp\left$$\sum_{n=1}^\infty {1\over n}(P(S_n<0)-1/2)\right$$$$

Here $\sigma^2$ is the variance of the jump distribution. Maybe it would be possible to work this out in your special case.

 Chow, Yuan S. On Spitzer's formula for the moment of ladder variables. Statist. Sinica 7 no. 1, 1997, 149–156.

 Spitzer, Frank A Tauberian theorem and its probability interpretation. Trans. Amer. Math. Soc. 94, 1960, 150–169.

• The $1/n$ term should be moved inside the sum. – Shai Covo Oct 27 '10 at 18:49
• Note, however, that the above formula for $E(S_N)$ corresponds to $N=\inf\{n \geq 1: S_n \geq 0\}$, whereas in our case $N=\inf\{n \geq 1: S_n > 0\}$. – Shai Covo Oct 27 '10 at 19:59

(EDITED, to comply with quite accurate objections by Louigi and Byron)

Assume that with full probability $X_k$ is either $-1$ or a random positive integer (this includes the setting of the question when $p=1/(k+1)$ with $k$ a positive integer but note that $X_k$ may take more than one positive integer values). Then, Wiener-Hopf factorization formula becomes simple enough to compute the distribution of $S_N$.

More precisely, let $N$ denote the first time $n\ge1$ such that $S_n>0$ (as in the OP's post) and let $M$ denote the first time $n\ge1$ such that $S_n\le 0$ (note the "lower than or equal to"). In the centered and bounded case the OP is interested in, $N$ and $M$ are both almost surely finite and Wiener-Hopf formula reads $$(1-E(e^{iuS_N}))(1-E(e^{iuS_M}))=1-E(e^{iuX}),$$ for every real number $u$ and every $X$ distributed as the steps $X_k$. Here, $S_M=-1$ on $[X_1=-1]$ and $S_M=0$ on $[X_1>0]$. This yields $$q(1-e^{-iu})E(e^{iuS_N})=E(e^{iuX};X>0)-p,$$ with $q=P[X=-1]$ and $p=1-q=P[X>0]$. This provides the full distribution of $S_N$ and, differentiating both sides at $u=0$, the expectation of $S_N$. The end result is $$E(S_N)=E(X+X^2;X>0)/(2q).$$ If $X=-1$ or $X=k$ with $k$ a positive integer, then $[X > 0]=[X=k]$ and $p=1/(k+1)$, and one sees that $S_N$ is uniformly distributed on the integers from $1$ to $k$ and that $E(S_N)=(k+1)/2$.

• This would be right except that it is not necessarily true that $S_M=0$ on the event $X_1 > 0$. If $p=2/3$, for example, then $X$ takes values $-1$ and $1/2$, So $S_M$ can take the value $-1/2$. – Louigi Addario-Berry Oct 29 '10 at 15:50
• @Didier: Why does $S_M=0$ on $X_1>0$? When $p=1/3$, you could jump once to the right, then once left, and find yourself at -1/2. This is the first time that the process is $\leq 0$. However, I'm still hopeful that the Wiener-Hopf approach may lead to a solution! – user6096 Oct 29 '10 at 15:54
• @Louigi: You beat me! – user6096 Oct 29 '10 at 15:54
• @Louigi, Byron: Argh... You are right, of course; the argument works only if the upward steps are integer valued. Sorry, I shall modify the answer. – Did Oct 29 '10 at 16:38