2
$\begingroup$

For every binary string $A=(a_1,a_2,\ldots,a_n)$ in $\{0,1\}^n$, let $R_k(A)$ denote the number of occurrences of $a_k$ in $(a_1,a_2,\ldots,a_k)$.

For example, if $A=(1,1,0,1,0)$ then $R_k(A)$ from $k=1$ to $k=5$ is $1$, $2$, $1$, $3$, $2$.

If $A$ and $B$ are two binary strings of the same length, then the score of $(A,B)$ is $$S(A,B)=\mathop{\text{max}}_{1\le k\le n}\ \left(R_k(A)+R_k(B)\right)$$

What is the expected score $E[S(A_n,B_n)]$ if $A_n$ and $B_n$ are independent and uniform in $\{0,1\}^n$?

$\endgroup$
  • $\begingroup$ I think you mean that $R(a_i)$ is the number of occurrences of $a_i$ up to index $i$? $\endgroup$ – iamwhoiam Jul 23 '17 at 8:14
  • $\begingroup$ Yes you are right. $\endgroup$ – marcella Jul 23 '17 at 8:24
  • 1
    $\begingroup$ How is $S(A,B)$ defined if the maximum of $R_A(k)+R_B(k)$ is realized at several different indexes $k$? // Please add some context to your question. $\endgroup$ – Did Jul 23 '17 at 10:33
  • 1
    $\begingroup$ @marcella, then it looks like you mean $\max$ instead of $\argmax$. $\endgroup$ – Marcus M Jul 23 '17 at 16:11
  • 1
    $\begingroup$ Now S(A,B) is well defined. Next is "Please add some context to your question". $\endgroup$ – Did Jul 23 '17 at 20:09
3
$\begingroup$

Well, for some $k$ we have $S(A_n,B_n)=R_k(A_n)+R_k(B_n)\leq\max_j(R_j(A_n))+\max_j(R_j(B_n))$. Taking expectations we have $$E(S(A_n,B_n))\leq E(\max_j(R_j(A_n)))+E(\max_j(R_j(B_n)))=2E(\max_j(R_j(A_n))).$$ However, what happens if we look at the last $i$ such that $a_i$ is the more common digit in $A_n$ and $b_i$ is the more common digit in $B_n$? The expected value of $i$ is at least $n-3$, since we have at least a $1/4$ chance that $n$ works, if not at least a $1/4$ chance that $n-1$ works, and so on. Thus we have $E(R_i(A_n))>E(\max_j(R_j(A_n))-3)$, etc. So $$2E(\max_j(R_j(A_n)))-6< E(S(A_n,B_n))\leq2E(\max_j(R_j(A_n))).$$ So to get $E(S(A_n,B_n))$ up to a small error term, we just need to work out $E(\max_j(R_j(A_n)))$. This is just the number of the more common digit. Suppose $n$ is odd (we can do a similar calculation for $n$ even). Then $$E(\max_j(R_j(A_n)))=\sum_{i=0}^n\binom ni 2^{-n}\max(i,n-i)\\ =2\sum_{i=\frac{n+1}2}^n\binom ni 2^{-n}i\\ =n\sum_{i=\frac{n+1}2}^n\binom{n-1}{i-1}2^{-(n-1)}.$$ This is just $n$ times the probability that there are at least $\frac{n-1}{2}$ $1$s in the first $n-1$ digits, which is $\frac12(1+\binom{n-1}{(n-1)/2})$. Using Stirling's formula, $\binom{n-1}{(n-1)/2}=(1+o(1))\sqrt{\frac{2}{\pi n}}$. Putting all this together we get $$S(A_n,B_n)=n+\sqrt{\frac{2n}{\pi}}+o(\sqrt{n}).$$

$\endgroup$
  • 1
    $\begingroup$ In the first line $R_k(A_n)+R_k(B_n)\leq max_j(R_j(A_n))+max_j(R_j(A_n))$. Why not $R_k(A_n)+R_k(B_n)\leq max_j(R_j(A_n))+max_j(R_j(B_n))$? or is it a typo? $\endgroup$ – marcella Jul 24 '17 at 16:29
  • $\begingroup$ Yes, it's a typo, thank you! Will fix. $\endgroup$ – Especially Lime Jul 24 '17 at 17:06

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.