El uso de decimales de $\pi$ a de almacén de datos

Question

Hace poco leí acerca de una idea que, en lugar de almacenar los datos reales, la conversión de los datos en una cadena de dígitos y, a continuación, guardar el índice de donde este patrón se produce en algún número, por ejemplo,$\pi$. La idea de que el índice de los datos ocupan menos espacio de almacenamiento de los datos reales.

Por supuesto, no sabemos si $\pi$ es un número normal y por lo tanto no sabemos si cada decimal finito patrón se produce, pero vamos a suponer por el momento que se hace (o simplemente los cambios a algunos demostrado número normal, como la Copeland-Erdős constante).

La cosa que me llamó la atención era la de si el índice de los datos podría ser en realidad un número mayor que los datos en sí. ¿Existe alguna medida de la probabilidad de encontrar una secuencia decimal de longitud $n$ antes de la $m$:th decimal? Para $\pi$ en este caso, dudo que haya una fórmula general. Tendría que depender de la base?

Información o referencias a otras ideas similares también son muy bienvenidos.

(Sí, yo entiendo que este método es muy práctico para el uso diario, acabo de encontrar la idea intriguinng.)

Answer 1

Usted no necesita saber nada acerca de $\pi$ a contestar esta una $-$ usted sólo necesita saber que usted no puede obtener algo por nada.

Para ser más precisos: cualquier algoritmo de compresión (que es lo que su esquema es), si es que tiene algunas entradas más cortas, debe también hacer algunas entradas más. Si un algoritmo fue capaz de comprimir, por ejemplo, todos los 10000 bits de entradas en menos de 10000 bits, el número de posibles salidas ($2^{10000} - 1$) sería menor que el número de entradas posibles ($2^{10000}$) $-$ así que, inevitablemente, tienen al menos un par de entradas de la compresión de la misma salida.

Answer 2

Tomando de base decimal, suponiendo (gran asunción) que los dígitos de $\pi$ son aleatorios, (distribución uniforme, iid) , luego se le da un número con $k$ dígitos decimales, la probabilidad de encontrar antes de algún tiempo $n$ es difícil de encontrar en general (véase, por ejemplo aquí), y que podría depender el número en sí.

Un supuesto simplificar sería asumir que todos coincidencia trata son independientes (sin superposición) ; obviamente una suposición falsa, pero en muchos asympotics esta es una buena aproximación). Tendríamos entonces una variable aleatoria geométrica con $p=1-10^{-k}$ (probabilidad de éxito), y su valor esperado $\approx 10^{k}$. Que es el mismo orden que el valor del número. Por lo tanto, según esta muy gruesa aproximación - el "índice" es, en promedio, de la misma magnitud que el número en sí.

Answer 3

La probabilidad de la $n$th dígito de un número normal (si es que tiene esencialmente dígitos al azar) siendo un determinado dígito es $1\over 10$. Por lo tanto, la probabilidad de encontrar una secuencia de $m$ dígitos comenzando con el enésimo dígito es $1 \over 10^m$, por lo que la probabilidad de que la secuencia no se haya producido después de $n$ dígitos es $(1-{1\over 10^m})^n$. Una manera de adivinar el dígito en el que podrían encontrar la secuencia sería encontrar el punto en el que la probabilidad de haber encontrado a se $\frac 1 2$, lo $\log_{1-10^{-m}}(\frac 1 2)$ o $\ln(\frac 1 2)\over \ln(1-10^{-m})$. Este resulta ser un número con casi el mismo número de dígitos, como en la secuencia que se está tratando de tienda, y así se ahorra espacio.