¿Cómo Ruido Aleatorio Suelen Buscar?

Question

¿Cómo afecta el ruido aleatorio en el mundo digital suelen buscar?

Suponga que tiene una memoria de n bits, y supongamos que un "ruido aleatorio" llega a la memoria de tal manera que la probabilidad de cada uno de los bits que están siendo afectadas es en la mayoría de los t.

¿Cuál será el comportamiento típico de un aleatoria de ruido digital? Parte de la cuestión es definir el concepto de "ruido aleatorio" de la mejor manera posible, y, a continuación, responder por esta definición.

La misma pregunta se le puede pedir para una memoria basada en una mayor r-letras del alfabeto.

En particular (como Greg mencionado) me interesa saber: ¿el "ruido aleatorio" comportarse normalmente en una forma que está cerca de ser independiente en los diferentes bits? o será altamente correlacionados? o pehaps la respuesta depende del tamaño del alfabeto y el valor de t?

El origen de esta pregunta es fácil de hecho acerca de la memoria cuántica que afirma que si usted se considera un ruido aleatorio de la operación actúe en una memoria cuántica con n qubits, y si la probabilidad de que cada qubit está dañado es un pequeño número real t, entonces normalmente el ruido tiene la siguiente forma: con gran probabilidad, no pasa nada y con mínima probabilidad de una gran parte de los qubits son perjudicados. (En este caso, el ruido aleatorio es altamente correlacionados.)

Hice un intento para el digital (binario) de la pregunta, pero no estoy seguro del todo que es la "correcta" la definición de lo "ruido aleatorio". Me considera una permutación aleatoria de todos la 2^n cadenas binarias de longitud n sujetas a la condición de que en la mayoría de los t bits se volcó. Voy a ser feliz si alguien puede pensar en el caso de los más grandes del alfabeto y también ofrece la conceptualmente "correcta" marco para esta pregunta.

Quizás la mejor forma de hacer esta pregunta (después de Jason y Greg observaciones) es esta: ¿Cuál es la forma apropiada para definir a un "azar" distribución de probabilidad en {0,1}^n y en {0,1,...,r}^n.

Dada esta definición que la gustaría entender el comportamiento típico de un aleatorio de distribución de probabilidad con la propiedad adicional de que la probabilidad de que la i-ésima coordenada de ser distinto de cero es en la mayoría de t para cada i.

Actualizado formulación: Una manera de resolver la cuestión fue propuesto por Greg: el espacio de La estocástico mapas en una probabilidad finita de espacio es un convexo polytope. Así que usted puede elegir el uso de una norma Euclidiana medida. (En nuestro caso, la probabilidad finita de espacio es el uniforme de la probabilidad de espacio en {0,1}^n, y, más en general, el uniforme de probabilidad espacio en {0,1,...,r}^n.)

La pregunta es (indicado por el binario caso) este: sea t>0 un pequeño número real. ¿Cómo funciona un azar estocástico mapa, con la condición de la propiedad que una proporción de t bits están dañados parece. También es el caso, como Greg espera, que (como en el quantum caso), con gran probabilidad, no pasa nada y con probabilidad pequeña cantidad de bits están dañados.

Voy a ser feliz, a ver cómo se hace el cálculo de la precisión o de forma heurística, o tal vez a encontrar en la literatura.
Actualización: La noción de Arikan la polar de codificación (Ver, por ejemplo, este papel) es algo relacionado con esta cuestión.

Answer 1

Creo que la gente podría ser la interpretación errónea de la pregunta.

El sencillo hecho de que creo que Gil tiene en mente es que si que elegir al azar un quantum de ruido de operación con ciertas propiedades, a continuación, para la mayoría de las opciones de que el ruido de la operación, aunque el total de la tasa de error es muy baja, los errores serán altamente correlacionados. La interpretación ortodoxa es que esta es una forma artificial para elegir un quantum modelo de ruido.

Un análogo clásico pregunta es la siguiente: Si usted escoger al azar un punto de vista estocástico mapa de la probabilidad en el espacio de cadenas de bits, con propiedades similares, ¿qué le parece?

Gil propone un elegido al azar permutación sujeto a la condición de que en la mayoría de los t bits se volcó. No estoy seguro de que eso es realmente una buena analogía para el quantum de ruido modelo que él propone.

El proceso de Poisson que voltea bits es un modelo específico de ruido aleatorio en cadenas de bits. No es un elegido al azar modelo de ruido.

---

Gil ha añadido que el más específico de la pregunta de por qué un azar estocástico mapa acondicionado en pocos errores tendrá la "emboscada ruido" de la propiedad que se describe por un azar del operador unitario. No es más complicado que la versión, en el que cada bit por separado tiene un límite de error, y una versión más simple, donde sólo la demanda que en la mayoría de las $tn$ de la $n$ bits están cambiado. Voy a mirar la versión más simple. Como primer paso, las diferentes entradas a la estocástico mapa no se comunican en esta pregunta. Cada cadena de bits, por ejemplo, la cadena de 0s, es enviado a otra cadena de bits de acuerdo a una distribución que es uniforme en el simplex de todos los $2^n$ cadenas de bits. Así que me concentraré en lo que sucede a 0 de la cadena.

Una observación es que el destino de sólo el 0 cadena es en realidad estadísticamente idénticos, si usted elige una al azar estocástico mapa clásico o un azar unitario operador quantumly. La primera columna de una al azar operador unitario es un vector aleatorio en $\mathbb{C}P^{N-1}$ ($N = 2^n$ para estados unidos). La inducida por el mapa de $\mathbb{C}P^{N-1}$ $(N-1)$- simplex de distribuciones es una tóricas momento de mapa, y un famoso hecho (debido a Arquímedes para $\mathbb{C}P^1$) es que tóricas momento de mapas medida de preservación. La diferencia entre un azar estocástico y aleatorio unitario sólo aparece primero parejas con las correlaciones, y al $N$ es grande sólo de muy alto orden, las correlaciones son significativas. Si Gil tiene un argumento en el que el azar unitaries, esta observación sugiere que también se aplica para el azar estocásticos.

Más directamente, una distribución en cadenas de bits induce una distribución de pesos de Hamming de cadenas de bits. Este es un lineal mapa de una enorme simplex $\Delta_{N-1}$ a los más pequeños simplex $\Delta_n$ cuyas esquinas están marcados por el Hamming pesos $0,1,\ldots,n$. Estamos interesados en el impulso hacia adelante de uniforme medida. Deje $p_0,\ldots,p_n$ ser baricéntrico coordenadas en $\Delta_n$; $p_k$ es también la probabilidad de que el azar cadena de bits tiene peso $k$. A continuación, empuje hacia adelante de uniforme medida en $\Delta_{N-1}$ es proporcional a $f(p) \propto \prod_k p_k^{\binom{n}{k}}$. Así, en este inducida por la medida en $\Delta_n$, existe una enorme estadístico de atracción para las esquinas con la media de los valores de $k$.

Ahora vamos a imponer la restricción de que el error total es en la mayoría de las $tn$, en otras palabras que $$\sum_k kp_k \le tn.$$ Esto reduce el simplex $\Delta_n$ por un hyperplane. En este punto voy a cambiar a un cálculo aproximado. Si $t \ll \frac12$, y si a maximizar el logaritmo de la densidad de probabilidad $\log f(p)$, el máximo que pone la mayoría de la probabilidad en los pesos $k \approx n/2$. Eso es porque el término correspondiente en $\log f(p)$$\binom{n}{k}(\log p_k)$. La dependencia logarítmica en $p_k$ es superado por el tamaño de los coeficientes. También hay un factor geométrico si está cerca de una esquina aguda de la corte simplex; sin embargo, después de un logaritmo este factor geométrico es de orden $n$, en tanto que es mucho más pequeño que el de los coeficientes binomiales.

Answer 2

Todavía estoy pensando en el problema original, pero permítanme discutir el problema en el lado de azar cadenas.

En el caso infinito de la forma correcta para designar "al azar" es bastante similar a la de "random tree" problema trajo hasta recientemente: dada una cadena de longitud n, cada posible cadena de longitud se produce con la misma frecuencia. Esta es la forma "normal" se define para trascendental números para capturar la noción de que ellos se producen al azar.

Esto es problemático para el caso finito, porque la cadena 1111111111 puede ocurrir con igual probabilidad como la cadena de 1100101010. A partir de un "puro" punto de vista no parece haber nada que podamos decir, pero en aplicar circunstancia con una muestra bastante grande de conjunto es posible obtener una noción de sesgo.

(Fuente de imagen, también más información sobre lo que estoy discutiendo.)

Esperaríamos que (dejar que p(n) es el número de total de permutación de las cadenas en la n primeros dígitos de una cadena) que en la base de diez n/p(n) convergían para 2755.

El "sintetizado" los datos en el gráfico de arriba proviene de la infame Corporación Rand trabajo de Un Millón de Dígitos al Azar, y parece tener un tipo de sesgo.

Sin embargo, en el caso de una convergencia de la secuencia (como los dígitos de pi) en el bajo-n de los casos es imposible determinar nada de n/p(n). Esto me sugiere que el modelo de ruido único problema que puede ser abordado (si en absoluto) de la gran n caso.

Answer 3

Creo que hay un punto de posible confusión con lo que quiere decir que hay un error. Cuando pienso en un proceso de ruido en un sistema cuántico, creo que el siguiente. Dado un estado inicial $\rho$ del sistema, el ruido es un proceso completamente positivo mapa de $\mathcal{E}$ que produce el estado de la salida $\sigma = \mathcal{E}(\rho)$. Así que, a menos que el canal es la identidad de canal, entonces siempre hay algo trivial sucediendo (por lo menos para algunos la elección de estado inicial $\rho$). Así ha ocurrido un error? En cierto sentido, sí. Incluso si el canal tiene un operador de descomposición donde una gran parte del apoyo de la canal es sobre la identidad del canal, luego de que en general hay siempre un error. Creo que el punto de confusión es que para estos tipos de canales, al medir el estado en el que se va a colapsar en un estado con ningún error, o de un estado con el que (potencialmente) un montón de errores. Así que, sí, los errores están altamente correlacionados. Pero el canal está tratando de modelo de algún tipo de independencia condicional. Después de la medición, usted piensa en el canal como de haber actuado trivialmente, o de haber hecho algo malo, como aplicar un muestreo aleatorio de Pauli error. Condicionada a que ocurra algo malo, entonces usted tiene la independencia.

(Para personas no familiarizadas con quantum canales, un modelo clásico que muestra este tipo de comportamiento sería una especie de "pérdida catastrófica" del canal, donde se ponen todos a $n$ bits en el canal, y con una probabilidad de $1-\epsilon$ son transmitido fielmente, y con una probabilidad de $\epsilon$ que tirar de la cadena de bits y reemplazarlo con el ruido, la c.f. algo que muestra de manera uniforme desde el hipercubo.)

También, siguiendo a Gil comentario de Greg en la respuesta de una manera obvia para definir al azar estocástico mapa sería simplemente escoger al azar de las distribuciones de probabilidad y los hacen las filas de una matriz estocástica. Escoger una distribución aleatoria que se podría hacer por elegir su favorito de la medida sobre el simplex cuyos puntos son etiquetados por cadenas de bits. Usted todavía tiene que decidir cómo elegir las dependencias entre las filas. Incluso en el simple y natural caso del uniforme de la medida y de forma independiente elegido filas, no es claro para mí cómo se ve esto.

Answer 4

El tipo de ruido que podría manejar ('filtro' o recuperar) es tal que para cualquier tiempo t, cualquier k bits son dañados con la probabilidad en la mayoría de epsilon^k para algunos pequeños positivo epsilon.

Answer 5

Si pensamos en una función booleana de tipo $\mathbb{B}^k \to \mathbb{B}$ como una "proposición" sobre cadenas de bits en $\mathbb{B}^k$, entonces viene a ser el ejemplo más simple de una "distribución"$\mathbb{B}^k$. Mantener el campo GF(2) para todo a la vista, una función de tipo de $(\mathbb{B}^k \to \mathbb{B}) \to \mathbb{B}$ puede ser pensado como un "orden superior de la proposición", es decir, una proposición acerca de las proposiciones acerca de las cadenas de bits de longitud $k$. Pero también puede ser considerado como el ejemplo más simple de una distribución de las distribuciones en el espacio,$\mathbb{B}^k$, en otras palabras, una "medida" en las distribuciones más de $\mathbb{B}^k$. El vínculo que se acaba de dar exhibe algunas fotos de la escasa dimensión de casos $k = 1, 2$ que pueden ayudar a la intuición un poco.