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



Asymptotic behavior of a random geometric sum
$\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$.


