¿Cómo generar una cantidad de no entero de los consecutivos éxitos de Bernoulli?

Question

Dado:

1. Una moneda con desconocidos sesgo $p$ (Cabeza).
2. Estrictamente positivo real $a > 0$.

Problema:

Generar un azar de la variable aleatoria de Bernoulli con la tendencia de $p^{a}$.

¿Alguien sabe cómo hacer esto? Por ejemplo, cuando se $a$ es un entero positivo, entonces uno puede voltear la moneda $a$ veces y ver si los resultados eran Cabezas: si son problema, a continuación, '0', de lo contrario tema '1'. La dificultad radica en el hecho de que $a$ no es necesariamente un entero. También, si yo sabía que el sesgo de $p$, yo podría crear otra moneda con la que desee sesgo.

Gracias de antemano!

Answer 1

Podemos resolver esto a través de un par de "trucos" y un poco de matemáticas.

Aquí es el algoritmo básico:

1. Generar una variable aleatoria Geométrica con probabilidad de éxito $p$.
2. El resultado de esta variable aleatoria que determina un fijo conocido el valor de $f_n \in [0,1]$.
3. Generar un $\mathrm{Ber}(f_n)$ variable aleatoria utilizando la feria de la moneda para decidir generados a partir de blockwise emparejado volteretas de nuestra $\mathrm{Ber}(p)$ moneda.
4. El resultado va a ser $\mathrm{Ber}(p^a)$ cualquier $a \in (0,1)$, que es todo lo que necesitamos.

Para hacer las cosas más fáciles de asimilar, vamos a romper cosas en pedazos.

Pieza 1: Sin pérdida de generalidad supongamos que $0 < a < 1$.

Si $a \geq 1$, entonces, podemos escribir $p^a = p^n p^b$ para algún entero positivo $n$ y algunos $0 \leq b < 1$. Pero, para cualquiera de los dos de Bernoulli independientes, tenemos $$\renewcommand{\Pr}{\mathbb P} \Pr(X_1 = X_2 = 1) = p_1 p_2 \>. $$ Podemos generar un $p^n$ de Bernoulli a partir de nuestra moneda en la manera obvia. Por lo tanto, sólo tenemos que ocuparnos de la generación de la $\mathrm{Ber}(p^a)$ al $a \in (0,1)$.

Pieza 2: Saber cómo generar un arbitrario $\mathrm{Ber}(q)$ fair coin flips.

No hay una manera estándar de hacer esto. Expandir $q = 0.q_1 q_2 q_3 \ldots$ en su binario de expansión y, a continuación, utilizar nuestra feria de la moneda gira para "igualar" los dígitos de $q$. El primer partido que se determina si declaramos un éxito ("cabeza") o el fracaso ("colas"). Si $q_n = 1$, y el tirón de la moneda es la cabeza, declarar cabezas, si $q_n = 0$, y el tirón de la moneda es de las colas, a declarar colas. De lo contrario, considere la posibilidad de la posterior dígitos en contra de un nuevo tirón de la moneda.

Pieza 3: Sepa cómo se generan una gran tirón de la moneda de lo injusto con desconocidos sesgo.

Esto se hace, asumiendo $p \in (0,1)$, por voltear la moneda en pares. Si conseguimos $HT$, declare la cabeza; si conseguimos $TH$, declara una de las colas, y en caso contrario, repetir el experimento hasta que uno de los dos anteriores resultados se produce. Son igualmente probables, por lo que debe tener la probabilidad de $1/2$.

Pieza 4: Algunos de matemáticas. (Taylor para el rescate.)

Mediante la expansión de $h(p) = p^a$$p_0 = 1$, Taylor teorema afirma que $$ p^a = 1 - (1-p) - \frac{a(1-a)}{2!} (1-p)^2 - \frac{a(1-a)(2-a)}{3!} (1-p)^3 \cdots \>. $$ Tenga en cuenta que debido a $0 < a < 1$, cada término después del primero es negativo, por lo que tenemos $$ p^a = 1 - \sum_{n=1}^\infty b_n (1-p)^n \>, $$ donde $0 \leq b_n \leq 1$ son conocidos a priori. Por lo tanto $$ 1 - p^a = \sum_{n=1}^{\infty} b_n (1-p)^n = \sum_{n=1}^\infty b_n \Pr(G \geq n) = \sum_{n=1}^\infty f_n \Pr(G = n) = \mathbb E f(G), $$ donde $G \sim \mathrm{Geom}(p)$, $f_0 = 0$ y $f_n = \sum_{k=1}^n b_k$$n \geq 1$.

Y, ya sabemos cómo utilizar nuestra moneda para generar una variable aleatoria Geométrica con probabilidad de éxito $p$.

Pieza 5: simulación Monte Carlo para el truco.

Deje $X$ ser un discreto de la variable aleatoria toma valores en $[0,1]$$\Pr(X = x_n) = p_n$. Deje $U \mid X \sim \mathrm{Ber}(X)$. Entonces $$ \Pr(U = 1) = \sum_n x_n p_n. $$

Pero, teniendo en $p_n = p(1-p)^n$$x_n = f_n$, vemos ahora cómo generar un $\mathrm{Ber}(1-p^a)$ variable aleatoria y esto es equivalente a la generación de una $\mathrm{Ber}(p^a)$.

Answer 2

¿La siguiente respuesta es tonta?

Si $X_1,\dots,X_n$ son independiente $\mathrm{Ber}(p)$ $Y_n$ tiene distribución $\mathrm{Ber}\left(\left(\sum_{i=1}^n X_i/n \right)^a\right)$, y se distribuirán aproximadamente $Y_n$ $\mathrm{Ber}(p^a)$, cuando $n\to\infty$.

Por lo tanto, si no sabes $p$, pero usted puede lanzar esta moneda muchas de las veces, es posible de la muestra (aproximadamente) de una variable de aleatoria $\mathrm{Ber}(p^a)$.

Ejemplo R código:

n <- 1000000
p <- 1/3 # works for any 0 <= p <= 1
a <- 4
x <- rbinom(n, 1, p)
y <- rbinom(n, 1, mean(x)^a)
cat("p^a =", p^a, "\n")
cat("est =", mean(y))

Resultados:

p^a = 0.01234568 
est = 0.012291 

Answer 3

He publicado la siguiente exposición de esta cuestión, y el cardenal de la respuesta a la Discusión General del foro de la corriente Analítica de la Combinatoria de clase en Coursera, "Aplicación de potencia de la serie a la construcción de una variable aleatoria." Estoy publicando una copia aquí como wiki de la comunidad para hacer esto públicamente y de manera más permanente disponible.

---

Hay una interesante pregunta y respuesta en stat.stackexchange.com en relación con el poder de la serie: "Cómo generar un no-entero cantidad de consecutivos de Bernoulli éxitos?" Voy a parafrasear la pregunta y la respuesta del cardenal.

Supongamos que tenemos una posibilidad de injusto de la moneda que es la cabeza con probabilidad de $p$, y un número real positivo $\alpha$. Cómo podemos construir un evento cuya probabilidad es $p^\alpha$?

Si $\alpha$ fueron un entero positivo, podríamos disponer de la moneda $\alpha$ veces y dejar que el evento sea que todos los tiros de la cabeza. Sin embargo, si $\alpha$ no es un número entero, decir $1/2$, entonces esto no tiene sentido, pero podemos utilizar esta idea para reducir para el caso de que $0 \lt \alpha \lt 1$. Si queremos construir un evento cuya probabilidad es $p^{3.5}$, tomamos la intersección de sucesos independientes cuyas probabilidades se $p^3$$p^{0.5}$.

Una cosa que podemos hacer es construir un evento con algún conocido probabilidad de $p' \in [0,1]$. Para ello, se puede construir una secuencia de la feria de bits repetidamente de darle la vuelta a la moneda dos veces, la lectura de $HT$$1$$TH$$0$, e ignorando $HH$$TT$. Podemos comparar esta secuencia con el binario de expansión de $p' = 0.a_1a_2a_3..._2$. En el caso de que el primer desacuerdo es donde $a_i=1$ probabilidad de $p'$. No sabemos $p^\alpha$, por lo que no podemos utilizar directamente, pero va a ser una herramienta útil.

La idea principal es que nos gustaría utilizar el poder de la serie para $p^\alpha = (1-q)^\alpha = 1 - \alpha q - \frac{\alpha(1-\alpha)}{2} q^2 - \frac{\alpha (1-\alpha)(2-\alpha)}{3!}q^3 -...$ donde $p=1-q$. Podemos construir los acontecimientos cuyas probabilidades se $q^n$ por voltear la moneda $n$ veces y ver si están todos de las colas, y podemos producir un evento con una probabilidad de $p' q^n$ mediante la comparación de los dígitos binarios de $p'$, con una feria de flujo de bits como la de arriba y la de comprobar si $n$ lanzamientos son todas las colas.

Construir una variable aleatoria geométrica $G$ con el parámetro $p$. Este es el número de colas antes de la primera cabeza en una secuencia infinita de lanzar una moneda. $P(G=n) = (1-p)^np = q^n p$. (Algunas personas usan una definición que difiere por $1$.)

Dada una secuencia $t_0, t_1, t_2, ...$, podemos producir $t_G$: dar la vuelta a la moneda hasta el primer jefe, y si hay $G$ colas antes de la primera cabeza, tomar el elemento de la secuencia de índice $G$. Si cada una de las $t_n \in [0,1]$, se puede comparar a $t_G$ con un uniforme de la variable aleatoria en $[0,1]$ (construido como el anterior) para llegar a un evento con una probabilidad de $E[t_G] = \sum_n t_n P(G=n) = \sum_n t_n q^n p $.

Esto es casi lo tenemos. Nos gustaría eliminar ese $p$ usar el poder de la serie para$p^\alpha$$q$.

$$1 = p + qp + q^2p + q^3p + ...$$

$$q^n = q^np + q^{n+1}p + q^{n+2}p + ...$$

$$\begin{eqnarray} \sum_n s_n q^n & = & \sum_n s_n (q^n p + q^{n+1}p + q^{n+2}p + ...) \newline & = & \sum_n (s_0 + s_1 + ... + s_n) q^n p \end{eqnarray}$$

Considere la posibilidad de $1-p^\alpha = \alpha q + \frac{\alpha(1-\alpha)}{2} q^2 + ... $. Deje $t_n$ la suma de los coeficientes de $q$ a través de $q^n$. A continuación,$1-p^\alpha = \sum_n t_n q^n p$. Cada una de las $t_n\in [0,1]$ ya que los coeficientes son positivos y la suma de $1-0^\alpha = 1$, por lo que se puede construir un evento con una probabilidad de $1-p^\alpha$ mediante la comparación de una feria de flujo de bits con el binario de expansión de $t_G$. El complemento tiene probabilidad de $p^\alpha$ como se requiere.

---

De nuevo, el argumento es debido a cardenal.

Answer 4

La muy completa respuesta por el cardenal y contribuciones posteriores inspiró el siguiente comentario/variante.

Vamos a PZ stand "Probabilidad de Cero" y $q:=1-p$. Si $X_n$ es un iid secuencia de Bernoulli con PZ $q$, luego $M_n := \max(X_1,\,X_2,\,\dots, X_n)$ es una de Bernoulli r.v. con PZ $q^n$. Ahora a hacer $n$ aleatorios, es decir, la sustitución por un número entero de rv $N \geq 1$ leads to Bernoulli rv $M_N$ con $$ \mathrm{Pr}\{M_N =0\} = \sum_{n=1}^\infty \mathrm{Pr}\{M_N =0 \,\vert\, N =n\} \mathrm{Pr}\{N =n\} = \sum_{n=1}^\infty \mathrm{Pr}\{N =n\} \, q^n. $$ Así que si $0 < a < 1$ y si tomamos $\mathrm{Pr}\{N =n\} =b_n$ a partir de cardenal's respuesta, nos encontramos con $\mathrm{Pr}\{M_N =0\} = 1- p^a$ $1-M_N$ es $\mathrm{Ber}(p^a)$ como quería. Este es de hecho posible, ya que el los coeficientes de $b_n$ satisfacer $b_n \geqslant 0$ y se suma a $1$.

La distribución discreta de $N$ sólo depende de $a$$0 < a < 1$, recordar $$ \mathrm{Pr}\{N =n\} = \frac{a}{n}\,\prod_{k=1}^{n-1}\left(1 - a/k\right) \qquad (n \geq 1). $$ Tiene características interesantes. Resulta que tengo un infinito expectativa y una pesada cola comportamiento de $n \,b_n \sim c/n^a$ con $c = -1/\Gamma(-a) >0$.

A pesar de $M_N$ es el máximo de $N$ rvs, su determinación de las necesidades de un número de $X_k$ $\leq N$ ya que el resultado es conocido, tan pronto como una $X_k$$1$. El número de la $X_k$ es geométricamente distribuido.