Aumentar el número de repeticiones disminuye la probabilidad de error

Question

En la teoría de la codificación cuando valoramos la 101 con 111000111 tenemos cierta probabilidad de error. ¿cómo se puede demostrar que el aumento del número de repeticiones disminuye la probabilidad de error.

Deje que la probabilidad de un tirón un poco en la recepción es 1-p

Si se hace mediante tres bits, a continuación,

P[a] = Si los dos bits son volteadas. = 3C2 * p^2 * (1-p)

P[B] = Si tres bits se volcó = 3C3 * p^3

P[E] < P[A] + P[B]

Del mismo modo se puede calcular para n=4, pero no soy capaz de generalizar.

Answer 1

Vamos a considerar sólo sea impar el número de repeticiones y $p < q$ donde $p$ es la probabilidad de que un bit flip y $q=1-p$. Deje $E_n$ ser el caso de un error, cuando se repite un poco $2n+1$ veces. Vamos a evaluar $P(E_{n+1})$. Aquí, el error ocurre si hay más de $(n+1)$ volteretas. Para encontrar $P(E_{n+1}$), considere lo que sucede en la primera $2n+1$ transmisiones fuera de la total $(2n+3)$ transmisiones. Hay 4 posibilidades para el número de lanzamientos en la primera $(2n+1)$ transmisiones: (a) $\leq n-1$ volteretas, (b) exactamente $n$ volteretas, (c) exactamente $n+1$ volteretas, (d) $\geq n+2$ volteretas. La probabilidad de evento $E_{n+1}$ en estos 4 casos se $0, p^2, 1-q^2$ $1$ respectivamente.

Para mayor comodidad, definir $\alpha_n = {2n+1 \choose n} (pq)^n$. Entonces

$P(E_{n+1}) = p^2 \alpha_n q + (1-q^2) \alpha_n p + \sum_{k=n+2}^{2n+1} {2n+1 \choose k} p^k q^{n-k}$

La suma es la expresión de la $P(E_n)$ con el primer término que falta, es decir,

$\sum_{k=n+2}^{2n+1} {2n+1 \choose k} p^k q^{n-k} = P(E_n) - \alpha_n p$. Armando estos nos da

$P(E_{n+1}) - P(E_n) = \alpha_n pq (p-q) = {2n+1 \choose n} (pq)^{n+1}(p-q) < 0$.

Edit: Otras respuestas me pegaba a él, pero voy a dejar esto de todos modos.

Answer 2

Bien, no era demasiado difícil en la final. Vamos a escribir $S(p,k)$ para la probabilidad de éxito en la transmisión de un bit, cuando una repetición de código de longitud $2k+1$ es utilizado. Celebrado por zyx (y a mí) la pregunta es muy interesante, sólo, cuando se $0<p<1/2$.

El reclamo es que para todos los $p$ en este rango y todos los enteros positivos $k$ tenemos la desigualdad $$ S(p,k+1)>S(p,k). $$

Para probar que esto suponga que una repetición de código de longitud $2k+3$ se usa una vez. W. l.o.g. podemos suponer que 0 se transmite, por lo que en el recibido bitstring de longitud $2k+3$ cualquier bit es igual a $0$ con una probabilidad de $1-p$ e igual a $1$ el (cross-over) probabilidad de $p$. La transmisión es correcta, iff la mayoría de los bits de ceros. Veamos la subcadena $s$ de la primera $2k+1$ bits. Una mayoría de estas son de 0 con probabilidad $S(p,k)$.

Con el fin de analizar el efecto de los dos bits adicionales necesitamos definir dos eventos: Llame a $s$ a casi el éxito de la cadena (NS), si tiene exactamente $k$ 0s y, en consecuencia, exactamente $k+1$ 1s. IOW, el mensaje correcto perdió por un solo voto. De manera similar llamada $s$ a casi el error de cadena (NF), si el mensaje correcto ganó por un solo voto, es decir no eran exactamente $k+1$ 0 $k$ 1 $s$.

Cuando no el receptor de ver todas las $2k+3$ bits de hacer una decisión correcta acerca de la transmisión de bits? Vemos que su decisión será la misma que con la inicial $2k+1$ bits de $s$, excepto en los dos casos, donde los dos últimos bits son 1, y la cadena de $s$ es casi fracasó, y también en el caso, donde los dos últimos bits son 0, y la cadena de $s$ fue casi un éxito. Así, obtenemos la fórmula $$ S(p,k+1)=S(p,k)+(1-p)^2 P(NS) p^2P(NF). $$ Aquí la distribución binomial nos dice que $$ P(NS)={2k+1\elegir k}p^{k+1}(1-p)^k,\qquad P(NF)={2k+1\elegir k+1}p^k(1-p)^{k+1}. $$ Por lo tanto, dos de los coeficientes binomiales son iguales) $$ (1-p)^2P(NS) p^2P(NF)={2k+1\elegir k}p^{k+1}(1-p)^{k+1}(1-2p)>0. $$ Por lo tanto $S(p,k+1)>S(p,k)$ como se reivindica.

Answer 3

La probabilidad de correctamente la codificación de un poco de repetición $2n+1$ veces es $$ x_n=P(S_{n}\le n), $$ donde el número de errores de $S_{n}$ es binomial $(2n+1,p)$. A continuación, las siguientes sostiene.

Si $0<p<\frac12$, la secuencia de $(x_n)$ es cada vez mayor.

Para probar esto, tenga en cuenta que $S_{n+1}$ es distribuido como $S_n+T$ donde $T$ es binomial $(2,p)$ e independiente en $S_n$. Además, $T=0$, $1$ o $2$ por lo tanto $$ [S_{n+1}\le n+1]=[S_n\le n-1]\copa[S_n=n,T\le1]\copa[S_n=n+1,T=0]. $$ Desde los sucesos de la RHS son distintos, esto produce $$ x_{n+1}=x_n-P(S_n=n)+P(S_n=n)P(T\le1)+P(S_n=n+1)P(T=0), $$ es decir, $$ x_{n+1}-x_n=P(S_n=n+1)P(T=0)-P(S_n=n)P(T=2). $$ Por lo tanto $x_{n+1}>x_n$ si y sólo si $P(S_n=n+1)P(T=0)>P(S_n=n)P(T=2)$.

Pero esta última condición es fácil de comprobar. Suponiendo que $p\ne0$$p\ne1$, $$ \frac{P(S_n=n+1)}{P(S_n=n)}=\frac{p}{1-p}\qquad\text{y}\qquad \frac{P(T=2)}{P(T=0)}=\frac{p^2}{(1-p)^2}, $$ por lo tanto, suponiendo que $p\ne0$ y $p\ne1$, $x_{n+1}>x_n$ si y sólo si $p(1-p)^2>(1-p)p^2$ si y sólo si $1-p>p$ si y sólo si $p<\frac12$ y el resultado deseado se mantiene.

Answer 4

Cuando un bit se transmite como $n$ bits, de manera que, sea cual sea 0 o 1 es más común en la señal recibida es tratada como el valor correcto, la probabilidad de que este protocolo se deje engañar por los errores disminuye exponencialmente (como una función de la $n$).

Si $f(p,n)$ es la probabilidad de un fracaso, ciertamente, $f$ disminuye al $n$ es mayor por $2$, pero no es cierto que $f(p,2k-1) > f(p,2k)$, debido a que hay un nuevo modo de fallo para, incluso,$n$, con igual número de 0's y 1's. Uno al azar se puede romper los lazos y en que versión del protocolo de las probabilidades de fallo de $n=2k-1$ $n=2k$ son iguales.