<p>Lower bound for question 2:</p>

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

<p><strong>Notation:</strong>
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 &lt; M$. </p>

<p>Define the <em>upper limit</em> 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$.</p>

<p><strong>Strategy:</strong> On every time step, increment the leftmost counter whose value is less than the upper limit.</p>

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

<p><strong>Lemma:</strong> 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.</p>

<p><strong>Proof of lemma:</strong> 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$.</p>

<p><strong>Proof of theorem:</strong> 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.</p>

CC BY-SA 3.0
2014-07-08T00:05:23.697Z
2014-07-08T00:05:23.697Z
isaacg
<p>Here is an upper bound for question 2.   </p>

<p><strong>Theorem:</strong> After $TM$ steps, you can have at most $T \log M$ positive counters. </p>

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

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

<p><strong>Proof:</strong> 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.</p>

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

<p>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.</p>

<p><strong>Proof of Lemma:</strong> 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}$.</p>

<p>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.</p>

CC BY-SA 3.0
2014-07-05T20:35:14.790Z
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
CC BY-SA 3.0
2014-07-05T20:35:40.830Z
Or perhaps I can give a better bound. Thanks again.
R B
CC BY-SA 3.0
2014-07-04T19:46:35.653Z
2014-07-04T21:36:31.073Z
2014-07-04T21:36:31.073Z
Peter Shor 
<p>This question was <a href="https://cs.stackexchange.com/questions/27777/whats-the-value-of-this-game-rebalancing-counters">posted in CS.SE two weeks ago</a>, but it didn't get a satisfying answer.</p>

<p>Suppose you have the following game:</p>

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

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

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

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

<blockquote>
  <p><strong>1. Given as many steps as you like, can many positive valued counters can you reach?</strong></p>
  
  <p><strong>2. How many positively valued counters are reachable after $T\cdot M - 1$ steps?</strong></p>
</blockquote>

<hr>

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

<ol>
<li>While you have less than $T-1$ counters at value $M$:

<ul>
<li>Increment the minimal index counter whose value is strictly less than $M$.</li>
</ul></li>
</ol>

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

<ol start="2">
<li><p>Let $r = T$.</p></li>
<li><p>While ($c_0&gt;1$)</p>

<p>a.  while ($c_0&gt;c_r$)</p>

<ul>
<li>Increment $c_r$</li>
</ul>

<p>b. $r = r + 1$</p></li>
</ol>

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

<p>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}$$</p>

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

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

<p>Is it possible to do better? Can anyone prove this is optimal?</p>

<ds.algorithms><board-games>
What is the value of this "game" (counters rebalancing)?
R B
# What is the value of this "game" (counters rebalancing)?

(Asked by: username_0 on 2014-06-30)

This question was [posted in CS.SE two weeks ago](https://cs.stackexchange.com/questions/27777/whats-the-value-of-this-game-rebalancing-counters), 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.)

2. Let $r = T$.
3. 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?

**Tags:** ds.algorithms, board-games

---

## 2 answers

### Answer by username_1 on 2014-07-08. Score: 5 | Accepted answer

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.


---

### Answer by username_2 on 2014-07-04. Score: 5

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.

> **Comments:**
> **username_0**: 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,  
> **username_0**: Or perhaps I can give a better bound. Thanks again.  

---

