Convertir una moneda sesgada en un Unbiased uno determinista

Question

No determinista Algoritmo Exacto

No es un simple algoritmo para convertir una visión sesgada de la moneda en una justa:

1. Voltear la moneda dos veces.
2. Identificar HT con H y TH con T.
3. Descartar los casos de HH y TT.

Este algoritmo produce una perfección de la feria de la moneda, pero no es determinista.

Determinista Aproximación

También sé que es posible aproximado de una moneda con un algoritmo determinista:

Deje $C_0$ ser el sesgada de la moneda y definir $C_1$ por voltear $C_0$ dos veces. $C_1$ es H si $C_0$ fue HH o TT, y $C_1$ es T si $C_0$ fue HT o TH.

Podemos ver que si la probabilidad de que $C_0$ fue cabezas es $p$, entonces la probabilidad de que $C_1$ es mano a mano es $p_1 = 1 - 2p(1 - p)$. Esta es una parábola que conecta $(0,1), (.5,.5)$, e $(1,1)$ y podemos ver que, si asumimos $0<p<1$ entonces la función tiene un punto fijo en $0.5$. Desde $0.5 < p_1 < p$ si $p>0.5$ e $0.5<p_1<1$ si $p<0.5$, entonces podemos ver que un punto fijo de la iteración con $0<p<1$ siempre convergen a $0.5$. Por lo tanto, podemos encontrar un determinista $C_i$ que es arbitrariamente de la feria (definido por voltear $C_{i-1}$ dos veces).

Mi Problema

Estoy tratando de averiguar si, teniendo en cuenta algunas sesgada de la moneda con rational probabilidad de cabezas $p$, se puede construir un algoritmo para resolver este problema que es determinista y exacta. ¿Alguien tiene algún conocimiento?

(Tenga en cuenta que el algoritmo sólo tiene que trabajar para una probabilidad fija $p$, ya que, como se señaló en los comentarios y la respuesta, hay algunos $p$, por ejemplo, $p = 1/3$ para los que no existe tal algoritmo.)

Answer 1

Un algoritmo que funciona para cualquier $p$ no existe. Es posible resolver el problema para algunos $p$.

Deje $p$ ser la probabilidad de cabezas.

Considere la posibilidad de un algoritmo determinista $F$ que utiliza $n$ lanzamientos. Denotar $A$ el conjunto de todas las posibles secuencias de $n$ lanzar una moneda ($|A| = 2^n$). El $F$ es esencialmente una función de $F: A \to \{0, 1\}$, que devuelve 0 (cabezas) para algunas secuencias de $n$ lanzamientos, y 1 (colas) para el resto.

Nuestro algoritmo determinista define dos conjuntos, $H = \{v \in A | F(v) = 0\}$ - el conjunto de $n$sacudida de secuencias, donde algoritmo decidió cabezas, y $T = A \setminus H$, de tal manera que $\mathbb{P}[H] = \mathbb{P}[T] = 0.5$.

Por otro lado, para cualquier secuencia $v \in A$ denotar $h(v)$ el número de colas en $v$. $$\mathbb{P}[H] = \sum_{v \in H}\mathbb{P}[v] = \sum_{v \in H} p^{h(v)}(1-p)^{n - h(v)} {\hspace{2cm}} [1]$$

Tenemos que hacer que esto $\frac{1}{2}$.

Deje $p = \frac{r}{q}$ cuando está completamente reducida. Entonces $$p^{h(v)}(1-p)^{n - h(v)} = \frac{r^{h(v)}(q-r)^{n-h(v)}}{q^n}$$

Vamos a contar cuántas veces cada posible valor de $h(v)$ aparece en el sum [1]:

Denotar $c_k = |\{v | v \in H \text{ and } h(v)=k \}|$. [1] se convierte en

$$\mathbb{P}[H] = \sum_{k=0}^n c_k \frac{r^{k}(q-r)^{n-k}}{q^n} = \frac{\sum_{k=0}^n c_k r^{k}(q-r)^{n-k}}{q^n} = \frac{1}{2}$$

Un algoritmo que funciona para todos los $p$ no existe, porque si $q$ es impar, no hay manera de introducir un factor de $2$ en el denominador de esta expresión. Lo mejor que podemos hacer es, dada una $p$, trate de encontrar un algoritmo que funciona para ese $p$, o determinar que no existe.

Desde allí se $n \choose k$ secuencias de lanzar una moneda con la longitud de la $n$ e $k$ cabezas, también necesitamos $c_k \leq {n \choose k}$.

Si $q$ es aún, y tenemos una solución a la siguiente ecuación, la satisfacción de los límites en las $c_k$ $$\sum_{k=0}^n c_k r^{k}(q-r)^{n-k} = \frac{q^n}{2}$$

Entonces, simplemente puede incluir $c_k$ secuencias que contengan $k$ cabezas en $H$ por cada $k$ conseguir nuestro algoritmo.

Tenga en cuenta que esta ecuación tiene un número finito de posibles soluciones, por lo que simplemente puede tratar a todos ellos.