Encontrar una moneda sesgada usando unos pocos lanzamientos de monedas

El siguiente problema surgió durante la investigación, y es sorprendentemente limpio:

Tienes una fuente de monedas. Cada moneda tiene un sesgo, es decir, una probabilidad de que caiga en "cabeza". Para cada moneda, independientemente, hay una probabilidad de 2/3 de que tenga un sesgo de al menos 0.9, y con el resto de la probabilidad su sesgo puede ser cualquier número en [0,1]. No sabes los prejuicios de las monedas. Todo lo que puede hacer en cualquier paso es lanzar una moneda y observar el resultado.

Para una n dada, su tarea es encontrar una moneda con sesgo de al menos 0.8 con probabilidad de al menos . ¿Puedes hacer eso usando solo lanzamientos de monedas O (n)? $1-\exp(-n)$

ds.algorithms pr.probability Dana Moshkovitz
fuente

Me parece muy improbable, ya que parece que se requieren lanzamientos de solo para determinar si una moneda dada es de alto sesgo o no con confianza . (También podemos suponer que cada moneda tiene un sesgo de o ). ¿Tiene algo mejor que ?

O (n)

$O(n)$

1 - \exp (- n)

$1-\exp(-n)$

0.9

$0.9$

0.8 - ϵ

$0.8-\epsilon$

O (n^{2})

$O(n^2)$

usul

No revisé las matemáticas, pero la siguiente idea parece prometedora: para cada moneda (en sucesión), haga la siguiente prueba. Elija un parámetro , diga y realice una caminata aleatoria en la línea usando la moneda. En cada paso , si la deriva desde es menor que , deseche la moneda. Las monedas con sesgo .9 deben pasar esta prueba con probabilidad constante, y las monedas que fallan deben fallar después de O (1) pasos en la expectativa, a excepción de las monedas con sesgo muy cercanas a . Elegir al azar entre y para cada moneda podría solucionar esto.

p

$p$

0.85

$0.85$

i

$i$

0

$0$

p \cdot i

$p \cdot i$

p

$p$

p

$p$

.84

$.84$

.86

$.86$

daniello

¿ estaría bien? ¿Conoces una solución con lanzamientos?

O (n \log n)

$O(n\log n)$

o (n^{2})

$o(n^2)$

Robin Kothari

Observación # 1: Si supiera que todas las monedas tienen un sesgo de al menos 0.9 o como máximo 0.8, habría sido posible encontrar una moneda con un sesgo de al menos 0.9 con probabilidad 1-exp (-n) usando lanzamientos de O (n) : toma una moneda, para i = 1,2,3, ..., tira la moneda por 2 ^ i veces y comprueba si la fracción de caras es al menos 0,89. Si no, reinicie con una nueva moneda. El lema clave: si se reinicia en la fase i, se lanzaron menos de 2 ^ {i + 1} monedas, y el problema es a lo sumo exp (- \ Omega (i)).

Dana Moshkovitz

Es bastante posible que los cambios de O (nlogn) sean necesarios y suficientes, pero aún no tenemos una prueba de eso.

Dana Moshkovitz

Respuestas:

El siguiente es un algoritmo de lanzamiento de bastante directo . $O(n \log n)$

Suponga que es la probabilidad de error a la que apuntamos. Supongamos que es una potencia de que se encuentra entre digamos y (solo algunas veces constantes lo suficientemente grandes como ). Mantenemos un candidato conjunto de monedas, . Inicialmente, ponemos monedas en . $1-\exp(-n)$ $N$ $2$ $100n$ $200n$ $n$ $C$ $N$ $C$

Ahora para , haga lo siguiente: Tire cada moneda en por veces (solo una constante lo suficientemente grande). Mantenga las monedas con la mayoría de las cabezas. $i=1,\dots,\log N$
$C$ $D_i = 2^i 10^{10}$
$N/2^i$

La prueba se basa en un par de límites de Chernoff. La idea principal es que tenemos la mitad del número de candidatos cada vez y, por lo tanto, podemos permitirnos el doble de lanzamientos de cada moneda.

Kasper Green Larsen
fuente

(1) Sería bueno escribir la prueba con más detalle: gran parte de la dificultad de este problema radica en dónde colocar el umbral para el límite de Chernoff (¿cuántas caras espera ver de las monedas de sesgo 0.9?) . (2) ¿Puedes demostrar que son necesarios los lanzamientos de monedas nlogn?

Dana Moshkovitz

La sutileza es esta: comienzas con n monedas, y excepto con un pequeño problema en n, hay al menos 0.6n monedas de sesgo 0.9. Ahora hay un problema constante de que las monedas con un sesgo de 0.9 pierden la competencia: 1 moneda con un sesgo menor a 0.8 (¡puede que caiga en la cabeza todo el tiempo!), 2 monedas con un sesgo de 0.8 + 1 / log, ..., n / 10 monedas con sesgo 0.9 - 1 / log n. Continúe de manera similar, donde el sesgo de las monedas elegidas se degrada con cada iteración, hasta que quede con la moneda de sesgo <0.8.

Dana Moshkovitz

Este es más o menos el algoritmo de eliminación mediana de Evan-Dar et. Alabama. Como lo muestran Mannor y Tsitsiklis en The Sample Complexity of Exploration in the Multi-Armed Bandit Problem, se puede usar para obtener el lanzamiento esperado de monedas cuando se conoce el sesgo objetivo en este caso.

O (n)

$O(n)$

Kristoffer Arnsfelt Hansen

Gracias por la referencia! Estoy interesado en el número máximo de lanzamientos de monedas que uno necesita, y para este caso muestran un límite inferior n ^ 2. Sin embargo, el problema que consideran es diferente al mío. Tienen n monedas, puede que solo haya una que esté más sesgada, y quieren encontrar una moneda con un sesgo similar. En mi configuración sé que hay al menos 0.6n monedas con sesgo aceptable (excepto con un problema exponencialmente pequeño en n).

Dana Moshkovitz

Supongo que los lanzamientos esperados de son fáciles para nuestro problema: comience con la primera moneda y haga lanzamientos para alguna gran constante en la notación . Si eso sale al menos veces, . De lo contrario, continúe con la próxima moneda. La probabilidad de corrección es y las monedas de entrada tienen un sesgo de 0.9 independientemente con la probabilidad , la probabilidad de alcanzar la -ésima moneda es menor que y, por lo tanto, la esperada el número de lanzamientos es .

O (n)

$O(n)$

m = Θ (n)

$m=\Theta(n)$

Θ (\cdot)

$\Theta(\cdot)$

0.85 m

$0.85m$

1 - \exp (- n)

$1-\exp(-n)$

2 / 3

$2/3$

i

$i$

(1 / 2)^{i}

$(1/2)^i$

\sum_{i = 0}^{\infty} m / 2^{i} = O (m) = O (n)

$\sum_{i=0}^\infty m/2^i = O(m) = O(n)$

Kasper Green Larsen