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

• Is a bit $\pm 1$? Otherwise it's hard for the sum to be $\le 0$. – Anthony Quas Oct 2 '15 at 19:31
• 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. – 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/(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".

• 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. – James Propp Oct 3 '15 at 13:49
• 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" – Anthony Quas Oct 3 '15 at 14:50
• 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). – James Propp Oct 3 '15 at 19:17
• 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. – 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 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.

• Don't you need measurability of $\theta$ for $\theta(A^+)$ and $\theta(A^-)$ to be constant? – Anthony Quas Oct 5 '15 at 15:01
• 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 shift-invariant mean on $\mathbb{N}$ will arise as a similar sort of limit, giving measurability, but I'm not an expert on this. – tmh Oct 5 '15 at 23:23