Let $S_n$ be a random walk defined as $S_n = X_1 + \dots + X_n $ ($S_0 = 0$), where $X_i$ are i.i.d. with $P(X_i = 0) = P(X_i=1) = 1/2$. Let $r \in (0,1)$. My question is: what is the almost sure limit of $$ \sum_{k=0}^{n} r^{S_n - S_k}.$$
When considering $\sum_{k=0}^{n} r^{S_k}$, we should have that it converges to $\sum_{k=0}^{\infty} r^{S_k}$ a.s., but what about the case above?
Let $$A_n = \sum_{k=0}^n r^{S_n - S_k} = \sum_{k=0}^{n-1} r^{X_n + S_{n-1} - S_k} + 1 = r^{X_n} A_{n-1} + 1$$
where we note that $X_n \perp A_{n-1}$. Now, if $A_n$ converge in probability, then we would expect a Cauchy behavior in terms of their probabilities i.e. if $X_n$ converges to $X$ in probability, $$\lim_{n,m \rightarrow 0} P(|X_m - X_n| > \epsilon) \rightarrow 0 \:\: \; \forall \epsilon $$ and this needs to hold for all diverging sequences $m_n, n_n$.
(This is part of theorem 4 in this PDF) http://eceweb1.rutgers.edu/~csi/chap6.pdf
However, let's take an $\epsilon \in (0, 1)$, $P(|A_n - A_{n-1}| > \frac{1}{2}) \geq 1/2$, since when $X_n = 0, A_n = A_{n-1} + 1$, and that happens with probability 1/2. So, this limit is not 0, so you don't have any convergence in probability, which means you cannot be converging almost surely either.
The intuition is that unlike in the example you gave, there is a very high amount of dependence on the value of $X_n$. (Whereas in the example you gave $X_n$ only shows up on the last term, which is already almost surely arbitrarily small as $n \rightarrow \infty$, so the value of $X_n$ basically does not change anything)