Given some real number :$a_1,a_2,...,a_n$Every time I chose two of them $a_i$ and $a_j$ and set both of them to $\frac{a_i+a_j}{2}$.
Now I have operated $T$ times,when $T$ is infinite,I guess that every number is equal to $\frac{\Sigma_{1}^{n}a_i}{n}$ If I'am right,can anyone show me how to prove it?
To be clear,$i$ and $j$ are two random numbers in $[1,n]$ OR $a_i$ and $a_j$ are the smallest and the biggest of all (there are now two questions...)
Further more,I think I can chose 3,4,5 or more each time,and if I chose $n$ of the numbers,all of $a_i$ are set to the same at once!
I want to know whether this is a simple problem because it seems to be but I can't prove it.
How to prove that all the $a_i$ will be the same after inf operations?
-
0@J.M., [stochastic-processes](http://math.stackexchange.com/questions/tagged/stochastic-processes), perhaps? – 2011-10-12
1 Answers
Yes, this is easy. First of all, it doesn't matter if you are choosing $i,j$ randomly or if you are picking them to be the biggest and the smallest, just so long as you are not deliberately picking the two that are closest together.
What happens is that you have some non-zero probability of picking the biggest and smallest at any given step, so you will wind up picking those infinitely many times with probability 1.
Now look at $\sum_{1\leq i < j \leq n} |a_i - a_j|$. This sum decreases by a factor which is at most $(1 - 4/n(n-1))$ each time we pick the largest and smallest numbers. So we wind up multiplying by this number (which is smaller than 1) infinitely many times -- so this sum must go to zero in the limit and all the $a_i$ are the same in the limit. Since the sum of the $a_i$ is preserved by the algorithm, each $a_i$ equals the average value in the limit.
-
0Sorry to replay so late.But I find I still can't see why *"This sum decreases by a factor which is at most XXX"*,how to estimate this factor? – 2012-03-09