8
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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, $\endgroup$ – R B Jul 5 '14 at 20:35
  • $\begingroup$ Or perhaps I can give a better bound. Thanks again. $\endgroup$ – R B Jul 5 '14 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.