Does every equalizing sequence converge?

Question

Let $(a_1,a_2, \dots, a_n) = (0, 0, \dots, 0)$. There are sets $B_1, \dots, B_k\subseteq\{1,2,\dots,n\}$, each of size $2$.

At time step $t$, consider the index $i\in\{1,\dots,k\}$ such that $i\equiv t\pmod k$, and let the two numbers in $B_i$ be $x$ and $y$, where $a_x \ge a_y$. If $a_x \ge a_y + 1$, we increase $a_y$ by $1$. Else, we increase $a_y$ until it is equal to $a_x$, then increase both $a_y$ and $a_x$ until the total amount we increased is $1$. Let $(b_1, \dots, b_n) = (a_1/t, \dots, a_n/t)$.

Is it true that, as $t\rightarrow\infty$, the sequence $(b_1,\dots,b_n)$ converges?

---

Example 1: $n = 3$, $k=2$, $B_1 = \{1,2\}$, $B_2 = \{2,3\}$.

• At $t = 1$, we update $(a_1, a_2, a_3)$ to $(0.5,0.5,0)$.

• At $t = 2$, it becomes $(0.5, 0.75, 0.75)$, so $(b_1,b_2,b_3) = (0.25,0.375,0.375)$.

• At $t = 3$, $(a_1,a_2,a_3) = (1.125,1.125,0.75)$ and $(b_1,b_2,b_3) = (0.375,0.375,0.25)$.

Eventually, $(b_1,b_2,b_3)$ converges to $(1/3,1/3,1/3)$.

---

Example 2: $n = 3$, $k=4$, $B_1 =B_2 = B_3 = \{1,2\}$, $B_4 = \{2,3\}$.

• At $t = 1$, $(a_1, a_2, a_3)=(\frac12,\frac12,0)$.

• At $t = 2$, $(a_1, a_2, a_3)=(1, 1, 0)$ and $(b_1,b_2,b_3) = (\frac12,\frac12,0)$.

• At $t = 3$, $(a_1,a_2,a_3) = (\frac32,\frac32,0)$ and $(b_1,b_2,b_3) = (\frac12,\frac12,0)$.

• At $t = 4$, $(a_1,a_2,a_3) = (\frac32,\frac32,1)$ and $(b_1,b_2,b_3) = (\frac38,\frac38,\frac14)$.

Eventually, $(b_1,b_2,b_3)$ converges to $(\frac38,\frac38,\frac14)$.

Answer 1

This is an idea for a proof. As is it isn’t rigorous, but I think it has the right direction.

Sort the numbers. Group values based on the gaps between them. Consider $\sum i a_i$ of the sorted values. Each group goes up at a constant rate and movement within a group is small, so asymptotically, the rate of increase is this is increasing.

Each group’s asymptotic increase per cycle would be the number of edges within the group and to higher groups divided by its size . If a higher group is below a smaller one, they’ll eventually intersect and either stay as one group or split again. That $\sum i a_i$ has to increase after each group/split, so eventually it’ll stabilize.

$n=3$ isn’t that much simpler than the general case.

Assume it doesn’t converge. Then, eventually the numbers will split up (note that the sum increases by $k$ every cycle). If one number gets split off (WLOG) downwards, then it must have a lower velocity per cycle than the average of the the group it split from, so they’ll keep separating. You can show the average velocity of a group only depends on the elements of the group and the elements of the other groups, not the relative ordering within groups. I suppose it’s possible a splits from b and c, and then later b splits from c, and hits a, and then a splits from them and hits c, etc., but the average velocity of the first element plus twice second element plus three times h the it’d element (use groups velocity and center index if they’re together) has too increase over time and since there’s a finite number of groupings, eventually one of them must be stable.

Answer 2

Some partial results

Let $a(t)=(a_1(t),a_2(t),...,a_n(t))$ at timestep $t$ and

$a(t_2)-a(t_1)=(a_1(t_2)-a_1(t_1),a_2(t_2)-a_2(t_1),...,a_n(t_2)-a_n(t_1))$ and

$||a(t)||=|a_1(t)|+|a_2(t)|+...+|a_n(t)|$

Same for $b(t)$

No matter what, $||a(t)||$ increases by $1$ every timestep, or specifically, $||a(t)-a(t-1)||=1$, and $||b(t)||=1$ always. Then, from step $t-1$ to $t$, all elements in $b(t-1)$ are multiplied by $\frac{t-1}{t}$, and a total of $\frac{1}{t}$ is added in addition, so

$||b(t-1)-b(t)||\le1-\frac{t-1}{t}+\frac{1}{t}=\frac{2}{t}$

This eliminates the possibility of nontrivial cyclic behavior, as that would require a fixed nonzero $||b(k\times t-m)-b(k\times t)||$ for some $0<m<k$, but this goes to $0$.

Note that $b_m(t)$ is the average of the previous differences $a_m(t)-a_m(t-1)$ as

$b_m(t)=\frac{1}{t}\sum_{0<i\le t}{(a_m(i)-a_m(i-1))}$

So then if $b_m(t)$ does not converge, then neither can the average of all $a_m(t)-a_m(t-1)$. One way of thinking about this is that there exists some finite interval $(x_1,x_2)$ for which the average will be below $x_1$ for infinitely many $t$ and above $x_2$ for infinitely many $t$. However, if the average is on one side at time $t_1$, in order to move the overall average to the opposite side of the interval, it is necessary to have the partial average of $a_m(t)-a_m(t-1)$ for $t_1\le t\le t_2$ to be on the other side at least for long enough that $t_2-t_1$ is proportional to $t_1$ as otherwise the partial average could not have a significant weight in the overall average. This means that the amount of time between switching sides increases exponentially, which strongly suggests that divergence is impossible.

Additionally, is it seems that, eventually, every k timesteps, each element in $a(t)$ will always be exactly one of $<,>,=$ for each other element in $a(t)$: for example 1 above, $a_1(k\times t)<a_2(k\times t)$ and also $a_2(k\times t+1)>a_3(k\times t+1)$ for all $t$. This alone does not imply, nor is it implied by, the convergence of $b(t)$, but its proof may be easier and could be insightful.