Constructing a bad sequence for counter algorithm

Question

Assume that we want to construct a sequence $s\in\{a,b\}^{N}$ such that $s$ contains exactly $n$ times the letter '$a$'.

The sequence is then feed to the following probabilistic algorithm:

• Initialization: $c = \begin{cases}1&\text{if } s_1=a\\0&otherwise\end{cases}$, $id = s_1$
• For $i=2,3,\ldots N$:
  • If ($id = a$ and $s_i = a$)
    • c += 1
  • Else if ($id\neq s_i$)
    • With probability $1/(c+1)$, replace $id$ with $s_i$ and increment $c$, or do nothing otherwise

Notice that the value of $c$ after processing the $N$ elements is a random variable. Denote its final value by $C$.

How to construct a sequence which minimizes $\mathbb E(C)$?

---

The motivation for this question comes from a streaming algorithm for heavy hitters, where such sequence could be the worst-case scenario. $b$ here represents all "tail" items (assumed to appear no more than once) which interfere with the heavy hitter $a$ we are trying to count.

---

For example, consider $N=5, n=2$ and the sequence is $a,b,b,a,b$.

$c$ starts with $1$. With probability $3/4$, the $id$ will be replaced by $b$ in $i=2,3$, so after seeing $a,b,b$ we have:

• $id = a, c = 1$ with probability $1/4$
• $id = b, c = 2$ with probability $3/4$

Now $a$ comes. If $id=a$, $c$ is incremented, otherwise, $id$ is replaced with probability $1/3$, so after seeing $a,b,b,a$ we get:

• $id = a, c = 2$ with probability $1/4$
• $id = a, c = 3$ with probability $1/4$
• $id = b, c = 2$ with probability $1/2$

When the final $b$ arrives, it may increase the counters, depending on $id$, so overall we get:

• $id = a, c = 2$ with probability $1/6$
• $id = b, c = 3$ with probability $1/12$
• $id = a, c = 3$ with probability $3/16$
• $id = b, c = 4$ with probability $1/16$
• $id = b, c = 2$ with probability $1/2$

So overall we get $\mathbb E(C)\approx 2.4$.

Which is worse than the sequence $b,b,b,a,a$, in which $C=2$ at the end with probability $1$.

Is late arrival ($s=b^{N-n}a^n$) always the best sequence for minimizing $\mathbb E(C)$?

(In fact, we only "identify" $a$ if $id=a$ at the end, and we can show that in such cases, $\mathbb E(C) \le n$, so we are not concerned with overestimation here).