Asymptotic behavior of a random geometric sum

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

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

• Thank you very much. My main question was still something more precise (I did not make it clear enough before). See my Edit.
– MMM
Jun 18, 2020 at 14:00
• 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.?
– MMM
Jun 18, 2020 at 23:19
• @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. Jun 19, 2020 at 11:27
• 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...
– MMM
Jun 20, 2020 at 20:13
• @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. 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}$$)

• Could you please explain why the asymptotic claim before the last limit statement holds? Jun 18, 2020 at 13:02