2
$\begingroup$

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?

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?

------my own guess, some one could please verify---------

**sorry for the mess, unintentionally, the new problem was posted with this part..

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

For an example of {11110,1111,01110}, it gives me 3.66666, which sounds correct.

$\endgroup$
3
  • $\begingroup$ What do you mean by "independent"? $\endgroup$ Oct 2, 2012 at 5:49
  • 1
    $\begingroup$ My first guess of the intended meaning is that you first choose, uniformly randomly, $2^N-K$ of the $2^N$ binary strings of length $N$, and then, from those $2^N-K$ strings, you randomly choose two and check in how many places both have 1's. But that seems equivalent to just choosing 2 among all $2^N$ strings, so it's probably not what was intended. I'll vote to close, as "not a real question", with the hope that the OP will clarify what he intended to ask. $\endgroup$ Oct 2, 2012 at 8:37
  • $\begingroup$ Gerry Myerson: that means no two identical strings in the set. Andreas Blass: 2^N-K is a given set, meaning some binary strings are not available. That makes the probability of having 1 at i-th position is biased. For example, when K=0, it is 0.5 exactly. But, when K=2^N-2 and two remaining strings are 11110 11111, the probability of having one at 0,1,2,3 the position is 1.0, while 4th has 0.5. $\endgroup$
    – big daddy
    Oct 2, 2012 at 13:33

1 Answer 1

1
$\begingroup$

Assuming I've understood the question correctly, this depends entirely on the distribution of 1's amongst the missing $K$ strings.

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

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}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.