Cómo Calcular La Distribución Binomial De Muy Pequeño %?

Question

Le pregunté a esta pregunta en el Foro de Bitcoin, pero creo que es más apropiado para las matemáticas foro.

Estoy haciendo un video informativo y necesito una distribución binomial de cálculo. Quiero averiguar cuántas pruebas son necesarias para conseguir un 1%, 50% y 90% de probabilidades de 1 o más éxitos. El problema es que la probabilidad de éxito es de 1 de cada 2^160 (número de distintos bitcoin/etereum direcciones).

Normalmente para algo como esto, me gustaría utilizar una distribución binomial de cálculo en Excel utilizando esta fórmula:

=1-BINOM.DIST(0,????,2^-160,TRUE)

Me permitiría jugar con el ???? hasta que todo el resultado de la celda devuelve el 1%, 50% y 90%. Sin embargo, Excel no puede manejar los números en cualquier lugar cerca de este tamaño. ¿Alguien sabe de alguna manera de calcular el número de ensayos requeridos para estos 3 porcentajes dada la infinitesimalmente pequeña probabilidad de éxito? Sería genial si hubo una herramienta en línea que podría utilizar para apoyar mis resultados.

Sólo para ilustrar lo que estoy buscando. Si este análisis fue por algo mucho más simple, tal como una probabilidad de éxito de 1%, entonces yo podría calcular los resultados a ser:

• 229 ensayos necesarios para el 90%, | 89.99%=1-BINOM.DIST(0,229,0.01,TRUE)
• 69 ensayos necesarios para el 50%, | 50.01%=1-BINOM.DIST(0,69,0.01,TRUE)
• 1 juicio necesarios para el 1%, | 1.00%=1-BINOM.DIST(0,1,0.01,TRUE)

Answer 1

Dejando $p$ la probabilidad de éxito en un juicio, y dejando $T$ ser el deseado probabilidad de que quieres superar (al menos un éxito en $n$ de los ensayos), tenemos $$1-(1-p)^n>T$$ Esto puede ser reescrita como $(1-p)^n<1-T$.

Así que queremos que $n\ln(1-p)<\ln(1-T)$

Que es equivalente a $n>\frac{\ln(1-T)}{\ln(1-p)}$

Si $p$ es muy pequeño, se obtiene una muy buena aproximación a $\ln(1-p)$ con un grado de una aproximación de Taylor: $\ln(1-p)\approx -p$. (El término siguiente de la aproximación de Taylor se $\frac{-p^2}{2}$, lo que probablemente puede considerarse despreciable; y el error global también será de alrededor de este valor.)

Por lo que se quiere $n$ a alrededor de $\frac{\ln(1-T)}{-p}$

En el caso de $p=2^{-160}$, esto le da a $n > -2^{160}\cdot \ln(1-T)$

Answer 2

Utilizando el manual de juguetear con R I a obtener los siguientes valores

pbinom(0,3.365231884e48,2^(-160), FALSE)   = 0.9000000000339017
pbinom(0,1.0130357393e48,2^(-160), FALSE)  = 0.5000000000001161
pbinom(0,1.46885823057e46,2^(-160), FALSE) = 0.01000000000005571

Como un cheque

pbinom(0,229,0.01, FALSE) = 0.8998941257385102
pbinom(0,69,0.01, FALSE)  = 0.5001629701008011
pbinom(0,1,0.01, FALSE)   = 0.01

Answer 3

Observo que $229/0.01^{-1} \approx 3.36\times 10^{48}/\left(2^{-160}\right)^{-1}$, así que creo que @gammatester números. Lo que no creo es que tenemos que buscar $229\%$ del espacio de direcciones a ser sólo $90\%$ seguros de encontrar la dirección para la que buscamos.

(Más precisamente, $\log_2 3.365231884 \times 10^{48} = 161.203\dots$, $2.302\dots$- veces el tamaño de su espacio de direcciones.)

El proceso se describe con esta distribución binomial es randonly seleccionar una dirección, hacer pruebas, luego de colocarlo en la población de las direcciones que pueden ser recogidos en el futuro. Sustancialmente, un método más eficaz de forma secuencial de verificación de direcciones, lo que significa que estamos a $100\%$ seguro de haber encontrado la dirección después de la comprobación $100\%$ del espacio de direcciones. De hecho, estamos $1\%$ seguro de que después de la comprobación $1\%$ del espacio, $50\%$ después $50\%$, y así sucesivamente.

Answer 4

Para un $\text{bin}(n,p)$, $P(0\text{ successes}) = (1-p)^n$

Tener un $q= 0.01, 0.50$ $0.99$ de probabilidad de 1 o más éxitos que usted correspondientemente ha $1-q$ -- $0.99, 0.50$ $0.01$ de posibilidades de 0 éxitos (como complemento de las probabilidades de que el complementario del suceso).

Para $P(0\text{ successes}) = 1-q$ establecer $1-q = (1-p)^n$ o $n=\log(1-q)/\log(1-p)$ (para cualquier base de los registros que desee). Voy a trabajar con los naturales de los registros.

Ahora $\log(1-p)\approx -p = -2^{-160}$ (a un alto grado de precisión, por lo que tenemos $n\approx 2^{160}\log(\frac{1}{1-q})$.

Ahora para $q=0.01, 0.5$ y $0.99$, $\log(\frac{1}{1-q}) \approx 0.01005, 0.69315$ y $4.60517$

Más generalmente de muy pequeño $p$, usted necesita $n\approx \frac{1}{p}\log(\frac{1}{1-q})$. Usted puede intentar para decir $2^{-16}$, por lo que es razonablemente preciso; es mucho más precisa de muy pequeño $p$.

Para (calcular en R):

n <- (2^16)*log(1/(1-c(.01,.5,.99)))
> n
[1]    658.6588  45426.0936 301804.4333

(1-(2^-16))^n
[1] 0.989999924 0.499997356 0.009999649

o ya que no podemos tener $n$ fraccional, si queremos truncar:

(1-(2^-16))^trunc(n)
[1] 0.990009876 0.499998070 0.009999715

Estos dan esencialmente la $1-q$ valores que requiere.