Maximizar esperadas cabezas con monedas sesgadas.

Question

Decir que tengo n sesgada monedas. Moneda de $i$ tierras en la cabeza con una probabilidad de $p_i$, que proviene de un uniforme antes de la distribución de probabilidad sobre $[0, 1]$. A veces $t = 1, 2, ..., k$ I debe seleccionar una de las monedas a la vuelta (Suponga que k > n). Cuál es la estrategia daría un máximo de espera número de cabezas en el k volteretas?

Este problema parece tan engañosamente simple... obviamente, Se necesita hacer algunos trade-off entre voltear la moneda que ha dado el mejor rendimiento hasta ahora y probar otros a ver si están mejor. No estoy seguro de cómo hacerlo.

Answer 1

Use el algoritmo de pesos multiplicativos (también conocido como mayoría ponderada, aumento [en aprendizaje automático], y probablemente otros nombres también). Vea esta conferencia, por ejemplo, la sección 2.