0
$\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---------

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ You should have edited your orginal problem -- mathoverflow.net/questions/108599/… -- instead of reposting as a new problem. $\endgroup$
    – Barry Cipra
    Oct 2, 2012 at 14:58
  • $\begingroup$ Don't think this is a research level Q. Also I have no idea what set you're sampling from. Is it all length $N$ strings with $K$ randomly chosen strings removed? $\endgroup$
    – Anthony Quas
    Oct 2, 2012 at 19:53
  • $\begingroup$ @Anthony, your comment would be better posted at the OP's original version, which he has edited in response to (I think) my previous comment, and which has elicited some other comments and an answer. It would be best, I think, if the moderators simply deleted this duplicate problem. $\endgroup$
    – Barry Cipra
    Oct 2, 2012 at 20:06

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.