2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 какое распределение?
Сообщение01.05.2011, 23:38 
Дано: 4 списка двоичных векторов длины n - $L_1, L_2, L_3, L_4.$
В каждом списке по 4 вектора, каждый вектор генерируется случайно, равновероятно. Нужно найти $P{\{|\{(x_1,x_2,x_3,x_4):x_1 \in L_1,x_2 \in L_2,x_3 \in L_3,x_4 \in L_4, x_1 \oplus x_2 \oplus x_3 \oplus x_4 = y\}| = k\} }$, где y - фиксированный двоичный вектор длины n (например нулевой).

Всего наборов $ |L_1| \cdot |L_2| \cdot |L_3| \cdot |L_4|$, т.е. 256.
$P\{ x_1 \oplus x_2 \oplus x_3 \oplus x_4 = y \} = 1/2^n$. Тогда, по идее, получается распределение $ Bi(256,1/2^n)$, но векторы$ x_1 \oplus x_2 \oplus x_3 \oplus x_4$ и $x_1 \oplus x_2 \oplus x_3 \oplus x'_4$ где $  (x_4 \neq x'_4)$ зависимы между собой и эти 256 векторов нельзя рассматривать как конечную последовательность независимых случайных величин, распределённых по $Be(1/2^n)$.
Искомая вероятность должна иметь какое-то другое расперделение. Вопрос: какое? :?
p.s. $ \oplus $ - побитовый XOR.
Проводил ряд экспериментов, скорее всего $ Bi(256,1/2^n)$ - "нижняя оценка" искомого распределения.

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group