63
$\begingroup$

Let $Q=\mathbb Q \cap(0,1)= \{r_1,r_2,\ldots\}$ be the rational numbers in $(0,1)$ listed out so we can count them. Define $x_n=\frac{1}{n}\sum_{k=1}^nr_n$ to be the average of the first $n$ rational numbers from the list.

Questions:

  1. What is required for $x_n$ to converge? Certainly $0< x_n < 1$ for all $n$.

  2. Does $x_n$ converge to a rational or irrational?

  3. How does the behavior of the sequence depend on the choice of list? I.e. what if we rearrange the list $\mathbb Q \cap(0,1)=\{r_{p(1)},r_{p(2)},\ldots\}$ with some one-to-one permutation $p: \mathbb N \to \mathbb N$? How does the behavior of $x_n$ depend on $p$?


My thoughts:

Intuitively, I feel that we might be able to choose a $p$ so that $x_n\rightarrow y$ for any $y\in[0,1]$. However, it also makes intuitive sense that, if each rational appears only once in the list, that the limit is required to be $\frac{1}{2}.$ Of course, intuition can be very misleading with infinities!

If we are allowed to repeat rational numbers with arbitrary frequency (but still capturing every rational eventually), then we might be able to choose a listing so that $x_n\rightarrow y$ for any $y\in(0,\infty)$.

This last point might be proved by the fact that every positive real number has a sequence of positive rationals converging to it, and every rational in that list can be expressed as a sum of positive rationals less than one. However, the averaging may complicate that idea, and I'll have to think about it more.


Example I:

No repetition: $$Q=\bigcup_{n=1}^\infty \bigcup_{k=1}^n \left\{\frac{k}{n+1}\right\} =\left\{\frac{1}{2},\frac{1}{3},\frac{2}{3},\frac{1}{4},\frac{3}{4},\frac{1}{5},\ldots\right\}$$ in which case $x_n\rightarrow\frac{1}{2},$ a very nice and simple example. Even if we keep the non-reduced fractions and allow repetition, i.e. with $Q=\{\frac{1}{2},\frac{1}{3},\frac{2}{3},\frac{1}{4},\boxed{\frac{2}{4},}\frac{3}{4},\frac{1}{5},\ldots\},$ then $x_n\rightarrow\frac{1}{2}.$ The latter case is easy to prove since we have the subsequence $x_{n_k}=\frac{1}{2}$ for $n_k=\frac{k(k+1)}{2},$ and the deviations from $1/2$ decrease. The non-repetition case, I haven't proved, but simulated numerically, so there may be an error, but I figure there is an easy calculation to show whether it's correct.


Example II:

Consider the list generated from the Stern-Brocot tree: $$Q=\left\{\frac{1}{2},\frac{1}{3},\frac{2}{3},\frac{1}{4},\frac{2}{5},\frac{3}{5},\frac{3}{4},\ldots\right\}.$$

I'm sure this list could be studied analytically, but for now, I've just done a numerical simulation. The sequence of averages $x_n$ hits $\frac{1}{2}$ infinitely often, but may be oscillatory and hence not converge. If it converges, it does so much slower than the previous examples. It appears that $x_{2^k-1}=0.5$ for all $k$ and that between those values it comes very close to $0.44,$ e.g. $x_{95743}\approx 0.4399.$ However, my computer code is probably not very efficient, and becomes very slow past this.

$\endgroup$
  • 8
    $\begingroup$ It seems likely to me that one could prove that most sequences will converge to $\frac 12$, but I don't see the measure space to make that precise. $\endgroup$ – Ross Millikan May 28 '16 at 15:13
  • $\begingroup$ @RossMillikan, I tend to agree. If all lists of rationals were equally likely, then all limits would be equally likely hence averaging to the middle, $\frac12$. However I wonder how many divergent "sequences of partial averages" there are? Maybe start with an arbitrary list of rationals, truncate it and create all sequences from it uniformly, then let the truncation point of the "generating list" go to $\infty$. My minimal skills with stochastic convergence don't provide enough intuition though. $\endgroup$ – jdods May 28 '16 at 19:39
  • $\begingroup$ I am sure there are continuum many divergent sequences. Take your favorite divergent one, mark off pairs of elements, and swap the pairs according to the binary expansion of any real. All those sequences will also be divergent. That is why I don't see what the measure space needs to be to measure "most sequences converge to 1/2". $\endgroup$ – Ross Millikan May 28 '16 at 20:45
  • $\begingroup$ But are there continuum-many converging sequences and continuum-many converging to $\frac12$. I suspect affirmative all around, but that's way out of my comfort zone! Or is it greater than continuum? $\mathfrak c=n^\mathbb{N}$, is $\mathbb{N}^\mathbb{N}>\mathfrak c$? $\endgroup$ – jdods May 28 '16 at 21:13
  • 2
    $\begingroup$ Yes, so cardinality is not sufficient to show that almost none diverge (or converge somewhere else than 1/2). $\endgroup$ – Ross Millikan May 28 '16 at 21:14
53
$\begingroup$

Depending on how you order the rationals to begin with, the sequence $x_n$ could tend to anything in $[0,1]$ or could diverge.

Say $y\in[0,1]$. Start with an enumeration $r_1,\dots$ of the rationals in $(0,1)$. When I say "choose a rational such that [whatever]" I mean you should choose the first rational currently on that list that satisfies [whatever], and then cross it off the list.

Start by choosing $10$ rationals in $I_1=(y-1/10,y+1/10)$. Then choose one rational in $[0,1]\setminus I_1$. Then choose $100$ rationals in $I_2=(y-1/100,y+1/100)$, and then choose one rational in $[0,1]\setminus I_2$. Etc.

First, note we have in fact defined a reordering of the original list. No rational appears in the new ordering more than once, because it is crossed off the original list the first time it is chosen. And every rational appears on the new list. In fact you can show by induction on $n$ that $r_n$ must be chosen at some stage: By induction you can assume that every $r_j$ for $j<n$ is chosen at some stage. So at some stage $r_n$ is the first remaining entry on the original list; hence it will be chosen soon, since either it's in $I_k$ or not.

And for large $n$ the vast majority of the rationals in the first $n$ elements of the new ordering are very close to $y$, hence $x_n\to y$.

(Similarly, to get $x_n$ to diverge: Start with a large number of rationals near $0$. Follow with a huge number of rationals near $1$, then a stupendous number of rationals near $0$...)

$\endgroup$
  • 9
    $\begingroup$ @Ant You're talking about Riemann's theorem that any rearrangement of an absolutely convergent series has the same sum? That theorem talks about a convergent series. There is no series anywhere in sight here. In particular there is no series that has $x_n$ for its $n$-th partial sum. "Sequence" and "series" are different things. $x_n$ is the $n$th partial sum of a certain series, _divided by $n$_. That sum of the series itself is infinite, and the sum of any rearrangement of that series is infinite, and that has no relevance. $\endgroup$ – David C. Ullrich May 28 '16 at 22:39
  • 2
    $\begingroup$ I'm just curious how the diverging sequence of adjectives "large, huge, stupendous, ..." continues :) $\endgroup$ – Hagen von Eitzen May 29 '16 at 13:28
  • 1
    $\begingroup$ @jdods Really. Making edits that clarify what the author meant is one thing - making edits that change what the author meant is a totally other thing! DON'T DO THAT! Here it should have been very clear that the problems you thought you were correcting at least could have been misunderstandings on your part, since the post has been up for a day, got 30 upvotes without a single comment or question about the validity of the details. I mean really - you change $y\in[0,1]$ to $y\in(0,1)$ it looks like you don't realize that a sequence of positive numbers can converge to $0$. ASK FIRST. $\endgroup$ – David C. Ullrich May 29 '16 at 14:00
  • 1
    $\begingroup$ @jdods SLOPPY??? It's your version that's sloppy, saying "for a suitable $\epsilon>0$" without explaining what would make it suitable! Using $y\pm1/10$, $y\pm1/100$, etc, is perfectly clear, precise, correct, and simpler - instead of saying what $\epsilon$ has to be why not just talk about specific numbers? Your version on the other hand was not only sloppy, not specifying what $\epsilon$ has to satisfy, it was also wrong, using $y\pm\epsilon$ at the first step and then $y\pm1/\epsilon^2$ at the second step. $\endgroup$ – David C. Ullrich May 29 '16 at 14:19
  • 3
    $\begingroup$ @jdods Well fine then. Sorry to fly off that handle, but I was already irritated at the edit itself. Sloppy is bad. Informal is not the same as sloppy - informal can be good. Consider the punchlline " And for large $n$ the vast majority of the rationals in the first $n$ elements of the new ordering are very close to $y$, hence $x_n\to y$.". Say I'd written that out in epsilons and capital N's. Beginners would pore through the inequalities and possibly end up with no real insight why it was really true. $\endgroup$ – David C. Ullrich May 29 '16 at 16:10
14
$\begingroup$

It depends on the order that you put them.
For example, let $A=(0,1/10]$, $B=(1/10,2/10]$ and $C=(2/10,1)$.
Pick one number from $A$, one from $B$, one from $C$ and repeat. The average will be less than $(\frac1{10}+\frac2{10}+1)/3=13/30$.

$\endgroup$
  • $\begingroup$ Can you explain how this makes sense considering the Riemann rearrangement theorem? All the numbers are positive, hence if the series converges, it converges absolutely (right?). So we should be able to rearrange without changing the sum. I know that there must be something wrong in my argument, but I just don't see it right now. $\endgroup$ – Eff May 28 '16 at 15:14
  • $\begingroup$ Hmm... I guess the addends also change as we increase $n$, since we can look at it like $S_n = \sum_k a_{k,n}$ with $a_{k,n} = r_k/n$. I guess that explains it (?). $\endgroup$ – Eff May 28 '16 at 15:18
  • 2
    $\begingroup$ @Eff I don't see how this has anything to do with that theorem. That theorem is about rearranging conditionally convergent series. What series do you have in mind? $\endgroup$ – David C. Ullrich May 28 '16 at 15:24
  • $\begingroup$ @Michael, Thanks for the solution. Presumably, if we chose uniformly from each set, the partial average would converge exactly to the average of the middles of the sets. Probably true for any finite partition of $(0,1)$. Very cool. Thanks! $\endgroup$ – jdods May 28 '16 at 19:23
  • $\begingroup$ Also, note that my examples converging to $\frac12$ could be explained by the uniform nature of the location of the rationals in the list. $\endgroup$ – jdods May 28 '16 at 21:20

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.