Нахождение смещенной монеты, используя несколько бросков монет

Следующая проблема возникла во время исследования, и она удивительно чиста:

У вас есть источник монет. Каждая монета имеет уклон, а именно вероятность того, что она упадет на «голову». Для каждой монеты независимо существует вероятность 2/3, что она имеет смещение не менее 0,9, а с остальной вероятностью ее смещение может быть любым числом в [0,1]. Вы не знаете предвзятости монет. Все, что вы можете сделать на любом этапе, это бросить монетку и понаблюдать за результатом.

Для данного n ваша задача состоит в том, чтобы найти монету с уклоном не менее 0,8 с вероятностью не менее . Вы можете сделать это, используя только O (n) бросков монет? $1-\exp(-n)$

ds.algorithms pr.probability Дана Мошковиц
источник

Мне кажется это очень маловероятным, поскольку броски , по-видимому, требуются только для определения того, является ли данная монета смещенной или нет с уверенностью . (Мы можем также предположить, что каждая монета имеет смещение либо либо .) У вас есть что-нибудь лучше, чем броски ?

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

усуль

Я не проверял математику, но следующая идея выглядит многообещающе: Для каждой монеты (подряд) сделайте следующий тест. Выберите параметр , скажем, и выполните случайное блуждание по линии, используя монету. На каждом шаге , если отклонение от меньше, чем , отбрасывают монету. Монеты со смещением .9 должны проходить этот тест с постоянной вероятностью, а провальные монеты должны потерпеть неудачу после O (1) шагов в ожидании, за исключением монет с уклоном, очень близким к . Выбор в случайном порядке между и для каждой монеты может исправить это.

p

$p$

0.85

$0.85$

i

$i$

0

$0$

p \cdot i

$p \cdot i$

p

$p$

p

$p$

.84

$.84$

.86

$.86$

Даниелло

Would будет в порядке? Вы знаете решение с бросками?

O (n \log n)

$O(n\log n)$

o (n^{2})

$o(n^2)$

Робин Котари

Наблюдение № 1: Если бы вы знали, что все монеты имеют смещение не менее 0,9 или не более 0,8, можно было бы найти монету с уклоном не менее 0,9 с вероятностью 1-exp (-n) с использованием бросков O (n) : возьмите монету, для i = 1,2,3, ..., подбросьте монету 2 ^ i раза и проверьте, составляет ли доля голов по крайней мере 0,89. Если нет, перезапустите с новой монетой. Ключевая лемма: если перезапустить на фазе i, то было меньше 2 ^ {i + 1} бросков монет, а проба не более exp (- \ Omega (i)).

Дана Мошковиц

Вполне возможно, что O (nlogn) броски необходимы и достаточны - но у нас пока нет доказательств этого.

Дана Мошковиц

Ответы:

Ниже приведен довольно простой алгоритм броска . $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$

Доказательство основано на паре оценок Чернова. Основная идея заключается в том, что мы каждый раз вдвое уменьшаем количество кандидатов и, следовательно, можем позволить себе в два раза больше бросков каждой монеты.

Каспер Грин Ларсен
источник

(1) Было бы неплохо записать доказательство более подробно - большая часть трудностей в этой задаче заключается в том, где разместить порог для границы Черноффа (сколько голов вы ожидаете увидеть из монет смещения 0,9?) , (2) Можете ли вы показать, что броски монет необходимы?

Дана Мошковиц

Тонкость заключается в следующем: вы начинаете с n монет, и, за исключением случаев, когда exp exp small, n, есть как минимум 0,6n монет с смещением 0,9. Теперь существует постоянная вероятность того, что монеты с смещением 0,9 проиграют конкурентам: 1 монета с смещением менее 0,8 (может случиться так, что она все время падает на голову!), 2 монеты с смещением 0,8 + 1 / logn, ..., n / 10 монет с уклоном 0,9 - 1 / log n. Продолжайте аналогичным образом, где смещение выбранных монет уменьшается с каждой итерацией, пока у вас не останется монета смещения <0,8.

Дана Мошковиц

O (n)

$O(n)$

Спасибо за ссылку! Меня интересует максимальное количество подбрасываемых монет, и в этом случае они показывают нижнюю границу n ^ 2. Однако проблема, которую они рассматривают, отличается от моей. У них есть n монет, может быть только одна, которая является наиболее предвзятой, и они хотят найти монету с аналогичным уклоном. В моей настройке я знаю, что есть как минимум 0,6n монет с допустимым смещением (за исключением случаев, когда экспоненциально мало по n).

Дана Мошковиц

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