4
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.