Let $S_n$ denote a simple random walk with i.i.d. increments $X_i$ such that $P(X_1 = 0) = P(X_1=1) = 1/2$, i.e. $$S_0 = 0, \ S_n = X_1 + \dots + X_n.$$

The behavior of $S_n$ as $n \to \infty$ is clear, namely $S_n /n \to 1/2$ a.s. Now, let $q < 1$ and consider the random sum

$$ \sum_{k=0}^{n-1} q^{S_k}. $$

What can we deduce about the asymptotic behavior of this sum as $n$ tends to infinity? Any ideas how to approach this or references to work that have examined such sums?

Edit: From the answers below, we have $$ \sum_{k=0}^{n-1} q^{S_k} \to \sum_{k=0}^\infty q^{S_k}.$$

Now, for instance $$ \frac{q^{S_n}}{q^{n/2}} \to 1 \quad a.s.$$

My question is, whether we can find a similar sequence for $\sum_{k=0}^{n-1} q^{S_k}$ that describes its growth behavior, i.e. a function $f(n)$ (ideally a deterministic function) such that $$\frac{ \sum_{k=0}^{n-1} q^{S_k}}{f(n)} \to 1 $$ almost surely as $n \to \infty$?


2 Answers 2


$\newcommand\D{\overset D=}$ If $|q|<1$, then, by the strong law of large numbers, there is a positive integer-valued random variable (r.v.) $N$ such that $S_k>k/4$ a.s. and hence $|q|^{S_k}<|q|^{k/4}$ a.s. for all $k\ge N$; so, the sum $\sum_{k=0}^{n-1} q^{S_k}$ converges to a real-valued r.v. $\sum_{k=0}^\infty q^{S_k}$ a.s.

If $|q|\ge1$, then $|q|^{S_k}\ge1$ for all $k$, and hence the sum $\sum_{k=0}^{n-1} q^{S_k}$ diverges.

Concerning the edits to your question (where you apparently assume that $0<q<1$): It is of course incorrect that $\frac{q^{S_n}}{q^{n/2}}\to1$ a.s. Indeed, $\frac{q^{S_n}}{q^{n/2}}\to1$ a.s. can be rewritten as $S_n-n/2\to0$ a.s., which is clearly false -- because, say by the law of the iterated logarithm, $\limsup_n|S_n-n/2|=\infty$.

Next, it was shown above in this answer that the sum $\sum_{k=0}^{n-1} q^{S_k}$ converges to a real-valued r.v. $L:=\sum_{k=0}^\infty q^{S_k}$ a.s. Note that \begin{aligned} \sum_{k=0}^{n-1} q^{S_k}&=1+\sum_{k=1}^{n-1} q^{S_k} \\ &=1+q^{X_1}\sum_{k=1}^{n-1} q^{S_k-X_1} \\ &=1+q^{X_1}\sum_{k=1}^{n-1} q^{T_{k-1}} \\ &=1+q^{X_1}\sum_{j=0}^{n-2} q^{T_j}, \end{aligned} where $T_j:=S_{j+1}-X_1=X_2+\dots+X_{j+1}\D S_j$ (with $T_0:=0$) and $\D$ denotes the equality in distribution. Note also that the $T_j$'s are independent of $X_1$. Letting now $n\to\infty$, we get the key identity for the limit r.v. $L$: $$L\D1+q^X L, \tag{1}$$ where $X\D X_1$ and $X$ is independent of $L$.

From here, it follows that the r.v. $L$ is non-degenerate, that is, $P(L=c)\ne1$ for any real $c$. Indeed, otherwise (1) would imply that $c=1+q^X c$ a.s., which is of course false.

Thus, the condition $$\frac{\sum_{k=0}^{n-1} q^{S_k}}{f(n)}\to1\quad\text{a.s.}$$ holds with $f(n)\equiv L$, but it cannot hold for any deterministic $f$.

  • $\begingroup$ Thank you very much. My main question was still something more precise (I did not make it clear enough before). See my Edit. $\endgroup$
    – MMM
    Jun 18, 2020 at 14:00
  • $\begingroup$ Thanks. The part was with $q^{S_n} / q^{n/2} \to 1 $ was stupid. It seems that it is difficult to match the growth behavior of $q^{S_n}$. Would you have any idea for what (random) function $f(n)$, we have $q^{S_n} / f(n) \to 1$ a.s.? $\endgroup$
    – MMM
    Jun 18, 2020 at 23:19
  • $\begingroup$ @BenC. : The obvious random $f(n)$ such that $q^{S_n}/f(n)\to1$ is $q^{S_n}$, and I don't think you can get anything more transparent than that. $\endgroup$ Jun 19, 2020 at 11:27
  • $\begingroup$ I thought that this might be possible, because at least in expectation $E (q^{S_n}) / ((1+ q)/2)^n \to 1$. So I thought that maybe the same holds without the expectation... $\endgroup$
    – MMM
    Jun 20, 2020 at 20:13
  • $\begingroup$ @BenC. : The convergence of the expectations by itself may mean little about the convergence of the corresponding random variables, as it is the case here. Other than this, I have nothing to add to my answer and comments. $\endgroup$ Jun 21, 2020 at 2:17

The function $\lim \limits_{n \to \infty} f(x)=\sum_{k=0}^{n-1} q^{s_k}x^k$ becomes,

$f(x)=\sum_{k=0}^{\infty} q^{s_k}x^k$.

From root test we get that radius of convergence of the series is $\lim \limits_{n \to \infty} |q|^{\frac{s_n}{n}}=\sqrt{|q|}$.

Hence, $f(1)$ converges for $q<1$.

But for $q \geq1$ and $n \to \infty, \sum_{k=0}^{n-1} q^{s_k}$ is asymptotic to $nq^{\frac{n}{2}}$

( as $\lim \limits_{n \to \infty} \frac{s_n}{n}=\frac{1}{2}$)

  • $\begingroup$ Could you please explain why the asymptotic claim before the last limit statement holds? $\endgroup$
    – Todd Trimble
    Jun 18, 2020 at 13:02

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.