Вероятность коллизий

[IndexOutOfRange]

Всем привет!

Есть интересная прикладная задача. Попробую ее перенести на язык математики. Я буду ее постепенно усложнять. Но начнем с простого. Может я пойму принцип и уже сам смогу ответить на более сложный вариант. Итак, имеется бесконечный источник шаров. Всего в этом источнике 300 уникальных шаров с номерами от 1 до 300. Будем считать, что шары распределены равномерно. Ну то есть вероянтность появления каждого шара одинакова. У нас есть 2 рабочих, которые постоянно берут шары из этого источника. Упростим задачу. Пусть они берут ровно 1 шар, что-то с ним делают 100 мс, потом берут следующий шар. Если вдруг рабочий №1 взял шар с номером 1, а в этот момент рабочий №2 уже работает с другим шаром с таким же номером, то он ждет 500 мс и снова пытается его обработать. Будем считать, что взять шар или првоерить, что он кем-то обрабатывается не требует времени. То есть на временной линии мы тратим время только на обработку или ожидание.

Вопросы:
1. Какова вероятность того, что возникнут коллизии. Кажется, что ответ $1/300$
2. Очевидно, что время ожидания влияет. Но можно ли сказать, что если время ожидания сделать строго больше, чем 100 мс, то вероятность станет постоянной, что для 150 мс, что для 200 мс? Интуитивно кажется, что уже нет никакой разницы. Но я в этом не уверен.

[sergey zhukov]

IndexOutOfRange
Смысл в том, что оба рабочих не должны одновременно работать над одинаковыми шарами? Если я взял тот же шар, что и у вас, то я стою и жду, пока вы не закончите с ним в надежде, что следующий ваш шар будет другим, и я смогу продолжить? Тогда нет смысла ждать больше 100 мс, вероятность коллизий будет постоянной ($\frac{1}{300}$)

[wrest]

IndexOutOfRange в сообщении #1612556 писал(а):

Всего в этом источнике 300 уникальных шаров с номерами от 1 до 300.

IndexOutOfRange в сообщении #1612556 писал(а):

Если вдруг рабочий №1 взял шар с номером 1, а в этот момент рабочий №2 уже работает с другим шаром с таким же номером,

Как-то у меня не связались эти два предложения. Если шары (номера) уникальны, то "другого шара с таким же номером" не существует.

[sergey zhukov]

wrest
Имеется ввиду "300 уникальных типов шаров". Источник бесконечен, как я понял.

[IndexOutOfRange]

sergey zhukov в сообщении #1612563 писал(а):

wrest
Имеется ввиду "300 уникальных типов шаров". Источник бесконечен, как я понял.

Да, все так, то есть может быть ситуация, что один рабочий взял шар с номеро 1 и другой рабочий тоже взял шар с номером 1. Это будут два разных шара, но номера будут одинаковые.

[mihaild]

Что такое "вероятность коллизии"? Вероятность того, что шар, который я только что взял, такой же как у напарника? Очевидно $1/300$, независимо от того, сколько времени напарник уже держит свой шар.
И что происходит, если оба работника берут шары с одинаковыми номерами одновременно? Или они шары берут по очереди (скажем первый в 00 миллисекунд каждой сотни секунд, а второв в 01)?

[IndexOutOfRange]

mihaild в сообщении #1612566 писал(а):

Что такое "вероятность коллизии"? Вероятность того, что шар, который я только что взял, такой же как у напарника? Очевидно $1/300$, независимо от того, сколько времени напарник уже держит свой шар.
И что происходит, если оба работника берут шары с одинаковыми номерами одновременно? Или они шары берут по очереди (скажем первый в 00 миллисекунд каждой сотни секунд, а второв в 01)?

Ну не совсем независимо от времени ожидания. Если мы будем ждать 50 мс, то у нас есть вероятность сделать вторую проверку, когда другой рабочий все еще не обработал свой шар и тогда это будет снова коллизия. Обрабатывает он его 100 мс.

[IndexOutOfRange]

mihaild в сообщении #1612566 писал(а):

Что такое "вероятность коллизии"? Вероятность того, что шар, который я только что взял, такой же как у напарника? Очевидно $1/300$, независимо от того, сколько времени напарник уже держит свой шар.
И что происходит, если оба работника берут шары с одинаковыми номерами одновременно? Или они шары берут по очереди (скажем первый в 00 миллисекунд каждой сотни секунд, а второв в 01)?

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

[wrest]

IndexOutOfRange в сообщении #1612579 писал(а):

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

А есть какой-то штраф за проверку после задержки? У вас написано, что

IndexOutOfRange в сообщении #1612556 писал(а):

Будем считать, что взять шар или првоерить, что он кем-то обрабатывается не требует времени

Почему тогда, например, не проверять каждую миллисекунду освободился шар или нет?

[mihaild]

IndexOutOfRange в сообщении #1612568 писал(а):

Ну не совсем независимо от времени ожидания

Я написал "шар, который я только что взял".
Если мы включаем еще и проверки, пока держим шар - то да, все интервалы проверок больше 100мс равнозначны, потому что если мы взяли шар, который сейчас у напарника, то распределение его шаров в любой период больше чем через 100мс одинаково.
С одновременностью еще нужно аккуратно, потому что если период проверок совпадает с периодом обработки, то возможна ситуация "Вася взял шар - Петя взял такой же шар - прошло 100мс - Петя проверил, и продолжает ждать - Вася взял новый шар" - Петя ждет лишние 100мс.

[IndexOutOfRange]

Усложняем задачу. Теперь у нас 3 рабочих. Вопросы:
- Какова вероятность коллизий теперь? Вроде бы 1 - (300/300 * 299/300 * 298/300), это приблизительно 1/100
- Как она зависит от времени ожидания?
- Какое самое оптимальное время ожидания?

[sergey zhukov]

IndexOutOfRange
Вероятность правильная. Время ожидания по прежнему 100 мс.

[IndexOutOfRange]

"Вроде бы 1 - (300/300 * 299/300 * 298/300), это приблизительно 1/100", походу я тут ошибся, все немного сложнее. Пусть 1A - означает, что 1 рабочий взял шар в обработку. И пусть 1W означает, что 1 рабочий ждет.
Тогда вероятность 1A - 300/300 = 1
Вероятность 1W = 0
Вероятность 2A = 1 * 299/300
Вероятность 2W = 1 * 1/300

В случае если произошли события 1A -> 2A, то:
- вероятность 3A = (1 * 299/300) * 298/300 = 89102/90000
- вероятность 3W = (1 * 299/300) * 2/300 = 598/90000

В случае если произошли события 1A -> 2W, то:
- Вероятность 3A = 300/300 * 1/300 * 299/300 = 1/300 * 299/300
- Вероятность 3W = 300/300 * 1/300 * 1/300 = 1/300 * 1/300

В итоге вероятности такие:
3A = 89102/90000 + 299/90000 = 89401/90000
3W = 598/90000 + 1/90000 = 599/90000

То есть вероятность коллизий будет P(1W) + P(2W) + P(3W) = 0 + 1/300 + 599/90000 = 899/90000. Вроде бы так.

-- 06.10.2023, 12:35 --

Да, эта вероятность не сильно отличается от 1 - (299/300 * 298*300), но она все же отличается. И не факт, что различие не станет расти при большем количестве рабочих. Или факт и можно пренебречь этими сложными расчетами?

[sergey zhukov]

IndexOutOfRange
А как, например, получается, что все три должны ждать? Т.е. P(3W)? Разве минимум один рабочий не работает в любых обстоятельствах?

Если задача стоит так: "Три человека взяли по случайному шару. Какова вероятность, что все шары разные?", то правильный ответ $\frac{300}{300}\frac{299}{300}\frac{298}{300}$. Но если совпадение есть, то оно может быть парным или тройным. В первом случае будет ждать один рабочий, во втором - два. Если за коллизию считать число ждущих рабочих в цикле, то да, нужно считать немного аккуратнее.

Можно так сформулировать: есть $m$ случайных величин, каждая из которых равномерно распределена на дискретном множестве $1...n$ ($m$ - число рабочих, $n$ - число типов шаров). Коллизия - это парное совпадение значений двух случайных величин. Если $k$ случайных величин приняли значение $a$, то число коллизий $K$ для этого случая равно числу разных парных комбинаций этих случайных величин, т.е. $K(k)=\frac{k^2-k}{2}$. Возможно, что, скажем, одна группа случайных величин приняла одинаковое значение $a$, а другая - одинаковое значение $b$. В этом случае число их коллизий внутри групп складывается, мы получаем $\sum\limits_{}^{}K$. Найти матожидание $\sum\limits_{}^{} K$ для заданных $m$ и $n$.

[IndexOutOfRange]

sergey zhukov в сообщении #1612674 писал(а):

IndexOutOfRange
А как, например, получается, что все три должны ждать? Т.е. P(3W)? Разве минимум один рабочий не работает в любых обстоятельствах?

Если задача стоит так: "Три человека взяли по случайному шару. Какова вероятность, что все шары разные?", то правильный ответ $\frac{300}{300}\frac{299}{300}\frac{298}{300}$. Но если совпадение есть, то оно может быть парным или тройным. В первом случае будет ждать один рабочий, во втором - два. Если за коллизию считать число ждущих рабочих в цикле, то да, нужно считать немного аккуратнее.

3W означает, что ждет рабочий под номером 3, а не то, что 3 рабочих одновременно ждут. И да, я по сути посчитал для 3 действий, берет 1-ый рабочий, берет 2-ой рабочий, берет 3-ий рабочий, но действия бесконечны. И интересует в среднем количество коллизий в такой системе. Даже упростим задачу - если рабочий ждет, то он ждет ровно момента завершения работы другого рабочего (чтобы исключить влияение ожидания и выровнять всех рабочих во временной сетке)

-- 06.10.2023, 14:02 --

Так как количество действий бесконечно, то начальным моментом, когда рабочие начинают брать шары можно пренебречь. Нас интересует вероятность того, что рабочий возьмет шар с номером, который уже в обработке. Если у нас $m$ рабочих и какой-то из рабочих пытается взять шар с номером $N$, то по сути вероятность коллизии - это вероятность того, что шар $N$ взят в обработку или находится в ожидании у хотя бы одного из остальных $m - 1$ рабочих.

То есть на каждом цикле имеем систему из 3 значений, где 3A - означает, что шар с номером 3 находится в обработке, а 5W - означает, что шар с номером 5 находит в ожидании на обработку.
Тогда на каждом цикле система выглядит как $(n_1S, n_2S, n_3S)$. S в данном случае это либо A, либо W. Потом каждый из рабочих пытается либо взять следующий шар в обработку, либо попытается обработать шар, который был в ожидании. Вроде бы не имеет значение в каком порядке они будут это делать, так что допустим от рабочего с номером 1 до рабочего с номером 3. Вопрос, какое количество W мы в среднем имеем на каждой итерации?