Expected score of two randomly generated binary strings

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$?

• I think you mean that $R(a_i)$ is the number of occurrences of $a_i$ up to index $i$? – iamwhoiam Jul 23 '17 at 8:14
• Yes you are right. – marcella Jul 23 '17 at 8:24
• 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. – Did Jul 23 '17 at 10:33
• @marcella, then it looks like you mean $\max$ instead of $\argmax$. – Marcus M Jul 23 '17 at 16:11
• Now S(A,B) is well defined. Next is "Please add some context to your question". – Did Jul 23 '17 at 20:09

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}).$$
• 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? – marcella Jul 24 '17 at 16:29