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$.

$\begingroup$ Is a bit $\pm 1$? Otherwise it's hard for the sum to be $\le 0$. $\endgroup$ – Anthony Quas Oct 2 '15 at 19:31

5$\begingroup$ Wouldn't a logarithmic average do it? $D(A)=\lim_{N\to\infty}1/(\log N)\sum_{n\le N}\mathbf 1_{n\in A}/n$. If not logarithmic, then certainly iterated logarithmic. $\endgroup$ – Anthony Quas Oct 2 '15 at 19:42
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/(mn)}$. 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".

$\begingroup$ Modulo Brownian motion calculations that I haven't checked, this looks good, as far as it goes. But how do we get to "converges to 1/2 with probability 1"? Given how slowly 1/log $N$ goes to 0, I don't see why the outliers in the sequence $S_1,S_2,...$ are still constrained to go to 0. There's probably a simple argument for this, but off the top of my head I don't see it. $\endgroup$ – James Propp Oct 3 '15 at 13:49

$\begingroup$ So I was thinking about this. I think the point is that the sequence $S_N$ is very slowly varying indeed. Nothing much can happen between times $e^{(1+\epsilon)^k}$ and $e^{(1+\epsilon)^{k+1}}$. So if the sequence goes to 0 with probability 1 along that sequence of times for each $\epsilon$, you get convergence for the full sequence. Now work with a countable sequence of $\epsilon$ going to 0. An argument of this type (for standard weights) appears in notes of Wierdl and Rosenblatt in the Cambridge Volume "Convergence in Ergodic Theory" $\endgroup$ – Anthony Quas Oct 3 '15 at 14:50

$\begingroup$ Yes, I believe this would work. So that settles the case $t=0$. But it's less clear to me how to handle other values of $t$ (from the original problem). $\endgroup$ – James Propp Oct 3 '15 at 19:17

$\begingroup$ I think roughly the same argument works for other values of $t$. Define $Y_n$ to be 1 if $a_1+\ldots+a_n>t\sqrt n$ and 0 otherwise. When you do the Brownian motion approximation argument with $m<n$, you end up with Cov$(Y_m,Y_n)$ $\approx \mathbb P(N_1>t;N_2>t\sqrt{n/(n−m)}−N_1\sqrt{m/(n−m)}−\mathbb P(N_1>t)^2$ where $N_1$ and $N_2$ are independent standard normals. The weighting means you don't have to worry about terms with $m$ and $n$ within a bounded factor of each other. Outside this range, this is close to 0 as before so that you get the desired convergence. $\endgroup$ – Anthony Quas Oct 4 '15 at 0:01
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 shiftinvariant 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 nonrandom by e.g. the HewittSavage 01 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)

$\begingroup$ Don't you need measurability of $\theta$ for $\theta(A^+)$ and $\theta(A^)$ to be constant? $\endgroup$ – Anthony Quas Oct 5 '15 at 15:01

$\begingroup$ At least in the case that $\theta$ is a subsequential limit of the functions $\frac{1}{n}\sum_{x\in[0,n]}1(x\in A)$, it is a limit of measurable functions and hence measurable (the same subsequence is used for every $A$). I think that every shiftinvariant mean on $\mathbb{N}$ will arise as a similar sort of limit, giving measurability, but I'm not an expert on this. $\endgroup$ – tmh Oct 5 '15 at 23:23

3$\begingroup$ I don't think this is the case. I believe the shiftinvariant means are produced using the HahnBanach theorem: you start off with defining a linear functional on the set of things that do have a limit; and then use HahnBanach (plus lots of axiom of choice) to extend it to the rest. To see the means are not subsequential, once you know the subsequence, it's pretty easy to find a set so that you don't get convergence along the subsequence. $\endgroup$ – Anthony Quas Oct 6 '15 at 0:28

$\begingroup$ Right, sorry, I was misremembering the construction. $\endgroup$ – tmh Oct 6 '15 at 5:12