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

 A: 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}).$$
