Рейтинг:2

Проверка независимости комбинации однородных случайных величин с помощью леммы о пиллинге

флаг br

Мой вопрос очень простой. Предполагать $a_0, a_1, a_2, a_3, a_4, b_0, b_1, b_2, b_3, b_4$ находятся $10$ равномерные случайные величины из $\{0,1\}$ независимы друг от друга. Теперь есть выражения вида

  1. $a_4b_4 + a_3(b_0 + b_2+1) + b_3(a_0 + a_2 +1) + a_1(b_2 + b_4) + b_1(a_2 +a_4)$
  2. $a_2b_0 + a_1b_1 + (a_0 + a_2 +1)b_2$

Можем ли мы применить лемму Пиллингапа? Или, альтернативно, случайные величины $a_4b_4, a_3(b_0 + b_2+1), b_3(a_0 + a_2 +1), a_1(b_2 + b_4), b_1(a_2 +a_4)$ независимым в случае 1? Точно так же $a_2b_0, a_1b_1, (a_0 + a_2 +1)b_2$ независимым в случае 2 ?

Как показать независимость или зависимость? Может ли кто-нибудь помочь мне понять это?

p.s. Не могу найти подходящие теги, кроме linear-cryptoanalyses. Любой, кто может лучше пометить вопрос, всегда приветствуется.

kelalaka avatar
флаг in
Плюс это х-или, верно? Для этого вы можете использовать `\oplus`. И обратите внимание, что лемма Piling-Up о x-oring не и. И деструктивно и создает предвзятость!.
hiren_garai avatar
флаг br
да плюс x-or.
Рейтинг:1
флаг cn

За $2$, легко увидеть, что эти переменные независимы, потому что каждая элементарная переменная, которая появляется в одном из выражений, не появляется в другом.

Например

$\mathbb{P}(a_2b_0=0| a_1b_1=0, b_2(a_0 + a_2 +1)=0) = \mathbb{P}(a_4b_4=0)$.

Я думаю, что хороший способ увидеть это - посмотреть энтропию одной из этих переменных:

$H (a_2 b_0 |a_1 b_1, b_2(a_0 + a_2 +1)) \geq H (a_2 b_0 |a_0, a_1, b_1, b_2) = H (a_2 b_0)$.

Последнее равенство вытекает из независимости элементарных переменных.

Таким образом, мы можем вывести $H (a_2 b_0 |a_1 b_1, b_2(a_0 + a_2 +1)) = H (a_2 b_0) $.

О $1$, это сложнее, потому что $b_4, b_2, а_2, а_4$ появляются более чем в одном выражении.

Тогда вы должны показать, что $a_4, b_4, a_3, (b_0 + b_2), b_3, (a_0 + a_2), a_1, (b_2 + b_4), b_1, (a_2 + a_4)$ линейно независимы в $\mathbb{F}_2$ (выполняя линейную алгебру), таким образом, вы можете сделать вывод, что эти переменные (в конечном итоге плюс константа) являются независимыми (с вероятностной точки зрения).

И тогда вы должны использовать аргумент «если $Х, У, Z, Т$ независимы, то $XY$ и $ZT$ являются независимыми».

Редактировать: хороший способ увидеть независимость линейных переменных - вычислить определитель следующей матрицы (первая строка соответствует $a_4$, второй до $b_4$, четвертый по $b_0 + b_2$, и т.д.), вы также можете доказать, что эти семейства векторов генерируются $\mathbb{F}^{10}_p$, и выведите по мощности его базу, и, следовательно, векторы независимы:

$\begin{matrix} 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \ 0 и 0 и 0 и 0 и 0 и 0 и 0 и 0 и 0 и 1 \ 0 и 0 и 0 и 1 и 0 и 0 и 0 и 0 и 0 и 0 \ 0 и 0 и 0 и 0 и 0 и 1 и 0 и 1 и 0 и 0 \ 0 и 0 и 0 и 0 и 0 и 0 и 0 и 0 и 1 и 0 \ 1 и 0 и 1 и 0 и 0 и 0 и 0 и 0 и 0 и 0 \ 0 и 1 и 0 и 0 и 0 и 0 и 0 и 0 и 0 и 0 \ 0 и 0 и 0 и 0 и 0 и 0 и 0 и 1 и 0 и 1 \ 0 и 0 и 0 и 0 и 0 и 0 и 1 и 0 и 0 и 0\ 0 и 0 и 1 и 0 и 1 и 0 и 0 и 0 и 0 и 0 \end{матрица}$

hiren_garai avatar
флаг br
спасибо за исчерпывающий ответ. Энтропия немного продвинута для меня. Часть линейной алгебры, которую вы предложили использовать, в основном показывает, что если выполняется $c_1a_4 + c_2b_4 + \cdots = 0$, то все коэффициенты $c_1, c_2, ..$ равны нулю?
Ievgeni avatar
флаг cn
Да. Точно. Вот и все.
hiren_garai avatar
флаг br
Итак, тогда коэффициенты $(b_2 + b_4), (a_2 + a_4)..$ должны быть разбиты, верно? И тогда мы должны использовать тот факт, что $b_2, b_4,...$ линейно независимы. Таким образом, случайные величины линейно зависимы, так как некоторые коэффициенты имеют ненулевое значение. Я где-то ошибся?
Ievgeni avatar
флаг cn
Что вы подразумеваете под "сломанным правом"?
hiren_garai avatar
флаг br
Также как насчет части $+1$? Я имел в виду правильное $a_2 +a_4 +1$. Я спотыкаюсь, чтобы понять. Вы можете очистить его? Спасибо
hiren_garai avatar
флаг br
Под сломанным я имел в виду $c_1 a_4 + \cdots + c_k (a_2 + a_4) + \cdots = 0$ подразумевает $(c_1 + c_k)a_4 +c_k a_2 + \cdots $ ?
Ievgeni avatar
флаг cn
Если $X$ и $Y$ независимы, то $X+1$ независимы. Таким образом, вы должны рассматривать однородную версию уравнения, чтобы выглядеть линейной независимостью, но тогда, когда вы можете добавить «+1», не изменяя вероятностную независимость.
Ievgeni avatar
флаг cn
Вы можете сделать это, чтобы показать линейную независимость, но я предложил вам два других метода: вычислить определитель ассоциированной матрицы или доказать, что он является базой векторного пространства (показывая, что он генерирует весь канонический вектор).
hiren_garai avatar
флаг br
Вы имели в виду, что $X+1$ и $Y+1$ или $X+1$ и $Y$ независимы? Кроме того, $c_1, c_2, ...$ мне очень понятны, поэтому я пытаюсь показать их таким образом.
Ievgeni avatar
флаг cn
Про "+1" Оба варианта верны, поскольку переменные стоят в $\{0, 1\}$, в этом легко убедиться, рассмотрев определение.
Ievgeni avatar
флаг cn
Итак, если вы используете методы $c_i$, вы можете сделать вывод, что каждый коэффициент $a_i$ равен нулю, потому что $a_i$ и $b_i$ линейно независимы (они образуют каноническая база).
hiren_garai avatar
флаг br
Да. Я понял. Спасибо за ваше время. Почти полегчало.
hiren_garai avatar
флаг br
Еще один вопрос, с помощью условной вероятности мы можем показать, что $X, Y$ независима, тогда $X+1, Y$ независима. Теперь мы можем показать эту независимость также, показав, что $c_1 (X+1) +c_2(Y) = 0 \ подразумевает c_1 X + c_2 Y + c_1 = 0 $, из которого мы должны иметь $c_1 = 0 = c_2$, поэтому из $c_1 X + c_2 Y = c_1$ можем ли мы сказать $c_1 = c_2 = 0 $ ? Потому что мы должны предположить, что $c_1 =0$, чтобы использовать независимость $X$ и $Y$. Это правда ? @левгени
Ievgeni avatar
флаг cn
Давайте [продолжим это обсуждение в чате](https://chat.stackexchange.com/rooms/126509/discussion-between-ievgeni-and-hiren-garai).

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.