Pengaruh minimum yang diharapkan dari fungsi Boolean acak

Untuk fungsi Boolean $f\colon\{-1,1\}^n \to \{-1,1\}$ , pengaruh variabel ke- didefinisikan sebagai mana adalah string yang diperoleh dengan membalik sedikit . Pengaruh minimum adalah $i$

{Inf}_{i} [f] \overset{d e f}{=} \underset{x \sim {- 1, 1}^{n}}{Pr} [f (x) \neq f (x^{\oplus i})]

$\operatorname{Inf}_i[f] \stackrel{\rm def}{=} \Pr_{x\sim\{-1,1\}^n}[ f(x) \neq f(x^{\oplus i})]$

x^{\oplus i}

$x^{\oplus i}$

i

$i$

x

$x$

f

$f$

MinInf [f] \overset{d e f}{=} min_{i \in [n]} {Inf}_{i} [f] .

$\operatorname{MinInf}[f] \stackrel{\rm def}{=} \min_{i\in[n]}\operatorname{Inf}_i[f].$

Dengan parameter $p\in[0,1]$ , kami memilih fungsi $p$ -random $f$ dengan memilih nilainya pada masing-masing dari $2^n$ input secara independen menjadi $1$ dengan probabilitas $p$ , dan $-1$ dengan probabilitas $1-p$ . Maka, mudah untuk melihat bahwa, untuk setiap $i\in[n]$

E_{f} [{Inf}_{i} [f]] = 2 p (1 - p)

$\mathbb{E}_{f}[\operatorname{Inf}_i[f]] = 2p(1-p)$ dan fortiori

I_{n} (p) \overset{d e f}{=} E_{f} [MinInf [f]] \leq 2 p (1 - p) .

$I_n(p) \stackrel{\rm def}{=}\mathbb{E}_{f}[\operatorname{MinInf}[f]] \leq 2p(1-p).$

Pertanyaanku adalah:

Apakah ada ekspresi ketat asymptotically (berkaitan dengan ) untuk ? Bahkan untuk , bisakah kita mendapatkan ungkapan seperti itu? $n$ $I_n(p)$ $p=\frac{1}{2}$

Secara khusus, saya sangat peduli dengan persyaratan pesanan rendah, yaitu saya akan tertarik pada padanan asimptotik untuk kuantitas . $2p(1-p)-I_n(p)$

(Pertanyaan berikutnya, tetapi yang lebih rendah dari yang pertama, adalah apakah seseorang juga bisa mendapatkan batas konsentrasi yang baik di sekitar harapan ini.)

Dengan batas Chernoff kita juga dapat menunjukkan bahwa setiap memiliki konsentrasi yang baik, sehingga dengan ikatan serikat kita dapatkan (jika saya tidak mengacaukan terlalu buruk) tetapi ini kemungkinan besar longgar di batas bawah (karena ikatan serikat) dan pasti pada batas atas. (Saya khususnya mencari batas atas yang benar-benar kurang dari sepele ). $\operatorname{Inf}_i[f]$

\frac{1}{2} - O (\sqrt{\frac{n}{2^{n}}}) \leq I_{n} (\frac{1}{2}) \leq \frac{1}{2}

$\frac{1}{2} - O\left(\sqrt{\frac{n}{2^n}}\right) \leq I_n\left(\frac{1}{2}\right) \leq \frac{1}{2}$

\frac{1}{2}

$\frac{1}{2}$

Perhatikan bahwa salah satu masalah dalam melakukan itu, selain mengambil minimum variabel acak yang terdistribusi secara identik (pengaruhnya), adalah bahwa variabel-variabel acak ini tidak independen ... walaupun saya berharap korelasi mereka meluruh "cukup cepat" dengan . $n$ $n$

(Untuk apa nilainya, saya telah menghitung secara eksplisit beberapa hingga , dan telah menjalankan simulasi untuk memperkirakan yang berikut, hingga atau lebih. Tidak yakin seberapa membantu hal ini bisa jadi, tetapi saya dapat memasukkannya begitu saya kembali ke kantor saya.) $I_n(1/2)$ $n=4$ $n=20$

reference-request pr.probability boolean-functions Clement C.
sumber

Berikut adalah beberapa yang pertama (hanya 4 yang pertama yang tepat, yang lain berasal dari pengambilan sampel acak (untuk memperkirakan pengaruh) rata-rata lebih dari 10 ^ 5 fungsi yang dihasilkan secara acak):

(catatan: untuk simulasi, tidak yakin digit ke-4 benar-benar signifikan)

\begin{aligned} 1 & 0.500 \\ 2 & 0.375 \\ 3 & 0.3359375 \\ 4 & 0.339141845703125 \\ 5 & 0.3623 \\ 6 & 0.3907 \\ 7 & 0.4166 \\ 8 & 0.4373 \\ 9 & 0.4535 \\ 10 & 0.4659 \\ 11 & 0.4751 \\ 19 & 0.4965 \\ 20 & 0.4967 \end{aligned}

$\begin{align}1 &\qquad 0.500\\ 2 &\qquad 0.375\\ 3 &\qquad 0.3359375\\ 4 &\qquad 0.339141845703125\\ 5 &\qquad 0.3623\\ 6 &\qquad 0.3907\\ 7 &\qquad 0.4166\\ 8 &\qquad 0.4373\\ 9 &\qquad 0.4535\\ 10 &\qquad 0.4659\\ 11 &\qquad 0.4751\\ 19 &\qquad 0.4965\\ 20 &\qquad 0.4967\\ \end{align}$

Clement C.

Jawaban:

Inilah langkah ke arah yang benar ...

Aku akan berpendapat bahwa untuk , Anda memiliki $p=1/2$ . $1/2 - I_n(1/2) = \Omega(\sqrt{1/2^n})$

(Ini tidak sekuat yang seharusnya. Mungkin seseorang dapat memperkuat argumen untuk menunjukkan .) Ini adalah sketsa bukti. $\Omega(\sqrt{n/2^n})$

Itu sudah cukup untuk menunjukkan . Kami melakukan itu. $1/2 - E_f[\min(\text{Inf}_1[f],\text{Inf}_2[f])] = \Omega(\sqrt{1/2^n})$

Perhatikan bahwa jika dan benar-benar independen, kami akan dilakukan karena harapan minimum dari dua jumlah independen adalah $\text{Inf}_1[f]$ $\text{Inf}_2[f]$ . Pertama, kami akan berdebat dengan hati-hati bahwa kedua jumlah tersebut hampir independen. $1/2-\Omega(\sqrt{1/2^n})$

Pertimbangkan semesta dari titik . Panggil dan dalam -tempat tinggal jika mereka berbeda hanya dalam koordinat ke- . Katakanlah kedua tetangga berkontribusi (ke ) jika . (Jadi adalah jumlah berkontribusi $X=\{-1,1\}^n$ $x$ $x'$ $X$ $i$ $i$ $\text{Inf}_i[f]$ $f(x) \ne f(x')$ $\text{Inf}_i[f]$ $i$ -neighbors, dibagi ) Perhatikan bahwa, jika dan adalah oneighbors, dan dan adalah oneighbors, maka atau . Karenanya, jumlah yang berkontribusi $2^{n-1}$ $x$ $x'$ $i$ $y$ $y'$ $i$ $\{x,x'\}=\{y,y'\}$ $\{x,x'\}\cap\{y,y'\}=\emptyset$ $i$ -neighbors adalah jumlah dari variabel acak independen, masing-masing dengan harapan . $2^{n-1}$ $1/2$

Partisi alam semesta menjadi kelompok ukuran empat, di mana dan berada dalam kelompok yang sama jika dan setuju pada semua kecuali dua koordinat pertama mereka. Kemudian untuk setiap pasangan dari 1-tetangga, dan setiap pasangan dari 2-tetangga, dan berada dalam kelompok yang sama. Untuk grup dan $X$ $2^{n-2}$ $x$ $x'$ $x$ $x'$ $(x,x')$ $(x,x')$ $x$ $x'$ $g$ , biarkan rv menjadi jumlah kontribusi -neighbors di . Kemudian, misalnya, jumlah penyumbang 1-tetangga secara keseluruhan adalah , jumlah variabel acak independen, masing-masing dalam . $i\in\{1,2\}$ $c^g_i$ $i$ $g$ $\sum_g c^g_1$ $2^{n-2}$ $\{0,1,2\}$

Perhatikan bahwa dan independen jika . Dengan analisis kasus, jika , distribusi bersama dan adalah $c^g_1$ $c^{g'}_2$ $g\ne g'$ $g=g'$ $c^g_1$ $c^g_2$

\begin{array}{cccc} 0 & 1 & 2 \\ 0 & 1 / 8 & 0 & 1 / 8 \\ 1 & 0 & 1 / 2 & 0 \\ 2 & 1 / 8 & 0 & 1 / 8 \end{array}

$\begin{array}{c|ccc} & 0 & 1 & 2 \\ \hline 0 & 1/8 & 0 & 1/8 \\ 1 & 0 & 1/2 & 0 \\ 2 & 1/8 & 0 & 1/8 \\ \end{array}$

Let r.v. $N=\{ g : c^g_1=c^g_2=1\}$ denote the set of neutral groups. (They contribute exactly their expected amount to the 1-influence and the 2-influence.) The number of contributing 1-neighbors is then

| N | + \sum_{g \in \bar{N}} c_{1}^{g} .

$|N| + \sum_{g\in \overline{N}} c^g_1.$

Conditioned on $N$ , for each $g\in \overline N$ r.v.'s $c^g_1$ and $c^g_2$ are independent (by inspection of their joint distribution above), so (conditioned on $N$ ) all r.v.'s $\{c^g_i : i\in\{1,2\}, g\in\overline N\}$ are i.i.d. uniformly over $\{0,2\}$ so,

E [| \bar{N} | - min (\sum_{g \in \bar{N}} c_{1}^{g}, \sum_{g \in \bar{N}} c_{2}^{g}) | N] \geq Θ (\sqrt{| \bar{N} |}) .

$\textstyle E\Big[|\overline N|- \min\big(\sum_{g\in \overline N} c^g_1, \sum_{g\in \overline N} c^g_2\big) ~\Big|~ N\Big] \ge \Theta(\sqrt{|\overline N|}).$

Finally, note that each group is neutral with probability 1/2, so $\Pr[|\overline N| \le 2^{n-2}/3]$ is extremely small, say $\exp(-\Omega(2^n))$ (and even in that case the left-hand-side above is at least $-2^n$ ). From this the claimed lower bound follows...

Neal Young
sumber

Thank you! I'll try and see if there is a way to adapt your approach get an additional

n

$n$ under the root...

Clement C.