Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Assume $(X_n)_{n\geq1} \subseteq \mathbb {Z}$ and $(Y_n)_{n\geq 1} \subseteq \mathbb {Z}$ to be iid, $X_i \sim Y_i$ and such that $S_n=\sum_{i=1}^n(X_i-Y_i)$ is a strongly aperiodic, recurrent random walk. Let $T \subseteq \mathbb{N}$ be a discrete random variable.

With this information can we then say anything about $P(\exists m, \;S_m =T)$?

Thank you.

share|cite|improve this question
Since I gave some incomplete answers to your previous related question, I'll try this in a comment first :-). If your definition of recurrence is that almost surely $S_m=0$ infinitely often (if not, what's your definition of recurrence?), then the walk has infinitely many tries to get from $0$ to $T$, and since it's strongly aperiodic each try has a non-zero probability of succeeding; it follows that it reaches $T$ with probability $1$? – joriki Oct 28 '12 at 15:46
Not sure you meant to write there exists a $m$ s.t. $P(S_m =T)$. Rather it seems that you are asked about $P(\exists m,S_m=T)$. – Did Oct 28 '12 at 15:47
did: I've corrected it, I meant what you said. Joriki: That is what I think too, I just want to be sure. – Henrik Oct 28 '12 at 15:59
up vote 2 down vote accepted

Let $U=\{x\in\mathbb Z\mid\exists n\geqslant0,\mathbb P(S_n=x)\ne0\}$ denote the union of the supports of the random variables $S_n$. Let $V=\{S_n\mid n\geqslant0\}$ hence the event $A=[\exists m, S_m=T]$ is $A=[T\in V]$. Note that $U$ is a deterministic subset of $\mathbb Z$ and $V$ is a random subset of $\mathbb Z$.

Since $(S_n)$ is irreducible on $U$ and recurrent, $V=U$ almost surely. In particular, $A=[T\in U]$, up to a negligible event. If $(S_n)$ is furthermore aperiodic, by hypothesis $\mathbb Z=U-U$. The increments of $(S_n)$ are symmetrically distributed, hence in our case, $U-U=U$.

Finally, $A=[T\in \mathbb Z]=\Omega$, up to a negligible event, that is, $\mathbb P(\exists m, S_m=T)=1$.

share|cite|improve this answer
The first version was sloppy, please see the revised one. – Did Oct 29 '12 at 8:43
Thank you for your answer! Would you mind elaborating on the $\mathbb {Z}=U-U$ part? Is it a setminus? And why does the statement hold? – Henrik Oct 29 '12 at 20:46
A setminus? Heaven's, no! Say, which definitions of the aperiodicity and the strong aperiodicity of a random walk do you use? – Did Oct 29 '12 at 21:28
Oh yea, sorry. Random walks was a bit new to me, now it makes sense. Thanks for your answer! – Henrik Nov 3 '12 at 12:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.