expected number of shared 1s between two binary strings from a given set - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T03:37:53Z http://mathoverflow.net/feeds/question/108599 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108599/expected-number-of-shared-1s-between-two-binary-strings-from-a-given-set expected number of shared 1s between two binary strings from a given set big daddy 2012-10-02T04:53:23Z 2012-10-02T18:42:20Z <p>Let say, I have two binary strings with length N, chosen from a set where there are $2^N-K,(K \ge 0)$ independent strings. What would be the expected number of Ones at the same index from two randomly picked strings from the set?</p> <p>For example, 0010 and 1010, the number of ones at the same index is 1. Can it be by somehow related to the expected hamming distance between two binary strings?</p> <p>------my own guess, some one could please verify---------</p> <p>**sorry for the mess, unintentionally, the new problem was posted with this part..</p> <p>having 1 at the i-th position is an independent event. So, let P(c_i=1) is the probability of having a common 1 at i-th position. Then, the expected number of shared 1s will be $\sum_{0..N-1} P(c_i)$. From the $2^N-K$ set, for ith position, count the number of 1s (denote $N^1_i$), and the number of 0s (denote $N^0_i$). Then $P(c_i)=\frac{N^1_i C 2}{(N^1_i+N^0_i) C 2}$. (C is combinations) when $N^1_i>=2$, otherwise $P(c_i)=0$.</p> <p>For an example of {11110,1111,01110}, it gives me 3.66666, which sounds correct.</p> http://mathoverflow.net/questions/108599/expected-number-of-shared-1s-between-two-binary-strings-from-a-given-set/108657#108657 Answer by Granger for expected number of shared 1s between two binary strings from a given set Granger 2012-10-02T18:42:20Z 2012-10-02T18:42:20Z <p>Assuming I've understood the question correctly, this depends entirely on the distribution of 1's amongst the missing $K$ strings. </p> <p>In particular, let $M = \{m_1,\ldots,m_K\}$ be the missing strings, and for $i \in \{0,\ldots,N-1\}$ let $k_i = \#\{ m \in M \mid m[i] = 1\}$, where $m[i]$ is the $i$-th bit of $m$.</p> <p>Then the probability that two randomly chosen bitstrings from the remaining $2^N - K$ both have their $i$-th bit equal to $1$ is $\binom{2^{N-1} - k_i}{2}/ \binom{2^N - K}{2}$, and since these events are independent, the expected number of indices which are both 1 is $$\sum_{i=0}^{N-1} \binom{2^{N-1} - k_i}{2}/ \binom{2^N - K}{2}.$$ </p>