Producir un resultado con una probabilidad determinada mediante el lanzamiento de una moneda justa

Question

"Introducción al algoritmo" C.2-6

Describa un procedimiento que tome como entrada dos enteros a y b tales que $0 < a < b$ y, utilizando lanzamientos de moneda justos, produce como salida caras con probabilidad $a / b$ y las colas con probabilidad $(b - a) /b$ . Dar un límite en el número esperado de lanzamientos de monedas, que debería ser O(1) (Pista: Representar a/b en binario.)

Mi opinión es que podemos utilizar la cabeza para representar el bit 0 y la cola para el bit 1. Entonces, al voltear $m = \lceil \log_2 b \rceil$ veces, obtenemos un $m$ número basado en el binario de bits $x$ . Si $ x \ge b $ entonces dejamos caer x y volvemos a hacer el experimento, hasta que podamos un $ x < b$ . Esta x tiene una probabilidad $P\{ x < a\} = \frac a b$ y $P\{ a \le x < a\} = \frac {b - a} b$

Pero no estoy muy seguro de que mi solución sea la que pide la pregunta. ¿Estoy en lo cierto?

---

Editar,

Creo que Michael y TonyK dieron el algoritmo correcto, pero Michael explicó la razón detrás del algoritmo.

Las 3 preguntas que hizo:

• mostrar que este proceso requiere c lanzamientos de moneda, en la expectativa, para alguna constante c;

La expectativa de c, el número de tiradas, como señaló TonyK, es 2.

• muestran que usted grita "¡NO!" con una probabilidad de 2/3;

P(gritar "¡NO!") = P("la moneda sale cruz en un lanzamiento impar") = $ \sum_{k=1}^\infty (\frac 1 2)^ k = \frac 2 3$

• explique cómo generalizaría a otros números racionales, con la misma constante c

Es el algoritmo dado por TonyK. Podemos reformularlo así

Representar a/b en binario. Definir $f(Head) = 0$ y $f(Tail) = 1$ . Si

f(resultado del n-ésimo flip) = "n-ésimo bit de a/b"

y luego terminamos. Si la última tirada es Cabeza, gritamos "Sí", de lo contrario "No".

Tenemos $ P \{Yes\} = \sum_{i\in I}(1/2)^i = \frac a b $ donde I representa el conjunto de índices donde la expresión binaria de a/b es 1.

Answer 1

Expreso $a/b$ en binario. Entonces, en el $n$ de la tirada, continúa si la tirada coincide con el bit $n$ de $a/b$ ; en caso contrario, termina, con el resultado "cara" si el $n$ El lanzamiento fue $0$ y "colas" si el $n$ El lanzamiento fue $1$ .

En cada lanzamiento, la probabilidad de terminar es $1/2$ . Así que el número esperado de lanzamientos es $$\sum_{r=1}^\infty \frac{r}{2^r} = 2$$ Podemos hacerlo un poco mejor si la expansión binaria termina, porque podemos detener el procedimiento después del último bit distinto de cero (la probabilidad de lanzar posteriormente una secuencia infinita de ceros es $0$ ).

Answer 2

El caso más sencillo no trivial es $a = 1, b = 3$ -- así que queremos lanzar monedas justas, observar si salen cara o cruz, y en algún momento gritar "¡SÍ!" o "¡NO!". Queremos gritar "¡SÍ!" con probabilidad $1/3$ y queremos que termine en una cantidad de tiempo que tenga una expectativa finita.

Digamos que obtenemos una cola en el primer lanzamiento. Entonces gritaremos "¡NO!"; esto significa que la mitad de las veces gritamos "¡NO!" después de un lanzamiento. La mitad de las veces aún no hemos dicho nada; en dos tercios de esta mitad de las veces queremos gritar "¡SÍ!", y el resto de las veces queremos gritar "¡NO!".

Así que si obtenemos (una cola en el primer lanzamiento y) una cabeza en el segundo lanzamiento queremos gritar "¡SÍ!". Ahora hemos gritado "¡NO!" en un lanzamiento con probabilidad $1/2$ y "¡SÍ!" en dos lanzamientos $1/4$ del tiempo. Para conseguir un tercio de "¡Si!" tenemos que gritar "¡Si!" $1/3$ de los restantes $1/4$ del tiempo.

Pero ya sabemos cómo hacerlo... gritar "¡NO!" si la moneda sale cruz en el tercer lanzamiento, "¡SÍ!" si sale cara en el cuarto lanzamiento, y así sucesivamente.

Así que en este caso se lanzan las monedas repetidamente, y se espera hasta que la moneda salga cruz en un lanzamiento impar - en cuyo caso se grita "¡NO!" - o cara en un lanzamiento par - en cuyo caso se grita "¡SÍ!". Te lo dejo a ti:

• muestran que este proceso requiere $c$ lanzamientos de moneda, en expectativa, para alguna constante $c$ ;
• demostrar que se grita "¡NO!" con probabilidad $2/3$ ;
• explicar cómo se generalizaría a otros números racionales, con la mismo constante $c$ .

Answer 3

Aquí está mi pensamiento de entender las soluciones de Michael y TonyK.

• $0 \lt a \lt b$ , lo que significa que $0 \lt {\frac ab} \lt 1$ Así que $\frac ab$ puede representarse mediante una fracción binaria infinita con la forma $0.b_1b_2...b_{j-1}b_jb_{j+1}b_{j+2}$ (añade el final $0$ s, cuando $\frac ab$ es una fracción binaria finita). Lanzar una moneda infinitas veces puede representar una fracción binaria entre $0$ y $1$ , como $0.{flip_1}{flip_2}...{flip_i}...$ uno por uno, correspondientemente. Ahora, la probabilidad de la fracción de volteo $0.{flip_1}{flip_2}...{flip_i}...$ menos de una fracción $\frac ab$ es $\frac ab$ y mayor que la fracción $\frac ab$ es $\frac {b-a} {b}$ , para distribución de probabilidad uniforme continua .
• Sin embargo, , lanzar una moneda infinitas veces es imposible y lo que queremos es el relación si esa cadena infinita $0.{flip_1}{flip_2}...{flip_i}...$ es menor o mayor que $\frac ab$ . podemos predecir la relación menor o mayor que cuando se produjo el primer lanzamiento no coincidente , porque cualquier $0.b_1b_2...b_{j-1}\mathbf0x_{j+1}x_{j+2}...$ es menor que $0.b_1b_2...b_{j-1}\mathbf1b_{j+1}b_{j+2}...$ cuando $b_j = 1$ y cualquier $0.b_1b_2...b_{j-1}\mathbf1x_{j+1}x_{j+2}...$ es mayor que $0.b_1b_2...b_{j-1}\mathbf0b_{j+1}b_{j+2}....$ cuando $b_j = 0$ .

Answer 4

Básicamente, lo que Michael dice que es así:

Expresamos a/b utilizando, por ejemplo, 64 dígitos binarios.

Ahora, lanza 64 monedas. Representa el resultado de esto como un binario usando cabeza=1 y cola=0.

La mejor aproximación del problema es:

• Si este número es mayor que la representación binaria de 64 bits de a/b entonces diga "HEAD".
• Si este número es menor que la representación binaria de 64 bits representación binaria de a/b entonces diga "TAILS".

Espero tener razón.