Expectation of first positive value in random walk

Question

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.

Answer 1

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.

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

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

Answer 2

(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$.