Encontrar uma moeda tendenciosa usando alguns lançamentos

O seguinte problema surgiu durante a pesquisa e é surpreendentemente limpo:

Você tem uma fonte de moedas. Cada moeda tem um viés, ou seja, uma probabilidade de cair na "cabeça". Para cada moeda independentemente, existe uma probabilidade 2/3 de ter uma tendência pelo menos 0,9 e, com o resto da probabilidade, sua tendência pode ser qualquer número em [0,1]. Você não conhece os preconceitos das moedas. Tudo o que você pode fazer a qualquer momento é lançar uma moeda e observar o resultado.

Para um dado n, sua tarefa é encontrar uma moeda com viés de pelo menos 0,8 com probabilidade de pelo menos . Você pode fazer isso usando apenas O (n) sorteios? $1-\exp(-n)$

ds.algorithms pr.probability Dana Moshkovitz
fonte

Parece-me muito improvável, uma vez que

joga parece ser necessário apenas para determinar se uma determinada moeda tem um viés alto ou não com confiança

. (Podemos também supor que cada moeda tenha um viés de

.) Você tem algo melhor do que

lançamento de

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

Não verifiquei a matemática, mas a seguinte idéia parece promissora: Para cada moeda (em sucessão), faça o seguinte teste. Escolha um parâmetro

, diga

e faça uma caminhada aleatória na linha usando a moeda. A cada passo

, se o desvio de

for menor que

, descarte a moeda. Moedas com viés .9 devem passar neste teste com probabilidade constante, e moedas com falha devem falhar após O (1) passos na expectativa, exceto para as moedas com viés muito próximas de

. Escolher

aleatoriamente entre

para cada moeda pode corrigir isso.

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 23/06

Será que

ficar bem? Você conhece uma solução com

arremessos?

O (n \log n)

$O(n\log n)$

o (n^{2})

$o(n^2)$

precisa

Observação nº 1: se você soubesse que todas as moedas possuem viés de pelo menos 0,9 ou no máximo 0,8, seria possível encontrar uma moeda com viés de pelo menos 0,9 com probabilidade 1-exp (-n) usando lançamentos de O (n) : pegue uma moeda, pois i = 1,2,3, ..., jogue a moeda por 2 ^ i vezes e verifique se a fração de cabeças é pelo menos 0,89. Caso contrário, reinicie com uma nova moeda. O lema principal: se reiniciar na fase i, ocorrerá menos que 2 ^ {i + 1} lançamentos de moedas, e o prob será no máximo exp (- \ Omega (i)).

Dana Moshkovitz

É bem possível que O (nlogn) flips sejam necessários e suficientes - mas ainda não temos uma prova disso.

Dana Moshkovitz

Respostas:

$O(n \log n)$

$1-\exp(-n)$ $N$ $2$ $100n$ $200n$ $n$ $C$ $N$ $C$

$i=1,\dots,\log N$
$C$ $D_i = 2^i 10^{10}$
$N/2^i$

A prova é baseada em alguns limites de Chernoff. A idéia principal é que tenhamos metade do número de candidatos de cada vez e, portanto, possamos pagar o dobro do número de lançamentos de cada moeda.

Kasper Green Larsen
fonte

(1) Seria bom anotar a prova com mais detalhes - grande parte da dificuldade desse problema está em onde colocar o limite para o limite de Chernoff (quantas cabeças você espera ver das moedas de 0,9 de viés?) . (2) Você pode mostrar que são necessários lançamentos de moedas nlogn?

Dana Moshkovitz

A sutileza é a seguinte: você começa com n moedas e, exceto com prob exp pequeno em n, há pelo menos 0,6n moedas de viés 0,9. Agora há um problema constante de que as moedas de 0,9 de viés perdem a competição para: 1 moeda com viés menor que 0,8 (pode cair sempre na cabeça!), 2 moedas com viés de 0,8 + 1 / logn, ..., n / 10 moedas com viés 0,9 - 1 / log n. Continue de maneira semelhante, onde o viés das moedas escolhidas diminui a cada iteração, até você ficar com a moeda do viés <0,8.

Dana Moshkovitz

O (n)

$O(n)$

Obrigado pela referência! Estou interessado no número máximo de lançamentos de moedas de que precisamos e, nesse caso, eles mostram um limite inferior de n ^ 2. No entanto, o problema que eles consideram é diferente do meu. Eles têm n moedas, pode haver apenas um que seja mais tendencioso e desejam encontrar uma moeda com um viés semelhante. Na minha configuração, eu sei que existem pelo menos 0,6n moedas com viés aceitável (exceto com prob exponencialmente pequeno em n).

Dana Moshkovitz

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)$