Добрый день!

Вот какую задачку я откопал в учебнике по Д.Математике:

Есть два генератора случайных двоичных векторов длины n и веса e.
Причём, n > 2*e
Векторы, сошедшие с генераторов умножаются друг на друга.
Найти мат. ожидание веса получившегося вектора.

Вчера несколько часов сидел, пока понял чего хотят

Здравствуйте, Аноним, Вы писали:

А>Добрый день!

А>Вот какую задачку я откопал в учебнике по Д.Математике:

А>Есть два генератора случайных двоичных векторов длины n и веса e.
А>Причём, n > 2*e
А>Векторы, сошедшие с генераторов умножаются друг на друга.
А>Найти мат. ожидание веса получившегося вектора.

А>Вчера несколько часов сидел, пока понял чего хотят

Хотелось бы уточнить
1) какой вес имеется в виду.
2) что значит умножаются друг на друга? скалярное произведение или попарное произведение координат?
3) на генераторы неплохо было бы наложить ограничения по поводу корреляции.

Здравствуйте, ghost92, Вы писали:

G>Здравствуйте, Аноним, Вы писали:

G>Хотелось бы уточнить
G>1) какой вес имеется в виду.
G>2) что значит умножаются друг на друга? скалярное произведение или попарное произведение координат?
G>3) на генераторы неплохо было бы наложить ограничения по поводу корреляции.

Мои предположения на этот счёт:
1. Вес двоичного вектора — кол-во ненулевых элементов
2. Попарное произведение. Иначе вопрос о весе результирующего вектора был бы довольно странным
3. Генераторы абсолютно независимые (иначе, как мне кажется, это было бы оговорено в условии дополнительно)

Но, это, как я уже сказал, моё понимание задачи.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, ghost92, Вы писали:

G>>Здравствуйте, Аноним, Вы писали:

G>>Хотелось бы уточнить
G>>1) какой вес имеется в виду.
G>>2) что значит умножаются друг на друга? скалярное произведение или попарное произведение координат?
G>>3) на генераторы неплохо было бы наложить ограничения по поводу корреляции.

А>Мои предположения на этот счёт:
А>1. Вес двоичного вектора — кол-во ненулевых элементов
А>2. Попарное произведение. Иначе вопрос о весе результирующего вектора был бы довольно странным
А>3. Генераторы абсолютно независимые (иначе, как мне кажется, это было бы оговорено в условии дополнительно)

А>Но, это, как я уже сказал, моё понимание задачи.

Ну если n> 2* e то вектора уже не случайные)))))

Пусть генераторы генерируют вектора v1 и v2.
Можно считать что сначала генерируется v1 затем v2.
Возьмем перестановку А такую, что А(v1) = (1, 1, 1 ... 1, 0, 0, 0 ... 0 )
А(v1 * v2) = А(v1) * А(v2), при этом А сохраняет вес.
Теперь достаточно посчитать мат ожидание количества единиц вектора v2 находящихся до координаты "e".
Кстати генератор то у нас какой?
на сколько понимаю всего различных варинатов векторов у нас C(e,n) и генерации любых двух вариантов равновероятны.

А>Ну если n> 2* e то вектора уже не случайные)))))
???
а что при этом мешает им быть случайными?
"n" и "е" просто фиксированы.

Здравствуйте, ghost92, Вы писали:

А>>Ну если n> 2* e то вектора уже не случайные)))))
G>???
G>а что при этом мешает им быть случайными?
G>"n" и "е" просто фиксированы.
Просто если вектора генерятся абсолютно случайно то метемптическое ожидание его веса e = n/2
А эти вектора генерятся так чтобы e < n/2

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, ghost92, Вы писали:

А>>>Ну если n> 2* e то вектора уже не случайные)))))
G>>???
G>>а что при этом мешает им быть случайными?
G>>"n" и "е" просто фиксированы.
А>Просто если вектора генерятся абсолютно случайно то метемптическое ожидание его веса e = n/2
А>А эти вектора генерятся так чтобы e < n/2

А... Черт извиняюсь, был неправ............

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Аноним, Вы писали:

А>>Здравствуйте, ghost92, Вы писали:

А>>>>Ну если n> 2* e то вектора уже не случайные)))))
G>>>???
G>>>а что при этом мешает им быть случайными?
G>>>"n" и "е" просто фиксированы.
А>>Просто если вектора генерятся абсолютно случайно то метемптическое ожидание его веса e = n/2
А>>А эти вектора генерятся так чтобы e < n/2

А>А... Черт извиняюсь, был неправ............

Вообще у меня получилось (1+ [n/2])^2 / 4 где [n/2] -- это минимальное натуральное число < n/2

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Аноним, Вы писали:

А>>Здравствуйте, Аноним, Вы писали:

А>>>Здравствуйте, ghost92, Вы писали:

А>>>>>Ну если n> 2* e то вектора уже не случайные)))))
G>>>>???
G>>>>а что при этом мешает им быть случайными?
G>>>>"n" и "е" просто фиксированы.
А>>>Просто если вектора генерятся абсолютно случайно то метемптическое ожидание его веса e = n/2
А>>>А эти вектора генерятся так чтобы e < n/2

А>>А... Черт извиняюсь, был неправ............

А>Вообще у меня получилось (1+ [n/2])^2 / 4 где [n/2] -- это минимальное натуральное число < n/2

.... поправка [n/2] мин натуральное <= n/2

Как я понял, есть набор векторов длины n с условием, что n>2*e, где e — вес вектора.
Таких векторов С(e,n).
А "генерирование" сводится к случайному выбору вектора из списка
Только и всего.

Здравствуйте, ghost92, Вы писали:

G>Пусть генераторы генерируют вектора v1 и v2.
G>Можно считать что сначала генерируется v1 затем v2.
G>Возьмем перестановку А такую, что А(v1) = (1, 1, 1 ... 1, 0, 0, 0 ... 0 )
G>А(v1 * v2) = А(v1) * А(v2), при этом А сохраняет вес.
G>Теперь достаточно посчитать мат ожидание количества единиц вектора v2 находящихся до координаты "e".
G>Кстати генератор то у нас какой?
G>на сколько понимаю всего различных варинатов векторов у нас C(e,n) и генерации любых двух вариантов равновероятны.

Введем множество фунцкий f.
результатом фукнции f(i,j,k) действующей на вектор "v" с весом "i" и длиной "k"
будет количество ненулевых координат, находящихся до "j" (включительно)

Тогда мат.ожидание = сумма f(e,e,n) по всем векторам / количество всех векторов.
Введем функцию F(i, j, k) = сумма всех функций f(i,j,k) по всем векторам "v", подходящим к этой функции.

рассмотрим 2 варината.
1) первая координата вектора нулевая.
2) первая координата вектора не нулевая.

 F(i, j, k) = (1) + (2) 
 (1) = F(i, j-1, k-1)
                           i-1
 (2) = F(i-1, j-1, k-1) + C   
                           k-1

при этом

F( i, 0, k ) = 0
F( i, j, i ) = j


количество всех различных векторов

  e
 C
  n

осталось посчитать F(e,e,n)

Здравствуйте, ghost92, Вы писали:

G>осталось посчитать F(e,e,n)

По-моему, всё гораздо проще.
Для подсчёта мат. ожидания воспользуемся классической формулой Сумма(для m=0 до m=e) по m*p(m),
где p(m) вероятность получения вектора веса m.

p(m) = C(e,n)*C(m,e)*C(e-m,n-e) / [C(e,n)]^2

И всё

Здравствуйте, ghost92, Вы писали:

G>Пусть генераторы генерируют вектора v1 и v2.
G>Можно считать что сначала генерируется v1 затем v2.
G>Возьмем перестановку А такую, что А(v1) = (1, 1, 1 ... 1, 0, 0, 0 ... 0 )
G>А(v1 * v2) = А(v1) * А(v2), при этом А сохраняет вес.
G>Теперь достаточно посчитать мат ожидание количества единиц вектора v2 находящихся до координаты "e".

Найти мат.ожидание веса e-мерной головы n-мерного вектора с весом e.

Длина головы e, длина хвоста n-e.

Рассмотрим классы векторов с весом головы h=0..e
В каждом классе вес головы h, вес хвоста e-h. Количество векторов q=C(e,h)*C(n-e,e-h).

Итого, M = sum(h=0..e) h*C(e,h)*C(n-e,e-h)/C(n,e)

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, ghost92, Вы писали:

G>>осталось посчитать F(e,e,n)

А>По-моему, всё гораздо проще.
А>Для подсчёта мат. ожидания воспользуемся классической формулой Сумма(для m=0 до m=e) по m*p(m),
А>где p(m) вероятность получения вектора веса m.

А>p(m) = C(e,n)*C(m,e)*C(e-m,n-e) / [C(e,n)]^2

А>И всё

ну да так проще.