Asymptotic behavior of a random geometric sum

Question

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$?

Answer 1

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

Answer 2

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}$)