What is the value of this “game” (counters rebalancing)?

This question was posted in CS.SE two weeks ago, but it didn't get a satisfying answer.

Suppose you have the following game:

There are infinitely many counters $\{c_1,c_2,\ldots\}$, all initialized to 0.

In each step, you choose a counter $c_i$ and increase it's value by 1.

Unfortunately, every $T$ steps, each counter that has a positive value is decremented by 1.

Also, the values of the counters are bounded by $M$, so you can't increment a counter any further.

1. Given as many steps as you like, can many positive valued counters can you reach?

2. How many positively valued counters are reachable after $T\cdot M - 1$ steps?

For question (1), here's a a detailed buildup for $\approx T\log(M)$ positive counters:

1. While you have less than $T-1$ counters at value $M$:
• Increment the minimal index counter whose value is strictly less than $M$.

(This has to converge as the sum of the counters are bound to increase every $T$ steps.)

1. Let $r = T$.

2. While ($c_0>1$)

a. while ($c_0>c_r$)

• Increment $c_r$

b. $r = r + 1$

Now for the analysis: first observation is that the number of positive counters is $r$.

Now let $m_r$ be the maximal value $c_{r}$ have reached. For $r=T$ we get $M(1-\frac{1}{T})$. For $r=T+1$ we get $m_r(1-\frac{1}{T})=M(1-\frac{1}{T})^2$, or in general $$\forall r\geq T:m_r = M(1-\frac{1}{T})^{r-T+1}$$

Next we notice that when $\forall m_r$ is achieved, $c_0=m_r$. This means the loop will halt when $m_r < 1$ (give or take integrality and end-of-game-strategies).

This gives us $$M(1-\frac{1}{T})^{r-T+1} < 1$$ $$(1-\frac{1}{T})^{r-T+1} < M^{-1}$$ $$({r-T+1}) \log (1-\frac{1}{T}) < -\log M$$ $${r-T+1} < \frac{-\log M}{\log (1-\frac{1}{T})}$$ $$r < \frac{-\log M}{\log (1-\frac{1}{T})} + T - 1$$ $$r < \frac{\log M}{\sum_{k\geq 1}^{\infty} {\frac{1}{kT^k}}} + T - 1 < T(\log M + 1) -1$$

Is it possible to do better? Can anyone prove this is optimal?

Lower bound for question 2:

Theorem: After $TM-1$ steps, with the strategy outlined below, you will have at least $(T-1)\log M$ positive counters.

Notation: Define time step $1$ to be the beginning of the $TM-1$ steps, and $TM-1$ to be the end. Decrements happen on time step $Tk$, $1 \le k < M$.

Define the upper limit to be $M- \lfloor N/T \rfloor$, where $N$ is the current time step. This limit starts at M, and decreases by one whenever the counters decrease, ending at $1$. This limit is chosen because if more counters are ever put on a cell than the upper limit, they will be wasted, because the counter will have value more than $1$ on step $TM-1$.

Strategy: On every time step, increment the leftmost counter whose value is less than the upper limit.

Notation: Define the importance of a counter to be $V/UL$, where V is its current value, and $UL$ is the current upper limit.

Lemma: In each group of $T$ steps ending on a decrement, the sum of the importances of the counters increases by at least $(T-1)/UL$, where $UL$ is the current upper limit.

Proof of lemma: Each time a counter is incremented, its importance rises by $1/UL$. When the decrement happens, all but one counter is at its upper limit and has an importance of $UL/UL=1$. The remaining counter's importance is shrunk by at most $1/UL$, because its value decreases by $1$, and $UL$ does not increase. Thus, the $T$ increments and $1$ decrement increase the total importance by at least $(T-1)/UL$. In addition, in the last group of $T-1$ increments, where no decrement occurs, the sum of importances increases by $(T-1)/UL$.

Proof of theorem: In each group of $T$ steps ending in decrement, and in the final $T-1$ steps, the sum of importances increases by at least $(T-1)/UL$. Therefore, after $TM-1$ steps, the sum of importances will be at least $\sum_{k=1}^m(T-1)/k$, which is at least $(T-1)\log M$. Since on time step $TM-1$ the upper limit is $1$, there must be $(T-1)\log M$ positive counters at this time.

Here is an upper bound for question 2.

Theorem: After $TM$ steps, you can have at most $T \log M$ positive counters.

Notation: we assign each step a number, ending with the $0$th step, and starting with the $(-TM+1)$th step.

Observation: in the optimal strategy, if you increment a counter, you do not let it return to $0$.

Proof: Let us assign a value of $1$ to each time you increment a counter in the last $T$ steps; $\frac{1}{2}$ to each time you increment a counter in the previous $T$ steps; $\frac{1}{3}$ to each time you increment a counter in the $T$ steps before that, etc. That is, if you increment a counter between step $-kT+1$ and $-(k-1)T$, it gets a value of $\frac{1}{k}$. We need a lemma that we will prove later.

Lemma: for a counter to be positive, it must have had a total value of at least $1$ assigned to it.

With the lemma, the proof is easy: the total value we have to assign is $T \sum_{i=1}^M \frac{1}{i} \approx T \log M$, and each positive counter requires us to have assigned total value of at least $1$ to it.

Proof of Lemma: Look at the first time you made that counter positive. If that was between $-kT$ and $-(k-1)T$, then it has been decremented at least $k-1$ times, and so you need to have incremented it $k$ times to have it end up positive. But each of these increments assigns it a value of at least $\frac{1}{k}$.

And here is an upper bound for question 1. Let's use the same overall proof strategy as before. Again, we assign a value of $\frac{1}{k}$ when we increment a counter on a step between $-kT+1$ and $-(k-1)T$. We also assign a value of $\frac{1}{M}$ when we increment a counter on a step between $-2MT$ and $-MT$, and a value of $0$ if we increment a counter before that. By the same reasoning as before, any counter that was $0$ at step $-2MT$ must be assigned a value of at least $1$. But now, if a counter was positive at step $-2MT$, it still must have been assigned a total value of at least $1$, since it must have been incremented $M$ times to end up positive. Now, the total value we have to assign is $T\log M + T$, so we can have at most $T (\log M + 1)$ positive counters.

• Thanks for the answer! I'm actually more interested in the lower bound of question (2). The motivation for this question comes from an algorithm I have for approximate counting of items in a sliding window (every iteration you see some element $x$ and every query is of the form "how many times $x$ appeared in the last $N$ steps). The counter decrementing is done in order to keep the number of positive counters small (but increases the error), and I can flush the buffer every $N=TM$ steps and still keep the error small, but I'm wondering if indeed a $\Omega(T\log M)$ counters could be positive, – R B Jul 5 '14 at 20:35
• Or perhaps I can give a better bound. Thanks again. – R B Jul 5 '14 at 20:35