Almost certain non-existence of limit

Solution 1:

I think your distribution should work, but exponential growth is probably too slow to prove it easily.

The idea is: make $N$ grow so fast that we will infinitely many times get segments longer than previous sequence. Also, by Kolmogorov's zero-one law, probability of limit existence is either 0 or 1, so it's enough to show that probability of it non-existence is greater than 0.

Consider Bernoulli schema with 3 outcomes: one with probability $p$, the second with probability $q\cdot p$ and the third with probability $1 - p - p \cdot q$. There is some monotone function $q(\varepsilon) > 0$ such that for any $p > 0$, probability of outcome with probability $p$ coming before outcome with probability $p \cdot q(\varepsilon)$ is at least $1 - \varepsilon$.

Let's start with some rapidly decreasing distribution $P$. First, define unnormalized version of it: $P'(1) = 1$, $P'(n + 1) = q(2^{-10-n}) P'(n)$. Let $P$ be normalized version of $P'$. Then probability of $1$ coming before $2$ is at least $1 - 2^{-11}$, probability of $2$ coming before $3$ is at least $1 - 2^{-12}$ and so on.

Combining it all, we have that probability that every number first comes before any larger comes is at least $1 - 2^{-10}$.

Now, let's choose some constants $C_k$ s.t. probability of number $C_k$ coming in first $k$ trials is at least $1 - 2^{-10 - k}$. Combining with previous, we get that with probability at least $1 - 2^{-9}$, every number first shows up in the first $C_k$ trials and don't have any larger numbers before it; let's call such outcome good.

Now, it's simple to define $N$: let $N(1) = 1$, $N(k)$ have the same parity as $k$ and $N(k) > 2 \cdot C_k \cdot N(k - 1)$.

Let's see what happens if our outcome is good. First, we get $1$, and frequency of even numbers is $0$. Eventually, we get $2$, and frequency of even numbers immediately after becomes at least $\frac{2}{3}$. Eventually, we get $3$, and the frequency becomes at most $\frac{1}{3}$. And so on - after encountering next even number frequency becomes at least $\frac{2}{3}$, after encountering odd, it becomes at most $\frac{1}{3}$. So, if outcome is good, limit of frequency doesn't exist.