Как рассчитать ожидаемую частоту столкновений

Question

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

Учитывая то, что я знаю о созданииПредположения, подобные этому, я могу гарантировать, что пользователи будут влиять на действия одновременно.Тем не менее, я в недоумении относительно того, как вы на самом деле рассчитали бы ожидаемую частоту столкновений.

Например, если мы предположим, что каждый пользователь выполняет действие каждые 3 минуты, а наш таймер действительно с точностью до миллисекунды,Какова формула для расчета частоты столкновений?

Учитывая, что запись в Википедии для проблемы дня рождения может быть обобщена в формулу Где d - 180 000 миллисекунд, а p - вероятность столкновения.

Таким образом, по словам 3 пользователей, мы получаем вероятность 2,4996E-05 в любой заданный 3-минутный период, что происходит столкновение.

Тогда возникает вопрос, каковы шансы столкновения в течение дня?Так как 60- * 60 * 8/3 = 9600 3-минутных периодов в рабочем дне, вероятность столкновения в любой данный день составит 1 - ((1-2.4996E-05) ^ 9600) = 21%.Очень хороший шанс, что все станет грушевидным.

Answer 1

Через 3 минуты у вас будет 180000 миллисекунд.Если вы знаете количество пользователей, вы можете использовать вероятность парадокса дня рождения для определения вероятности столкновения.

Также учтите, что ваш таймер может быть не с точностью до миллисекунды,даже если это может быть измерено в миллисекундах.Многие таймеры основаны на тике, который запускается намного менее 1000 раз в секунду.

Answer 2

Чтобы получить частоту столкновений, просто получите вероятность столкновения в течение интервала 1 мс, а затем масштабируйте до любого интервала, который вам нравится (например, умножьте на 1000, чтобы получить столкновения в секунду).

Чтобы получить эту вероятность, получите вероятность столкновения no в течение интервала времени 1 мс?Это вероятность того, что число пользователей, действующих в течение этого интервала, равно 1 или 0.

Если существует n пользователей, и вероятность того, что конкретный пользователь действует в течение этого интервала времени, составляет p, то

P (0) = (1-p) ⁿ = 1 - np + n (n-1) p ² / 2 - ...
P (1) = np (1-p) ^n-1 = np - n (n-1) p ² + ...
P (0 или 1)= 1 - n (n-1) p ² / 2 + ...
P (более 1) = n (n-1) p ² / 2 +...

Теперь добавим несколько чисел: каждые 3 минуты дает p = 1,8x10 ^-5 , поэтому вероятность столкновения составляет примерно

n (n-1) (3.24x10 ^-10 )

Так что, если мои расчеты верны, если у вас будет 100 пользователей, вы будете получать примерно одно столкновение каждые десять минут.

Answer 3

3 минуты = 180 секунд = 180000. Назовите это M для миллисекунд.

Сколько у вас пользователей? Допустим, есть N.

За 3 минуты пользователь 1 сожирает миллисекунду - 180000 бесплатных, 180000 возможных - это 180000/180000 = 1 шанс на успех.

Следующий парень: 179999/180000 шансов получить хороший слот. Следующий парень: 179998/180000 шансов получить хороший слот.

Шансы на все это

 180000 * 179999 * 179998 . . .
--------------------------------
 180000 * 180000 * 180000 . . .

Короче говоря:

 N! / ((N^N)*(N-M)!)

Answer 4

CollisionFreqPercent = (AccuracySecs / (ActionDelaySecs / ConcurrentUsers)) * 100;

например:

1 пользователь = (0,001 / ((3 * 60) / 1)) * 100 = 0,00055% вероятности столкновения в любой момент времени

1000 пользователей = (0,001 / ((3 * 60) / 1000)) * 100 = 0,55% вероятности столкновения в любой момент времени

Answer 5

Ключевым моментом в этом вопросе является знание вероятности события, произошедшего за определенный интервал, и знание того, сколько времени потребуется для его завершения. Тогда вероятностью для обоих будет вероятность второго события, произошедшего в течение самого первого события, обусловленная вероятностью первого события.

Теперь вы можете вычислить это, в общем, на основе правила Байеса .