5
$\begingroup$

Consider a sequence $(x_n)_{n\in\mathbb{N}}$ of 0s and 1s. The asymptotic frequency of 1s in $x$ is usually defined as:

$$f=\lim_{n\to+\infty} \frac{1}{n}{\sum_{i=0}^{n-1} x_i}$$

when this limit exists. But sometimes the limit does not exist yet it sounds "reasonable" to say that the asymptotic frequency still exists. Is there a general way to define asymptotic frequency so that it applies to a much broader class of sequences?.

For simplicity, we can focus only on defining $f=0$: how to define there are "infinitely more" 0s than 1s in the sequence. Maybe this could involve probability theory, maybe not. Of course the definition can't be invariant under any permutation since there is nothing to say in terms of cardinal except there are as many 1s as 0s: countably many.

The tricky example I have in mind is successive groups of length $2^k$. In each group the values are equal: all 0s or all 1s. There are infinitely many groups with value 1 but these become more and more sparse for example with frequency $1/k$. It looks like it:

1-00-1111-0000000- ....... groups of length $2^k$: most are 0, with sometimes a group of 1s.

If you compress visually each group into a single digit, it looks like:

101000010000000000000100000000000000000000000000000000000000000000001....

The limit does not exist as the average is greater than 1/2 infinitely many times. Yet, this example can be thought as the realization of a random sequence $(X_n)_{n\in\mathbb{N}}$ that tends to 0 in probability. Hence it could make sense saying the asymptotic frequency is 0.

$\endgroup$
  • 2
    $\begingroup$ I don't see any example where " the limit does not exist yet it sounds "reasonable" to say that the asymptotic frequency still exists". In your diadic-blocks example, the relative frequency of 1's never goes below $1/3$, and it oscillates asymptotically, with ever doubling "periods", between $1/3$ and $2/3$. So, I cannot see why "it could make sense saying the asymptotic frequency is 0" here. $\endgroup$ – Iosif Pinelis Mar 29 '18 at 15:55
  • $\begingroup$ Right; there's such symmetry between 1s and 0s in this example, that, if anything, I'd only want to assign a generalized frequency of 50-50 between the two (as in a kind of Cesàro-style generalized limit). $\endgroup$ – Sridhar Ramesh Mar 29 '18 at 18:02
  • $\begingroup$ Actually, my example is: for block #$k$ decide it is 1s with probability $1/k$, 0s otherwise (like coin tossing). There is no symmetry. The frequency is most often very small, except after seeing a group of 1s. $\endgroup$ – Benoit Sanchez Mar 29 '18 at 18:13
  • $\begingroup$ @BenoitSanchez : That was not how I interpreted your original post. You are saying "The frequency is most often very small"; in what sense most often? Every once in a while, your frequency stays at a level $\ge 1/4$ during at least $1/4$ of the entire prehistory. Whatever the frequency "loses" during the very-very long first $1/2$ of such a journey, it recovers -- gradually and steadily -- during the last very-very long $1/2$ of it. (You can't see this if you compress the blocks into single digits.) $\endgroup$ – Iosif Pinelis Mar 29 '18 at 20:06
  • $\begingroup$ As for the convergence of $f_n$ in probability (which concerns only the one-dimensional distributions of the random variable $f_n$) in your example, it does not seem of sufficient relevance to the behavior of the sequence $(f_n)$, which is an infinite-dimensional random vector. This should be especially true in your example, where the convergence of (say) $Ef_n$ to $0$ is very slow, of a $\log\log n$ rate. $\endgroup$ – Iosif Pinelis Mar 29 '18 at 20:20
4
$\begingroup$

You want to assign limits to possibly divergent sequences, generalized limits that will catch some sort of asymptotic frequency. The only methods that I am aware of are so called summability methods. The particular method that you use is called the Cesaro summability method. There is a general result of Toeplitz that characterizes all regular matrix summability methods, see Theorem 9.9 in [1]. Moreover, there is an abstract result due to Mazur which allows you to assign a generalized limit to any bounded sequence. Such a generalized limit is called a Banach limit, see Section 11.1 in [1]. These methods are also described in many other textbooks in Functional Analysis.

[1] P. Hajlasz, Functional Analysis.

$\endgroup$
  • $\begingroup$ Banach limits are not unique. A sequence is said to be almost convergent if all Banach limits agree about it. Being almost convergent is stronger than being Cesaro convergent (en.wikipedia.org/wiki/Almost_convergent_sequence). I'm still looking for a something where the frequency could be (sometimes) uniquely defined. I'm not sure it's possible... Your answer is enriching anyway. Thanks. $\endgroup$ – Benoit Sanchez Mar 28 '18 at 15:31
2
$\begingroup$

$\newcommand{\ep}{\epsilon} \newcommand{\ga}{\gamma} \newcommand{\la}{\lambda} \newcommand{\Si}{\Sigma} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\operatorname{\mathsf E}} \newcommand{\PP}{\operatorname{\mathsf P}}$

I don't think such a "reasonable" much broader definition is possible. The reason is that the relative frequency $f_n:=s_n/n$ (where $s_n:=\sum_1^n x_i$) varies very slowly in $n$ when $n$ is large. So, it will take $f_n$ a very long time to significantly depart from whatever value it has attained.

To express this thought rigorously, let us now indeed "focus only on defining $f=0$", as you suggested; for any other value of $f$, we can reason quite similarly. Take some $\ep\in(0,1/2)$ and suppose that $f_M\le\ep$ and $f_N\ge2\ep$ for some natural $M$ and $N>M$; this situation would "reasonably" occur if a "generalized limit frequency" is $0$, but $f_n\not\to0$. Then $s_M\le M\ep$, $s_N\ge2N\ep$, and hence \begin{equation} N-M\ge s_N-s_M\ge(2N-M)\ep, \end{equation} which implies $N\ge\frac{1-\ep}{1-2\ep}\,M$, and so, \begin{equation} s_N-s_M\ge\frac\ep{1-2\ep}\,M. \end{equation} Note that $s_N-s_M$ is the number of $1$'s in the sequence $(x_n)$ for natural $n\in(M,N]$. Thus, this number of $1$'s -- after the time $M$ (at which $f_M$ was $\ep$-close to $0$) -- needed to get a relative frequency at least $2\ep$ is at least proportional to the time $M$. So, for the $f_n$'s, it is impossible get a picture like the one below, where the intervals of significantly non-zero values of $f_n$ become (relatively) negligibly short in time. Therefore, I don't think one can reasonably say that such a sequence has a negligible amount of $1$'s.

enter image description here

For such a picture to be possible, $f_n$ would need to grow arbitrarily fast over some intervals -- but it cannot do that, because $x_n\in\{0,1\}$ for all $n$ and hence $$|f_{n+1}-f_n|=\Big|\frac{nf_n+x_{n+1}}{n+1}-f_n\Big|=\Big|\frac{x_{n+1}-f_n}{n+1}\Big| \le\frac1{n+1}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.