número esperado de 1s compartidos entre dos cadenas binarias de un conjunto dado

Question

Supongamos que tengo dos cadenas binarias de longitud N, elegidas de un conjunto en el que hay $2^N-K,(K \ge 0)$ cuerdas independientes. ¿Cuál sería el número esperado de Unos en el mismo índice a partir de dos cadenas elegidas al azar del conjunto?

Por ejemplo, 0010 y 1010, el número de unos en el mismo índice es 1. ¿Puede estar relacionado de algún modo con la distancia hamming esperada entre dos cadenas binarias?

------mi propia conjetura, alguien podría por favor verificar---------

**Lo siento por el desorden, sin querer, el nuevo problema fue publicado con esta parte..

tener 1 en la posición i-ésima es un suceso independiente. Por lo tanto, P(c_i=1) es la probabilidad de tener un 1 común en la posición i-ésima. Entonces, el número esperado de 1s compartidos será $\sum_{0..N-1} P(c_i)$ . Desde el $2^N-K$ para la posición ith, cuente el número de 1s (denote $N^1_i$ ), y el número de 0s (denote $N^0_i$ ). Entonces $P(c_i)=\frac{N^1_i C 2}{(N^1_i+N^0_i) C 2}$ . (C es combinaciones) cuando $N^1_i>=2$ de lo contrario $P(c_i)=0$ .

Para un ejemplo de {11110,1111,01110}, me da 3,66666, que parece correcto.

Answer 1

Suponiendo que he entendido bien la pregunta, esto depende totalmente de la distribución de 1's entre los que faltan $K$ cuerdas.

En concreto $M = \{m_1,\ldots,m_K\}$ son las cadenas que faltan, y para $i \in \{0,\ldots,N-1\}$ deje $k_i = \\#\{ m \in M \mid m[i] = 1\}$ donde $m[i]$ es el $i$ -ésimo bit de $m$ .

Entonces, la probabilidad de que dos cadenas de bits elegidas al azar de las restantes $2^N - K$ ambos tienen su $i$ -ésimo bit igual a $1$ es $\binom{2^{N-1} - k_i}{2}/ \binom{2^N - K}{2}$ y como estos sucesos son independientes, el número esperado de índices que son ambos 1 es $$ \sum_{i=0}^{N-1} \binom{2^{N-1} - k_i}{2}/ \binom{2^N - K}{2}. $$