¿Cuál es la probabilidad de que el número de ceros de una secuencia binaria con una longitud de $m$ al menos $q$?

Question

Para un problema práctico para un proyecto (no educativos) para un amigo necesito tu ayuda.

• Tenemos una secuencia $b$ $m$ valores binarios: $$b_1,...,b_m $$ Update: We have sequence b'of m' hexadecimal ($b_i$=0,1,...15) values: $$b_1,...b'_m$$

• $n<m$ de ellos tiene valor 1, el otro $m-n$ elementos tienen un valor de 0

  $n'<m'$ de ellos no tienen un valor de 0 (pero 1-15), el otro $(m'-n')$ elementos tienen un valor de 0

• Elegimos $x<m$ elementos al azar y el cambio de sus valores (independenty). Así que si $b_j$ es uno de los $x$ elementos, entonces la probabilidad de que su valor es 0 $1/2$ y la probabilidad de que su valor si 1 es $1/2$ después de la modificación.

  Elegimos $x'<m'$ elementos al azar y el cambio de sus valores (independenty). Así que si $b_j$ es uno de los $x'$ elementos, la probabilidad de que su valor es 0 $1/16$ y la probabilidad de que su valor no es 0 $15/16$ después de la modificación.

• Después de eso me gustaría saber cuál es la probabilidad de tener al menos $q<m$ ceros en la modificación de los elementos.

  Después de eso me gustaría saber cuál es la probabilidad de tener al menos $q'<m'$ ceros en la modificación de los elementos.

Necesito un método para calcular esta probabilidad $P(m,n,x,q)$.

Necesito un método para calcular esta probabilidad $P'(m',n',x',q')$.

• $m > 1000$
• $0<n<0.3m$
• $0<x<0.6m$
• $0.5m <q < m$

Alguna idea? Muchas gracias !

Además: si un método matemático no está disponible, también voy a aceptar cualquier respuesta que contiene una completa java o código de matlab donde puedo enchufar $m,n,x$ $q$ con la salida de $P$.

Answer 1

Si no tiene que ser exacto, la aproximación normal será fácil de usar. Si un bit individual es el elegido para ser girada, ha $\frac nm$ oportunidad de comenzar como un $1$ $\frac {m-n}m$ oportunidad de comenzar como un $0$. Ha $\frac n{2m}$ la posibilidad de cambiar de $1$ $0, \frac {m-n}{2m}$la posibilidad de cambiar de $0$ $1$ $\frac 12$de probabilidad de no cambiar. Su número esperado de $1$'s después de flipping es, a continuación, $\mu=n+x(\frac{m-n}{2m}-\frac n{2m})=n+x\frac{m-2n}{2m}.$ de La varianza en el cambio de un solo bit es $\frac 12$, por lo que la desviación estándar del número de $1$ bits después de flipping es $\sigma=\sqrt {x}/2$ Comparar su $q$ $\mu$ver cuántas desviaciones estándar diferentes que son. A continuación, puede ver la probabilidad de que a lo lejos, en una normal estándar o z-score de la tabla. Su lenguaje de programación, bien puede tener una función para esto.

Añadido para el hexagonal problema: el mismo enfoque funciona. Primer lugar, calcular el número esperado de ceros después de la perturbación. Empezar con $n'$ ceros, en promedio, $n'(1-\frac x{m'})$ no va a ser modificado y $\frac x{16}$ de la modificación de dígitos será cero, por lo $\mu=n'(1-\frac x{m'})+\frac x{16}$. El promedio de cambio de la cantidad de ceros en una alteración de dígitos es $\frac 1{16}-\frac {n'}{m'}$ de La varianza en el cambio de un solo bit es $\frac 1{16}\cdot \frac {15}{16}=\frac {15}{256}$. La desviación estándar es, a continuación, $\sigma=\frac {15x'}4$