Take the 2-minute tour ×

A random walk $X$ is a sequence of elements of the set $\{-1, 0, 1\}$ and $X_i$ denotes the $i^{th}$ element of $X$. Consider the set $C_n$ of all random walks of length $n$ and the set $C_\infty = \lim_{n \rightarrow \infty} C_n$ ($|C_\infty| = 2^{\aleph_0}$).

Now define the statement $S(X,k) = \exists (1 \le j \le |X|) \forall (j \le h \le |X| )|\sum_{m=1}^h X_m| \ge k$

Also consider the following potentially useful function $S\#(X,k) = \left\{ \begin{array}{lr} 1 & : & S(X,k)\\ 0 & : & \neg S(X,k) \end{array} \right.$

Now obviously over random walks of a fixed length, $S$ will be true more often for $k$ near $0$. I am wanting to ask about this process asymptotically as the random walks increase in length. I know that random walks of infinite length are recurrent, however there do exist walks $X$ s.t. $|X| = \aleph_0$ and $S(X,k) = True$ (e.g. $S(\{1, 1, 1, 1, 1, ...\}, 3)$).

How are the cardinalities $|\{X : X \in C_\infty \wedge S(X,k)\}|$ distributed across non-negative integer values of $k$? Are the cardinalities $2^{\aleph_0}$ when $k=0$ and $\aleph_0$ otherwise?

share|improve this question
add comment

1 Answer

Fix $X \in C_\infty$; then $S(X,k)$ iff there is some $n_0$ such that $$\left\vert\sum\limits_{i=1}^n X_i\right\vert \ge k$$ whenever $n \ge n_0$. It’s easy to see that for each $k\ge 0$ there are $2^{\aleph_0}$ such random walks: start with a sequence of $k$ $1$’s and append any infinite sequence whose terms are all $0$ or $1$. Since there are $2^{\aleph_0}$ infinite sequences of $0$’s and $1$’s, there are $2^{\aleph_0}$ random walks $X \in C_\infty$ such that $S(X,k)$.

share|improve this answer
This seems right, and it resolves my problem in the setting I need it solved. For the sake of curiousity: what happens if we make a random walk sequences of {-1, 1}? –  Ross Snider Sep 25 '11 at 13:37
I suppose you could do the same thing by using sequences of -1 followed by 1 in the place of 0 with the same argument. Thanks! –  Ross Snider Sep 25 '11 at 13:50
add comment

Your Answer


