2
$\begingroup$

Be a set of numbers $v=(a_1, a_2, \ldots, a_n)$

I want to form the following average vector $\mu = (\frac{\sum a_i}{n}, \frac{\sum a_i}{n}, \ldots, \frac{\sum a_i}{n})$.

If I do it iteratively step by step, in each step we pick three components, $a_i,a_j$ and $a_k$ that are not all equal, and we replace them by their mean, $s_1=\frac{a_i+a_j+a_k}{3}$, to obtain $\mu_1 = (a_1, \ldots, a_{i-1}, s_1, a_{i+1}, \ldots, a_{j-1}, s_1, a_{j+1}, \ldots, a_{k-1}, s_1, a_{k+1}, \ldots, a_n)$.

In the next step, we select three other compounents (always not all equal) and compute $\mu_2$

By iterating, Can we have $\mu_n \rightarrow \mu$? if yes, how to pick up the three elements in each step?

Does this "partial averaging" have a particular name/theorem in number theory?

Improve this question
$\endgroup$
3
  • $\begingroup$ But why don't you just form the average vector $\mu$ by, well, calculating it? $\endgroup$
    – Matthias Ludewig
    Commented Dec 26, 2014 at 16:03
  • $\begingroup$ I want to compute $\mu$ using a theoritical algorithm that operates only on three compenents and converges to $\mu$ $\endgroup$
    – John
    Commented Dec 26, 2014 at 16:07
  • $\begingroup$ What is the connection with number theory? $\endgroup$
    – Douglas Zare
    Commented Dec 27, 2014 at 4:42

5 Answers 5

Reset to default
1
$\begingroup$

This operation decreases the variance of the set of numbers. If you include the minimum and the maximum, the operation decreases the variance by a factor bounded by some $c(k) \lt 1$ (we can take $c(k) = 1-1/(2k)$ though that is not sharp) so the vector converges to a constant if you repeatedly include the minimum and the maximum.

You can check that many predetermined sequences of indices, such as $(1,2,3),(2,3,4),...$ will cause the vector to converge to a constant vector. The operation is linear, so it suffices to check how it acts on standard basis vectors.

Improve this answer
$\endgroup$
3
$\begingroup$

If you just pick a random triple of coordinates at every step and average, the fact that your vector will converge to $\mu$ follows from the machine of random matrix products, Bougerol's book is an OK reference:

Products of Random Matrices with Applications to Schrodinger Operators by P. Bougerol

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your answer. Can you point out a chapiter of that book to see what it is about? $\endgroup$
    – John
    Commented Dec 26, 2014 at 16:15
  • $\begingroup$ Chapter V should work. (you have to be a little careful, since your linear transformations are not invertible, but semigroups are fine). Note that picking the triples randomly will both slow you down (when you pick three equal coordinates) and prevent you from jamming, as in @Henry's example). $\endgroup$
    – Igor Rivin
    Commented Dec 26, 2014 at 17:44
2
$\begingroup$

This is a Markov chain in state-space $\mathbb R^n$. There is machinery to determine whether (and to what) it converges.

This part below wrong, the state space is continuous, not finite...

You determine that a certain $n \times n$ matrix is "irreducible" and then you get convergence to the unique (up to scalar multiple) positive eigenvector with eigenvalue $1$. Goes back to Perron & Frobenius, I guess.

Maybe this 3-term average has a name in probability theory (but I don't know one) ... However I really doubt is has a name in number theory.

Improve this answer
$\endgroup$
0
$\begingroup$

Your specification for an algorithm will work if $n=6$ unless it jams.

As an example of jamming, suppose you started with $(2,3,7,5,9,6)$ and as a first step took the first three positions to give $(4,4,4,5,9,6)$ and as a second step took the third, fourth and fifth positions to give $(4,4,6,6,6,6)$; then you cannot find three nonequal values for the third step. Jamming is inevitable for $n=4$ or $n=5$ unless you reach $\mu$ almost immediately.

For $n=7$, even if you avoid jamming, you could just be applying the algorithm to the first six positions, converging towards the average of those values but ignoring the value in the seventh position. Similarly with $n=12$ you could be taking the three positions each time from the first six or from the last six, and so need not coverge overall. This issue is related to Gerald Edgar´s mention of "irreducible".

So I suspect you need to specify your algorithm in more detail to avoid these issues, and in particular how you choose the three positions to average at each step.

Improve this answer
$\endgroup$
2
  • $\begingroup$ By nonequal I mean not all equal, in your example $(4,4,6)$ is a valid choice. I edited the question to make it clear $\endgroup$
    – John
    Commented Dec 26, 2014 at 17:35
  • $\begingroup$ @John: then ignore the jamming point, though my issue with $n=7$ would then extend to $n=5$ and $6$, and with $n=12$ to $n=8$ $\endgroup$
    – Henry
    Commented Dec 26, 2014 at 17:38
0
$\begingroup$

For the sake of conceptual simplicity let's not worry bout three terms of a consecutive $n$-vector being unequal.

Any procedure which results in an infinite sequence of index triples such that each triple appears infinitely many times will work, will produce a convergent $n$-vector.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .