Menemukan koin bias menggunakan beberapa lemparan koin

Masalah berikut muncul selama penelitian, dan ternyata sangat bersih:

Anda memiliki sumber koin. Setiap koin memiliki bias, yaitu probabilitas bahwa koin itu jatuh di atas "kepala". Untuk setiap koin secara mandiri ada probabilitas 2/3 bahwa ia memiliki bias setidaknya 0,9, dan dengan sisa probabilitas biasnya dapat berupa angka dalam [0,1]. Anda tidak tahu bias dari koin. Yang bisa Anda lakukan pada langkah apa pun adalah melempar koin dan mengamati hasilnya.

Untuk n tertentu, tugas Anda adalah menemukan koin dengan bias setidaknya 0,8 dengan probabilitas minimal . Bisakah Anda melakukannya dengan hanya menggunakan lemparan koin O (n)? $1-\exp(-n)$

ds.algorithms pr.probability Dana Moshkovitz
sumber

Sepertinya sangat tidak mungkin bagi saya, karena

lemparan tampaknya diperlukan hanya untuk menentukan apakah koin yang diberikan memiliki bias tinggi atau tidak dengan keyakinan

. (Kita juga dapat mengasumsikan bahwa setiap koin memiliki bias

atau

.) Apakah Anda memiliki sesuatu yang lebih baik daripada lemparan

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

Saya tidak memeriksa matematika, tetapi ide berikut ini tampak menjanjikan: Untuk setiap koin (berturut-turut) lakukan tes berikut. Pilih parameter

, ucapkan

dan lakukan jalan acak di jalur menggunakan koin. Pada setiap langkah

, jika penyimpangan jauh dari

kurang dari

, buang koin. Koin dengan bias 0,9 harus lulus tes ini dengan probabilitas konstan, dan koin gagal harus gagal setelah O (1) langkah-langkah dalam harapan, kecuali untuk koin dengan bias sangat dekat dengan

. Memilih

secara acak antara

dan

untuk setiap koin dapat memperbaikinya.

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

Apakah

baik-baik saja? Apakah Anda tahu solusi dengan

lemparan?

O (n \log n)

$O(n\log n)$

o (n^{2})

$o(n^2)$

Robin Kothari

Pengamatan # 1: Jika Anda tahu bahwa semua koin memiliki bias setidaknya 0,9 atau paling banyak 0,8, akan mungkin untuk menemukan koin dengan bias setidaknya 0,9 dengan probabilitas 1-exp (-n) menggunakan O (n) lemparan : ambil koin, untuk i = 1,2,3, ..., lempar koin itu sebanyak 2 ^ i kali dan periksa apakah fraksi kepala paling tidak 0,89. Jika tidak, mulai lagi dengan koin baru. Kunci lemma: jika memulai kembali pada fase i, maka lemparan koin kurang dari 2 ^ {i + 1}, dan masalahnya paling banyak exp (- \ Omega (i)).

Dana Moshkovitz

Sangat mungkin bahwa O (nlogn) membalik diperlukan dan cukup - tetapi kami belum memiliki bukti untuk itu.

Dana Moshkovitz

Jawaban:

Berikut ini adalah algoritma undian $O(n \log n)$ agak mudah .

Asumsikan $1-\exp(-n)$ adalah probabilitas kesalahan yang kami tuju. Misalkan $N$ adalah kekuatan $2$ yaitu antara katakanlah $100n$ dan $200n$ (hanya beberapa waktu konstan yang cukup besar $n$ ). Kami mempertahankan satu set calon koin, $C$ . Awalnya, kami menempatkan $N$ koin di $C$ .

Sekarang untuk $i=1,\dots,\log N$ , lakukan yang berikut:
Aduk setiap koin dalam $C$ untuk $D_i = 2^i 10^{10}$ kali (hanya beberapa konstanta yang cukup besar).
Simpan koin $N/2^i$ dengan kepala terbanyak.

Buktinya didasarkan pada beberapa batasan Chernoff. Gagasan utama adalah bahwa kami setengah dari jumlah kandidat setiap kali dan dengan demikian mampu membayar dua kali lebih banyak dari setiap koin.

Kasper Green Larsen
sumber

(1) Akan menyenangkan untuk menuliskan buktinya secara lebih rinci - sebagian besar kesulitan dalam masalah ini adalah di mana menempatkan ambang batas untuk ikatan Chernoff (berapa banyak kepala yang Anda harapkan untuk dilihat dari koin bias 0,9?) . (2) Dapatkah Anda menunjukkan bahwa lemparan koin nlogn diperlukan?

Dana Moshkovitz

Kehalusannya adalah ini: Anda mulai dengan n koin, dan kecuali dengan prob exp kecil dalam n, setidaknya ada 0,6n koin bias 0,9. Sekarang ada kemungkinan konstan bahwa koin bias 0,9 kehilangan persaingan menjadi: 1 koin dengan bias kurang dari 0,8 (mungkin terjadi jatuh di kepala sepanjang waktu!), 2 koin dengan bias 0,8 + 1 / logn, ..., n / 10 koin dengan bias 0,9 - 1 / log n. Lanjutkan dengan cara yang sama, di mana bias dari koin yang dipilih menurun dengan setiap iterasi, sampai Anda tersisa dengan koin bias <0,8.

Dana Moshkovitz

O (n)

$O(n)$

Terima kasih untuk referensi! Saya tertarik pada jumlah maksimum lemparan koin yang dibutuhkan seseorang, dan untuk kasus ini mereka menunjukkan batas bawah n ^ 2. Namun, masalah yang mereka anggap berbeda dengan saya. Mereka memiliki n koin, mungkin hanya ada satu yang paling bias, dan mereka ingin menemukan koin dengan bias yang sama. Dalam pengaturan saya, saya tahu bahwa setidaknya ada koin 0.6n dengan bias yang dapat diterima (kecuali dengan probabilitas kecil secara eksponensial dalam 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)$