Bukti yang mengekspos struktur yang lebih dalam

35

Bukti standar ikatan Chernoff (dari buku Acak Algoritma ) menggunakan Markov ketidaksetaraan dan fungsi menghasilkan momen, dengan sedikit ekspansi Taylor dilemparkan. Tidak ada yang terlalu sulit, tetapi agak mekanis.

Tetapi ada bukti terikat Chernoff lainnya yang mengekspos struktur yang lebih dalam mendorong hasilnya. Misalnya, ada versi informasi-teoretis yang menggunakan metode tipe, dicontohkan oleh makalah Impagliazzo dan Kabanets ini , serta tulisan singkat ini oleh Sanjoy Dasgupta . Bukti terakhir ini lebih "intuitif" karena memberikan generalisasi hasil standar, serta menjelaskan dari mana asalnya istilah lucu dalam eksponen (ini adalah KL-divergence).

Apa contoh bagus dari hal-hal seperti itu? Agar lebih konkret, berikut aturannya:

Pernyataan itu harus cukup terkenal (hal yang akan diajarkan di semacam kelas pascasarjana)

Seharusnya ada "standar" bukti yang tersedia di buku pelajaran atau bahan referensi standar yang "umum" diajarkan

Seharusnya ada bukti alternatif yang tidak begitu terkenal, TIDAK diajarkan secara umum, dan bisa membuktikan pernyataan yang lebih umum atau menghubungkan pernyataan itu dengan struktur matematika yang lebih dalam.

Saya akan mulai dengan dua contoh.

Kabel terikat
- "buku teks" bukti: markov ketimpangan, fungsi menghasilkan momen, ekspansi Taylor (MR)
- Bukti yang tidak umum dan berwawasan luas: metode tipe, eksponen ekor yang melibatkan KL-divergensi
The Schwartz-Zippel Lemma
- "buku teks" bukti: kasus dasar yang melibatkan polinomial univariat. Induksi pada sejumlah variabel
- Bukti "tidak umum": argumen geometris melalui Dana Moshkovitz (dan Per Vognsen )

Tolong, satu contoh per jawaban.

ps Saya tidak perlu menyiratkan bahwa bukti yang tidak biasa harus diajarkan: bukti langsung seringkali lebih mudah bagi siswa. Tetapi dalam arti bahwa "bukti membantu kita memahami", bukti alternatif ini sangat membantu.

big-list proofs Suresh Venkat
sumber

23

Saya tidak yakin ini yang Anda cari, karena saya telah melihat bukti "tidak umum" di buku pelajaran, tetapi: waktu O (n log n) terikat untuk quicksort.

"Buku Teks" bukti: mengatur hubungan perulangan acak, buktikan dengan induksi bahwa ia memiliki solusi yang diinginkan.
"Tidak umum" bukti: temukan rumus sederhana untuk probabilitas bahwa setiap dua elemen dibandingkan (hanya 2 / (d + 1) di mana d adalah perbedaan antara peringkat mereka dalam urutan diurutkan), dan gunakan linearitas dari harapan dan seri harmonik untuk menghitung jumlah pasangan yang diharapkan yang dibandingkan.

Bukti buku teks membutuhkan wawasan yang kurang kreatif, tetapi bukti yang tidak umum memperkenalkan teknik yang sangat berguna dalam analisis algoritma lain misalnya untuk algoritma inkremental acak dalam geometri komputasi.

David Eppstein
sumber

3

Saya pikir ini berhasil. itu contoh yang bagus. Anda benar bahwa bukti 'tidak umum' juga ada di buku pelajaran, tetapi masih belum umum.

Suresh Venkat

1

Saya telah mengajar undergrads yang bukti "tidak biasa" selama lebih dari satu dekade.

Jeff

Saya tidak tahu apa yang dipikirkan orang lain tentang itu; tetapi Jon Bentley telah memberikan analisis runtime yang sangat elegan untuk runtime cepat yang diharapkan dari teks Kode Indah. Anda juga dapat mengakses videonya melalui topik yang sama <a href=" youtube.com/watch?v=aMnn0Jq0J-E"> di sini </ a >. Saya cukup yakin ini adalah "analisis buku" dari runtime quicksort yang diharapkan

Akash Kumar

19

Saya akan membuang satu dari kerumitan, bukti bahwa BPP ada di . Bukti buku teks adalah karena Lautemann, cukup tulis ekspresi dan tunjukkan itu bekerja dengan argumen probabilistik sederhana. Bukti yang tidak umum: Tebak fungsi keras ( untuk menebak, untuk memeriksa kekerasan) dan hubungkan ke generator Nisan-Wigderson. $\Sigma_2^p$ $\exists\forall$ $\exists$ $\forall$

Lance Fortnow
sumber

Selain itu, bukti Lautemann sangat menyederhanakan bukti Sipser (1983), yang dikaitkan oleh Sipser dengan Gacs.

MS Dousti

1

Apakah ada referensi untuk bukti "tidak biasa", atau itu cerita rakyat?

MS Dousti

2

Buktinya ada di koran Nisan-Wigderson.

Lance Fortnow

2

Ini adalah "bukti biasa", tapi apa "pemahaman baru" dari bukti ini? Saya akan berpikir bukti Lautemann lebih mencerahkan. Apakah saya melewatkan sesuatu di sini?

V Vinay

13

Kita semua tahu untuk Bernoulli harus berperilaku seperti seorang Gaussian dengan standar deviasi , kan? Jadi, mari kita buktikan dengan berhubungan langsung dengan orang Gaussians! Mengambil bilangan bulat, $\sum_i a_iX_i$ $\pm 1$ $X_i$ $\sigma = \|a\|_2$ $t \ge 2$

\begin{array}{rcl} E [{(\sum_{i} a_{i} X_{i})}^{t}] & = & \sum_{i_{1}, \dots, i_{t}} (\prod_{j = 1}^{t} a_{i_{j}}) E [\prod_{j = 1}^{t} X_{i_{j}}] \\ \leq & \sum_{i_{1}, \dots, i_{t}} (\prod_{j = 1}^{t} | a_{i_{j}} |) E [\prod_{j = 1}^{t} X_{i_{j}}] \\ = & \sum_{\begin{matrix} i_{1} < \dots < i_{m} \\ r_{1}, \dots, r_{m} \\ \sum_{j} r_{j} = t \\ \forall j r_{j} > 0 \end{matrix}} (\binom{t}{r_{1}, \dots, r_{m}}) (\prod_{j = 1}^{m} | a_{i_{j}} |^{r_{j}}) (\prod_{j = 1}^{m} E [X_{i_{j}}^{r_{j}}]) \end{array}

$\begin{eqnarray*} \mathbf{E}\left[\left(\sum_i a_iX_i\right)^t\right] &=& \sum_{i_1,\ldots,i_t} \left(\prod_{j=1}^t a_{i_j}\right) \mathbf{E}\left[\prod_{j=1}^t X_{i_j}\right]\\ &\le& \sum_{i_1,\ldots,i_t} \left(\prod_{j=1}^t |a_{i_j}|\right) \mathbf{E}\left[\prod_{j=1}^t X_{i_j}\right]\\ &=& \sum_{\substack{i_1<\ldots< i_m\\ r_1,\ldots,r_m\\ \sum_j r_j = t\\ \forall j\ r_j > 0}} \binom{t}{r_1,\ldots,r_m}\left(\prod_{j=1}^m |a_{i_j}|^{r_j}\right)\left(\prod_{j=1}^m \mathbf{E}[X_{i_j}^{r_j}]\right) \end{eqnarray*}$

$r_j$ $0$ $1$ $X_i$ $G_i$ $r_j$ $0$ $r_j$ $1$

E [{(\sum_{i} a_{i} X_{i})}^{t}] \leq E [{(\sum_{i} | a_{i} | G_{i})}^{t}]

$\mathbf{E}\left[\left(\sum_i a_iX_i\right)^t\right] \le \mathbf{E}\left[\left(\sum_i |a_i|G_i\right)^t\right]$

$2$ $\sum_i |a_i| G_i$ $\|a\|_2$ $t$ $\|a\|_2^t \cdot t! / (2^{t/2} \cdot (t/2)!)$ $\|a\|_2^tt^{t/2}$

P r [| \sum_{i} a_{i} X_{i} | > λ] < 2^{O (t)} \cdot λ^{- t} \cdot ‖ a ‖_{2}^{t} t^{t / 2}

$\mathbf{Pr}\left[\left|\sum_i a_iX_i\right| > \lambda\right] < 2^{O(t)}\cdot \lambda^{-t}\cdot \|a\|_2^t t^{t/2}$

t = λ^{2} / (C \cdot ‖ a ‖_{2}^{2})

$t = \lambda^2 / (C\cdot \|a\|_2^2)$

C

$C$

e x p (- Ω (λ^{2} / ‖ a ‖_{2}^{2}))

$\mathrm{exp}(-\Omega(\lambda^2 / \|a\|_2^2))$

X_{i}

$X_i$

Jelani Nelson
sumber

6

$A$ $r_i$ $i$ $A$

\prod_{i} (r_{i}!)^{1 / r_{i}} .

$\prod_i (r_i!)^{1/r_i}.$

Timothy Chow
sumber

Bukti yang mengekspos struktur yang lebih dalam

Jawaban: