Pertimbangkan masalah set-persimpangan: Alice dan Bob masing-masing mendapatkan subset dari , dan mereka ingin tahu apakah set mereka berpotongan. Ini adalah masalah kanonik dari kompleksitas komunikasi, dan diketahui bahwa protokol acak untuk masalah ini memerlukan bit komunikasi ( lihat survei di sini ). Dalam kasus di mana set berukuran untuk , diketahui bahwa protokol acak membutuhkan bit ( lihat di sini ).
Pertimbangkan sekarang varian di mana Alice dan Bob ingin tahu ukuran persimpangan set mereka. Jelas, menghitung ukuran yang tepat akan mengurangi masalah set-persimpangan standar, dan ini berlaku bahkan jika mereka hanya ingin menghitung perkiraan multiplikasi ukuran. Namun, apa yang terjadi jika mereka ingin menghitung perkiraan tambahan ukuran persimpangan? Apakah ada batas bawah atau batas atas yang diketahui tentang masalah ini?
Saya sangat tertarik dengan pertanyaan ini dalam pengaturan set kecil, yaitu, kasus di mana set adalah ukuran .
sumber
Jawaban:
Saya akan memberikan dua batas atas. Biarkan dan B menjadi set yang diberikan masing-masing untuk Alice dan Bob, dan beri a = | A | , b = | B | , c = | A ∩ B | .A B a=|A| b=|B| c=|A∩B|
Pertama, ada protokol acak yang, diberikan dan ϵ > 0 , menghitung dengan probabilitas ≥ 1 - ϵ perkiraan c hingga kesalahan aditif d , menggunakan O ( ( min { a , b }d>0 ϵ>0 ≥1−ϵ c d bit komunikasi, danO((min{a,b}O((min{a,b}d)2lognlogϵ−1) bit keacakan.O((min{a,b}d)2logmin{a,b}logϵ−1)
Protokolnya sebagai berikut:
Jika , pihak yang melihatnya mengakhiri protokol dan menghasilkan 0 sebagai estimasi. Jika tidak, Alice dan Bob berkomunikasi a dan b satu sama lain, dan menentukan mana yang lebih kecil. Aku akan menganggap di bawah wlog bahwa sebuah ≤ b .d≥min{a,b} 0 a b a≤b
Alice menggambar sampel acak seragam independen a i ∈ A , i < t , dan mengirimkannya ke Bob.t=log(2ϵ−1)a2/(2d2) ai∈A i<t
Bob memperkirakan sebagai ac .at|{i<t:ai∈B}|
Protokol adalah benar dengan batas-batas Chernoff-Hoeffding: jika menunjukkan indikator variabel acak acara yang saya ∈ B , maka X i , i < t , adalah variabel iid dengan mean p = c / a . Jadi, Pr [ a ¯ X ≤ c - d ] = Pr [ ¯ X ≤ p - dXi ai∈B Xi i<t p=c/a
dan juga untukPr[a ¯ X ≥c+d].
Sekarang, batas-batas ini agak boros jika : ada juga varian Chernoff batas yang menyatakan Pr [ ¯ X ≤ p - δ ]c≪a
yang akan memungkinkan kita untuk mendapatkan dengan jumlah sampeltlebih kecil dengan faktor sekitarp. Masalahnya adalah bahwap=c/aadalah jumlah yang ingin kita perkirakan, maka kita tidak mengetahuinya sebelumnya. Ini dapat diatasi dengan membuat estimasi pertama ball-parkc.
Jadi, protokol yang ditingkatkan menghitung dengan probabilitas suatu aditif d -pendekatan c menggunakan O ( min { a , b }≥1−ϵ d c bit komunikasi, danO(min{a,b}O(min{a,b}d(1+cd)lognlogϵ−1) bit keacakan, dan itu berjalan sebagai berikut (konstanta tidak dioptimalkan):O(min{a,b}d(1+cd)logmin{a,b}logϵ−1)
Sama seperti di atas.
Alice menarik sampel acak a / d dari A , dan mengirimkannya ke Bob.r=10(logϵ−1)a/d A
Bob jumlah berapa banyak sampel ini milik , dan mengirimkan nomor ini, s , untuk Alice.B s
Jika , protokol berakhir dengan output 0 .as/r≤d/2 0
Alice menarik sampel acak yang saya ∈ A , i < t , dan mengirimkannya ke Bob.t=10sa/d ai∈A i<t
Bob memperkirakan sebagai ac .at|{i<t:ai∈B}|
Tanpa masuk ke dalam perincian, batas Chernoff yang dikutip di atas menyiratkan bahwa dengan probabilitas tinggi, nilai adalah Θ ( c / a ) , dalam hal ini protokol tidak melebihi biaya yang dinyatakan, dan ia menghitung dengan probabilitas tinggi a. Estimasi C yang baik dengan aplikasi lain dari batas Chernoff.s/r Θ(c/a) c
sumber
[Jawaban Emil jelas lebih baik dan lebih sederhana jika Anda tertarik pada jenis kesalahan ini, kecuali karena alasan tertentu Anda membutuhkan protokol Anda untuk menjadi deterministik. Ups.]
Ada protokol nontrivial jika Anda tertarik pada perkiraan aditif tipe untuk konstanta kecil δ > 0 .±δn δ>0
Sebagai contoh, ini satu:
Jika pendekatan semacam ini menarik bagi Anda, Anda mungkin mendapatkan jarak tempuh lebih banyak dari lemma keteraturan grafik lainnya, terutama Frieze-Kannan. Ini adalah survei.
sumber