вероятность вероятности рознь

[valtih1978]

на одном шаге программы нужно к каждому элементу массива применить операцию мутации с вер-ностью $p$. Если массив длинный, а вероятность маленькая, то пробегать весь массив, вызывая $(r\operatorname{random}(1) > p)$ каждый раз - не эффективно. Лучше, если например $p = 1/1000$, сразу взять элемент с номером $\operatorname{random}(1000)$. В тысячу раз эффективнее!

Стреляя несколько раз, $m$, можно аппроксимировать любое $p$, вычислив зависимость $m$ от $p$: вероятность не попасть в элемент, $1-p$, равняется $(1-1/1000)^m$ откуда $m = \log_{1-1/1000}{(1-p)}$

Однако я чего-то не понимаю. В случае если пробегать все, то может оказаться что ни один из тысячи элементов не выпадет или выпадут сразу много элементов. А если подходить вторым путём то будет выбран один и только один. Кажется что логика программы нарушается. Известен ли данный эффект?

[svv]

Не знаю, известен эффект или нет, но он понятен. По крайней мере, на одном шаге, действуя этими двумя методами, получаем неэквивалентные результаты.

Чтобы сделать программу эффективнее, но сохранить её поведение, надо в один шаг включать несколько выстрелов. Но число выстрелов $m$ само должно быть случайной величиной, принимающей значения от $0$ до $n$. Исходя из описания первого метода, с перебором всех элементов, $m$ должно иметь биномиальное распределение:

Википедия писал(а):

Биномиальное распределение в теории вероятностей — распределение количества «успехов» в последовательности из $n$ независимых случайных экспериментов, таких что вероятность «успеха» в каждом из них постоянна и равна $p$.

В Вашем первом методе (при котором поведение программы берется за эталонное) эксперимент — это принятие решения для одного элемента массива, нужно или нет его мутировать. А последовательность из $n$ независимых экспериментов — это перебор всех элементов массива.

В соответствии с формулой, вероятность того, что Вы для $m$ элементов из $n$ решите, что их надо мутировать, равна
$P(m)=\frac{n!}{m!(n-m)!}p^m (1-p)^{n-m}$
Во втором методе надо построить случайную величину с таким же распределением, на каждом шаге получать её случайное значение и потом делать количество выстрелов, равное этому значению.