Probabilidad de compartir un número fijo de bits

Question

Digamos que hay un conjunto $\mathcal{S}$ de enteros aleatorios de 32 bits, donde cada bit se denota de $b_0$ a $b_{31}$ .

Quiero saber cómo calcular la cardinalidad $c =$ # $\mathcal{S}$ de la cual $\mathcal{S}$ podría contener $n$ enteros que tienen $x$ sucesivos bits constantes, con una alta probabilidad $p$ .

Por ejemplo, ¿qué tamaño debe tener $c$ ser para tener $n = 200$ enteros con $b_0$ a $b_{11}$ constante ( es decir $x=12$ ) con una probabilidad $p \geq 0.9$ ?

Answer 1

Hay $2^{12}=4096$ posibilidades para la $12$ bits. Puede garantizar que habrá $200$ números que coinciden con todos los $12$ de estos bits si $c=199\cdot 4096+1$ por el principio de encasillamiento .

Para una respuesta aproximada a la pregunta de cuántos se necesitan para una probabilidad menor utilizaremos el Distribución de Poisson . Para un conjunto dado de los $12$ bits, la probabilidad de que cada número coincida con aquellos es $\frac 1{2^{12}}$ por lo que el número esperado es $\lambda=\frac c{2^{12}}$ . La posibilidad de tener al menos $200$ es $p_1=\sum_{k=200}^\infty \frac {\lambda^ke^{-\lambda}}{k!}$ . La posibilidad de que ninguno de ellos tenga al menos $200$ es entonces $(1-p_1)^{4096}$ que quiere menos que $0.1$ . Obtenemos $p_1 \approx 0.000562$ Resolver para $\lambda$ se puede hacer usando la función gamma incompleta, pero no puedo obtener una respuesta de Alpha. Esto pretende que el par de un número que va en un conjunto de $12$ bits es independiente de su paso por otro conjunto de $12$ bits, lo que no es absolutamente correcto pero no está muy lejos porque el número de conjuntos es grande.