Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

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|cite|improve this question

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|cite|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

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.