I'm confused by how to analyse if a vector sequence is convergent or not. Here I first post the original problem as follows:
(Although this post is long, the problem meaning is easy to understand but how to prove it is very hard for me.)
(You may first jump over the original problem below and take a glance at my toy example.)
1. Problem:
Given a sequence length value $T\in\mathbb{N}$, a threshold $K\in\mathbb{N}$ and target summation $S\in\mathbb{N}$, an N-dimensional vector sequence $\{\mathbf{v}_t\}_{t=0}^{T}$ is produced by:
- The first item $\mathbf{v}_0\in\mathbb{R}^N$ is given by random generation. All its elements are non-negative and their summation is a non-negative integer denoted by $S\in\mathbb{N}$ that satisfies: $0\le S\le KN$;
- The subsequent items is produced by the following steps (procedure):
$~~~~~~~$(1) Initialize $\mathbf{v}_t:=\mathbf{v}_{t-1}$;
$~~~~~~~$(2) Calculate the average error between the element summation and $S$, i.e., let $\delta_t:=\text{average}(\mathbf{v}_t)-(S/N)$;
$~~~~~~~$(3) Force the summation of its all elements to be $S$, i.e., $\mathbf{v}_t:=\mathbf{v}_t-\delta_t$, here each element of $\mathbf{v}_t$ is reduced by $\delta_t$;
$~~~~~~~$(4) Force all elements to be integers in $[0,K]$, i.e., $\mathbf{v}_t:=\text{round}(\text{clip}_{0,K}(\mathbf{v}_t))$, where $\text{round}(\cdot)$ and $\text{clip}_{0,K}(\cdot)$ are element-wise operator, they calculate the new vector element values dimension-by-dimension.
The complete recurrence formula should be:
$$ \mathbf{v}_t:=\text{round}(\text{clip}_{0,K}(\mathbf{v}_{t-1}-[\text{average}(\mathbf{v}_{t-1})-(S/N)])). $$
Is $\{\mathbf{v}_t\}_{t=0}^{T}$ convergent or not when $T\rightarrow\infty$?
(Some above expressions may be informal but do not affect the meaning of this problem)
There is a toy example (created by myself) that may be helpful to understand the original problem:
2. My Example (may be a little weird but not impactive):
I have three children ($N=3$) and ten stamps ($S=10$). My children weigh $90$kg, $6$kg and $4$kg (the first one may be a teenager and the latter two may be little baby boys), respectively, so at the beginning, I want to give them $9$, $0.6$ and $0.4$ stamps, respectively.
But there are three constrains. Firstly, I think a child can not have more than four stamps ($K=4$). Secondly, the stamps can only be given one-by-one and one single stamp can not be cut, divided or shared (the stamps given to each child must be with a non-negative integer number). Thirdly, I only have ten stamps in total, and I want to try my best to distribute them all (the summation of all elements should be $S$ or close to $S$).
So I perform the above mentioned procedure as follows:
$~~~~~~~$(1) I initialize the stamp number vector: $(9, 0.6, 0.4)$;
- First round:
$~~~~~~~$(2) I calculate the average error $\delta$, and found that it is zero;
$~~~~~~~$(3) I clip each element into $[0,4]$ and round them, then I get: $(4, 1, 0)$;
- Second round:
$~~~~~~~$(4) I calculate the average error $\delta=(5-10)/3=-1.67$;
$~~~~~~~$(5) I correct the stamp number vector: $(4, 1, 0)-(-1.67)=(5.67,2.67,1.67)$;
$~~~~~~~$(6) I clip each element into $[0,4]$ and round them, then I get: $(4, 3, 2)$;
- Third round:
$~~~~~~~$(7) I calculate the average error $\delta=(9-10)/3=-0.33$;
$~~~~~~~$(8) I correct the stamp number vector: $(4, 3, 2)-(-0.33)=(4.33,3.33,2.33)$;
$~~~~~~~$(9) I clip each element into $[0,4]$ and round them, then I get: $(4, 3, 2)$.
I find that the stamp vector sequence is converged, so I stop, give the children four, three and two stamps, respectively, and keep one stamp.
3. My Efforts (may be not a correct idea):
I'm trying to prove that the average error sequence $\{\delta_t\}$ is absolutely convergent, i.e., I was trying to show that:
$$ 0\le |\delta_{t}|\le|\delta_{t-1}|, $$
but I was failed. And I think if $\{\delta_t\}$ is convergent, we can not say that $\{\mathbf{v}_t\}$ is convergent.
May be I need to prove that $\{\delta_t\}$ is convergent to zero? However, I empirically find that $\{|\delta_t|\}$ may only be convergent to a non-negative number in most cases (please see below).
Nevertheless, I simulated the absolute average error sequence $\{|\delta_t|\}$ by a toy Python program and observed that $\{|\delta_t|\}$ may be convergent:
import numpy as np
from matplotlib import pyplot as plt
N = 100 # vector dimension
T = 30 # max sequence length
S = 51200 # target sum of vector elements
K = 1024 # max value of each element
for _ in range(1000): # 1000 test instances
v = np.random.rand(N) # uniformly distributed random vector
v = (v / np.sum(v)) * S # normalize to make the element sum be S
abs_delta_list = [] # all absolute values of deltas
for t in range(T + 1): # t = 0, 1, 2, ..., T
delta = np.mean(v) - (S / N) # average error
v -= delta # force the sum to be S
v = np.round(np.clip(v, 0, K)) # force all elements to be intergers in [0, K]
abs_delta_list.append(np.abs(delta)) # collect abs(delta)
plt.plot(abs_delta_list, color='blue') # plot curve
plt.xlabel('t')
plt.ylabel('abs(delta)')
plt.savefig('abs_delta.png', dpi=600)
I obtained:
$(N=100, T=30, S=5120, K=1024)$
$(N=10, T=30, S=5120, K=1024)$
(Obviously, $\delta_1$ is zero).
4. Update:
I've solved this problem with the help of @antkam.
Outline of proof that the vector converges.
Part A: The key observation is this: let $v^i_t$ denote the $i$-th component of $v_t$, then $ \forall i \neq j, \forall t:$
bigger element remains bigger (or equal), i.e. $v^i_t \ge v^j_t \implies v^i_{t+1} \ge v^j_{t+1}$;
absolute difference between elements is monotonically decreasing, i.e. $|v^i_t - v^j_t| \ge |v^i_{t+1} - v^j_{t+1}|$.
These follow relatively easily from your rules.
Now because you are dealing with integers, these imply for any pair, $v^i - v^j$ must converge, because the absolute difference converges (it cannot decrease forever) and which-is-bigger is preserved.
Thus we know the vector's "shape" converges, but it is still possible the whole vector shifts up and down by a constant amount across all elements.
Part B: Prove that it doesn't oscillate like that. Once the "shape" converges, say to $w$, all possible future vectors are of the form $w + n$ for some $n \in N$, and you should be able to prove that every step brings $v$ closer to the $w+n$ which minimizes $\delta$.
There is a bit of special case where two adjacent solutions $w+n, w+n+1$ both minimize $\delta$ at $\delta = 0.5$ and you will need some argument with the $round()$ function to prove it settles on one of them.