Generalized density functions on the natural numbers If $a_1,a_2,\dots$ are IID random bits (correction as per Anthony Quas: these "bits" are $+1$ and $-1$ with equal probability), then with probability 1, the set of natural numbers $n$ such that $a_1+a_2+\dots+a_n \leq 0$ has lower density 0 and upper density 1, so it has no density in the ordinary sense. Still, I wonder if there is a principled way to generalize the manner in which we assign "densities" to subsets of the natural numbers in such a fashion that, with probability 1, the aforementioned set has generalized density 1/2 -- and, more generally, for every real $t$, the set of $n$ such that $(a_1+a_2+\dots+a_n)/\sqrt{n} \leq t$ has generalized density equal to the probability that the relevant Gaussian random variable has value less than $t$.
 A: So I think a logarithmic average will do the trick for you. If you define $Y_n$ to be the sign of $a_1+\ldots+a_n$, then calculations with Brownian motion in place of random walk suggest the covariance of $Y_n$ and $Y_m$ with $m<n$ is approximately $(1/2\pi)\arctan\sqrt{m/(m-n)}$. Now define $S_N=(1/\log N)(Y_1/1+\ldots +Y_N/N)$. This has expectation 0 and variance $\approx 1/\log N$, which gives a systematic way of saying that the random walk is "positive half the time". 
A: EDIT: As pointed out by Anthony Quas below, this approach suffers from what looks to be a quite serious measurability issue.
A more abstract approach: 
Let $\theta$ be a shift-invariant probability mean   on $\mathbb{N}$  (i.e., a finitely additive but not necessarily $\sigma$-additive set function with total weight 1 such that $\theta(\{n : n+1 \in A\}=\theta(A)$ for every subset $A$ of $\mathbb{N}$). (Such a mean can be obtained e.g. by taking a subsequential limit of the functions sending $A$ to $\frac{1}{n}\sum_{x\in[0,n]}1(x\in A)$.)
Let's define $A_+=\{n : a_1 + \cdots + a_n >0\}$, $A_0=\{n : a_1 + \cdots + a_n =0\}$ and $A_-=\{n : a_1 + \cdots + a_n <0\}$.


*

*The values of $\theta(A_+)$ and $\theta(A_-)$ are non-random by e.g. the Hewitt-Savage 0-1 law.

*By symmetry, $\theta(A_+)=\theta(A_-)$.

*$\theta(A_0)=0$ for every choice of $\theta$ since the upper density of $A_0$ is zero .


It follows that $\theta(A_+)=\frac{1}{2}$ almost surely.
(here's a reference from google for the third item above https://books.google.ca/books?id=eFFyBgAAQBAJ&lpg=PA16&ots=srDM7KjW76&dq=translation%20invariant%20means%20and%20upper%20density&pg=PA16#v=onepage&q=translation%20invariant%20means%20and%20upper%20density&f=false)
