6
$\begingroup$

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)$.

$\endgroup$
6
  • $\begingroup$ What is the motivation for studying this particular set of operations? $\endgroup$ May 18, 2023 at 5:24
  • $\begingroup$ It is a dynamical process that came up in some discussion. It seems like a very natural question though (one that could appear as an exercise in a real analysis class or similar!) $\endgroup$
    – pi66
    May 18, 2023 at 5:42
  • $\begingroup$ @pi66 This question is very interesting. There are many variations and generalizations. $\endgroup$
    – Apass.Jack
    May 22, 2023 at 16:27
  • $\begingroup$ @pi66 $n=2$ is trivial. I have not figured out a proof for the case of $n=3$, although it does not look very intimidating. Are you able to prove the case of $n=3$? If not, I would recommend you to restrict this question/bounty to the case of $n=3$. $\endgroup$
    – Apass.Jack
    May 22, 2023 at 16:28
  • $\begingroup$ These are reminiscent of Markov probabilities, so I'd start there to try to prove it using similar techniques. Note in particular that if $b = (b_1, \ldots, b_n)$ then $\| b \| = \sum b_i = 1$ at all time steps, so $b$ should be an associated probability vector to the Markov-like process acting on the state space of the $a_i$. $\endgroup$ May 22, 2023 at 16:53

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The last observation could be made more precise. It seems that $a_i-a_j$ for every $k$ ticks will be fixed eventually for any fixed $i$ and $j$. In other words, $a(t)-a(t-1)$ is eventually periodic with period $k$. This implies the convergence. $\endgroup$
    – Apass.Jack
    May 25, 2023 at 15:59
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Can you show a proof for the case of $n=3$? $\endgroup$
    – Apass.Jack
    May 24, 2023 at 17:32
  • $\begingroup$ Added more detail for $n=3$. Will make more rigorous later. $\endgroup$
    – Eric
    May 24, 2023 at 17:42
  • $\begingroup$ "Making it rigorous seems more annoying than hard". I would agree to that readily. I would also agree readily if someone says the devil is in the details like four-color theorem. $\endgroup$
    – Apass.Jack
    May 24, 2023 at 17:46

You must log in to answer this question.

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