most recent 30 from http://mathoverflow.net 2013-05-22T10:53:32Z http://mathoverflow.net/feeds/user/26931 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 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/108637/expected-number-of-shared-1s-between-two-binary-strings-from-a-given-set big daddy 2012-10-02T14:13:13Z 2012-10-02T14:13:13Z

<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>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 big daddy 2012-10-02T13:33:17Z 2012-10-02T13:33:17Z

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.