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 QuasCommented Oct 2, 2015 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 QuasCommented Oct 2, 2015 at 19:42
2 Answers
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".
-
$\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$ Commented Oct 3, 2015 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$ Commented Oct 3, 2015 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$ Commented Oct 3, 2015 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$ Commented Oct 4, 2015 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.
(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$ Commented Oct 5, 2015 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 shift-invariant mean on $\mathbb{N}$ will arise as a similar sort of limit, giving measurability, but I'm not an expert on this. $\endgroup$– tmhCommented Oct 5, 2015 at 23:23
-
3$\begingroup$ I don't think this is the case. I believe the shift-invariant means are produced using the Hahn-Banach theorem: you start off with defining a linear functional on the set of things that do have a limit; and then use Hahn-Banach (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$ Commented Oct 6, 2015 at 0:28
-
$\begingroup$ Right, sorry, I was misremembering the construction. $\endgroup$– tmhCommented Oct 6, 2015 at 5:12