Произведение случайных булевых полиномов

[Daniil_Sh]

Рассмотрим такой пример: даны два булевых полинома $f_1(x_1,x_2)=\xi_{00}^{1}+\xi_{01}^{1}x_1+\xi_{10}^{1}x_2+\xi_{11}^{1}x_1x_2$ и $f_2(x_1,x_2)=\xi_{00}^{2}+\xi_{01}^{2}x_1+\xi_{10}^{2}x_2+\xi_{11}^{2}x_1x_2$, где $\xi_{i}^{k}$ независимые равномерно распределённые на $\{0,1\}$ случайные величины, нижние индексы показывают соответствие мономам, верхние индексы связаны с номером полинома. Вектор коэффициентов $f_1f_2$ получается такой:

$$(\xi_{00}^1\xi_{00}^{2},\xi_{00}^{1}\xi_{01}^{2}\oplus \xi_{01}^{1}\xi_{00}^{2}\oplus\xi_{01}^{1}\xi_{01}^{2},\xi_{00}^{1}\xi_{10}^{2}\oplus \xi_{10}^{1}\xi_{00}^{2}\oplus\xi_{10}^{1}\xi_{10}^{2},\xi_{00}^{1}\xi_{11}^{2}\oplus\xi_{01}^{1}\xi_{10}^{2}\oplus\xi_{01}^{1}\xi_{11}^{2}\oplus\xi_{10}^{1}\xi_{01}^{2}\oplus\xi_{10}^{1}\xi_{11}^{2}\oplus\xi_{11}^{1}\xi_{00}^{2}\oplus\xi_{11}^{1}\xi_{01}^{2}\oplus\xi_{11}^{1}\xi_{10}^{2}\oplus\xi_{11}^{1}\xi_{11}^{2}).$$

(в общем случае, компоненты этого вектора вычисляются по формуле (свёртка) $\oplus_{i\vee j=ind}\ \xi_{i}^{1}\xi_{j}^{2}$, где $ind$ — индекс компоненты, $ind\in\{0,1,...,2^n-1\}$).
Чтобы вычислить математические ожидания компонент этого вектора, необходимо перейти от $\oplus$ к $+$ по формуле $x_1\oplus x_2\oplus...\oplus x_n=\frac{1}{2}(1-(1-2x_1)(1-2x_2)...(1-2x_n))$ или, что то же самое, $\sum\limits_{i=1}^{n}x_i-2\sum\limits_{i< j}x_ix_j+4\sum\limits_{i< j< k}x_ix_jx_k-...$.
Например, третья компонента преобразуется к виду

$$\xi_{00}^{2}\xi_{10}^{1}+\xi_{00}^{1}\xi_{10}^{2}+\xi_{10}^{1}\xi_{10}^{2}-2\xi_{00}^{1}\xi_{00}^{2}\xi_{10}^{1}\xi_{10}^{2}-2\xi_{00}^{2}(\xi_{10}^{1})^2\xi_{10}^{2}-2\xi_{00}^{1}\xi_{10}^{1}(\xi_{10}^{2})^2+4\xi_{00}^{1}\xi_{00}^{2}(\xi_{10}^{1})^2(\xi_{10}^{2})^2.$$

Преобразуя остальные компоненты и учитывая, что любая степень $\xi$ совпадает с $\xi$, получим вектор математических ожиданий $(\frac{1}{4},\frac{3}{8},\frac{3}{8},\frac{15}{32})$.

В общем случае, имеется $n$ булевых полиномов от $n$ переменных со случайными коэффициентами (равномерно распределены на $\{0,1\}$), я хочу найти математические ожидания коэффициентов произведения $f_1f_2...f_n$. У меня трудность с учётом $(\xi_{i}^{k})^{n}=\xi_{i}^{k}$ для любого $n\in\mathbb{N}$ (эти степени возникают при переходе от $\oplus$ к $+$).

[DeBill]

Daniil_Sh в сообщении #1479508 писал(а):

любая степень $\xi$ совпадает с $\xi$,

Daniil_Sh в сообщении #1479508 писал(а):

с учётом $(\xi_{i}^{k})^{n}=\xi_{i}^{k}$

Это еще почему????
А почему бы по простому не сосчитать матожидание произведения - обычного, забив на будевость - а потом привести подобные? Кстати, получится вектор из одних четвертинок - а не как у Вас....

[Daniil_Sh]

DeBill, $\xi$ принимает значения 0 или 1. Поэтому, например, $\text{E}\xi^2=\frac{1}{2}$, но не $\frac{1}{4}$.

[Xaositect]

/Кажется, произведение лучше считать не в полиномах, а в векторах значений.

Рассмотрим Ваш пример. Равномерное распределение коэффициентов полинома - это все равно, что равномерное распределение значений будевой функции. У произведения двух равномерных случайных булевых функций значения будут независимыми одинаково распределенными величинами с вероятностью нуля $\frac34$ и вероятностью единицы $\frac14$. Дальше, коэффициенты многочлена - это линейные (по модулю 2) функции от значений, и матожидание их будет зависеть только от количества слагаемых. Например, $\xi_{01} = f(0,0) \oplus f(0,1)$, $\mathbb P(\xi_{01} = 1) = 2 \cdot \frac34 \cdot \frac14 = \frac38$. В общем случае там будет сумма нечетных членов бинома, понятно, как считать.

[Утундрий]

(Оффтоп)

DeBill в сообщении #1479563 писал(а):

будевость

Xaositect в сообщении #1479629 писал(а):

будевой

Я проспал какую-то реформу?

[DeBill]

...

[Daniil_Sh]

Xaositect, Спасибо. Всё получилось.

[DeBill]

Daniil_Sh
Ага, это я был невнимателен...
Однако, я все же не понимаю...
1. Ведь матожидание - оно линейно (и мультипликативно - для независимых. Ужасная формула по превращениям обещает , что все будет хорошо - в нашем случае). Так что нам мешает заменить матожидание произведения на произведение мптожиданий?
2.

Daniil_Sh в сообщении #1479508 писал(а):

Например, третья компонента преобразуется к виду

И прекрасно! Однако из этой формулы получается матожидание равным одной четверти, разве нет?
3. Все коэф-ты нашего многочлена совершенно равноправны, да? (инволюциями вида $x_i \mapsto 1-x_i$ мы можем любой к-т превратить в Свободный Член). А для Свободного ответ - одна четверть. Значит, и для всех прочих - тоже... А в общем случае, соответственно - один на два в энной...

-- 18.08.2020, 10:19 --

Xaositect в сообщении #1479629 писал(а):

Например, $\xi_{01} = f(0,0) \oplus f(0,1)$, $\mathbb P(\xi_{01} = 1) = 2 \cdot \frac34 \cdot \frac14 = \frac38$.

Боюсь, что пара эта - зависимая....

-- 18.08.2020, 10:24 --

[EUgeneUS]

DeBill в сообщении #1479679 писал(а):

И прекрасно! Однако из этой формулы получается матожидание равным одной четверти, разве нет?

У меня получилось $\frac{3}{8}$

[DeBill]

EUgeneUS
Ага, у меня - по новой - тоже..
Получается, что весь мой пред пост - бред...
А так правдоподобно...

[Daniil_Sh]

В произведении $n$ полиномов коэффициент перед мономом $k$-ой степени равен 1 с вероятностью $\frac{1}{2}\cdot(1 - (1 - 2^{1-n})^{2^k})$.