Задача по теории вероятности

sunni

Помогите доформализовать и решить задачу:
(Задача о профкоме) Есть m билетов в театр, есть N человек, (обязательно членов профкома желающих сходить в театр. Но эти N человек разбиты на K групп. В каждой группе ni человек, так что n1+n2+...nK=N. Люди из каждой группы хотят пойти в театр только вместе, поэтому они подают в профком "коллективную заявку" на ni человек. В результате в профкоме оказывается K коллективных заявок, и устраивается случайная лотерея между ними.
Вопрос: какой должна быть лотерея, чтобы справедливо распределять билеты? (скорее всего, понадобится несколько кругов однотипных лотерей с выбыванием победителей). Формализовать понятие справедливости в терминах вероятности. Пример: справедливость = вероятность выигрыша группы равна равномерной вероятности выигрыша одного человека(m/N умноженной на количество человек в группе.
Все изменения, дополнения, здравый флуд приветствуются.

Vlad128

А вот эти группы, они заданы силами свыше или люди сами решают, как в них объединяться? А то ведь тут два случая: либо вероятность победы группы не зависит от числа человек в ней, либо зависит. Причем если не зависит, то все совсем просто (справедливость на уровне групп). А если зависит, то если монотонно, то группы начнут объединяться там (это же профком!). И все же не ясно, в чем трудность. Тут же даже не формализация, а постановка хромает, чем не устраивает случайный равновероятный выбор между группами? Это убирает необходимость воротить кулуарные переговоры :) Просто победившая группа должна получать билеты ровно на себя, чтобы искусственным разделением не увеличивали вероятность победы. В общем, сначала надо понять про деление групп, потом, чем не устраивает равновероятный выбор, чем он не справедлив? Тем, что больше человек обламывается? Почему это плохо?

Vlad128

Во, кстати, предлагаю так:
ограничить число человек в группе сверху некоторым числом Z.
Подавшие заявки группы разделить по величине на несколько сегментов: не более z1, между z1 и z2 ... от z_n-1 до z_n = Z.
Ну и вероятность назначать исходя из того, к какому сегменту принадлежит число человек в этой группе. Можно даже несколько билетов разыграть, чтобы победить могли одновременно и большие и маленькие группы. Ну как, справедливо? Это еще не решение, конечно, просто идея.

sunni

Задача навеяна этой темой:
Равномерное распределение получается, если всякий желающий (нет никаких групп) с вероятностью m/N получает билет. Для этого достаточно вытянуть случайно m листочков из шляпы с N листочками.
Но что делать, если "чуве с барышней" хотят идти вместе и никак иначе? В принципе, если лотерея равномерная, они пойдут в театр с вероятностью m*(m-1) / (N*(N-1 . Встаёт вопрос: справедливо ли это? Предположим, что мы разрешим им объединиться и участвовать в равномерной лотерее как одно целое, но если лотерея выбирает и их, то они должны забрать два билета. Вот какая вероятность того, что они пойдут в таком случае в театр вместе. Очевидно, что просто равномерное распределение между N-1 участниками в лотерее не сработает, так как может оказаться, что на 1 билет претендуют 2 человека. Да и вообще, как должна проходить лотерея в случае K групп? Вдруг на всех членов одной группы не хватает билетов? То есть нужно либо учитывать порядок выпадения счастливых номеров, либо совсем другая лотерея. Самый главный вопрос задачи: каков реальный алгоритм проведения лотереи, чтобы осталось неиспользованными как можно меньше билетов, и чтобы все были довольны и сетовали лишь на судьбу.
Да, задача не поставлена корректно. Первый шаг к определенности - что есть справедливость здесь? Я предложил(и ошибся) выше следующий критерий: одному человеку вероятностно нет выгоды вступать вгруппы.

sunni

То есть идея такая: не должен 1 человек бороться за свой билет с той же вероятностью, что и 10 человек за десять билетов. Какой-то смысл в этом есть. Очень даже похоже на следующее: любой человек, вне зависимости от группы, имеет одинаковую вероятность выиграть по сравнению с другим.
Надо добавить, что сами люди должны хотеть разбиваться по группам не с целью выгоды в лотерее, а с какой-то другой целью. Например, если человек выигрывает билет, то он обязан пойти в театр. Бедный чуве в театре, да без барышни. Если он не пойдет в театр, его, скажем, в бан-лист профкома ставят.

Badyss

а вот если в твоей модели будет такая ситуация:
есть 3 места в театр и подано 3 заявки:
З1: на 2 человека
З2: на 2 человека
З3: на 1 человека
Получается что З3 будет удовлетворена в 100% случаев, а вот З1 и З2 с вероятностью 1/2 .
Это у тебя будет считаться справедливым?

Badyss

чисто как вариант:
1) мы считаем вероятность похода в театр, как если бы все заявки были на одного человека, то есть m/N
2) Мы берем самую большую по численности группу. Кидаем какой-то жребий. В итоге с вероятностью m/N все члены группы идут в театр, а с вероятностью 1-m/N не идёт никто
После этого берутся оставшиеся билеты и выбирается оставшаяся наибольшая группа.
Легко придумать контрпримеры когда это будет несправедливо или когда останется много свободных мест. Но - се ля ви...
PS. да и вероятности для жребия, те которые в начале m/N наверное всё же придётся пересматривать каждый раз

serguei

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

sunni

А вы как считаете? Любая лотерея, справедливая и нет, обеспечивает З3 билет в театр.Мы исходим из того, что группа хочет билеты сразу на всех. Люди из группы не хотят идти в театр даже без одного своего члена.

sunni

:) Это уже не халява получается, Остап Б. недоволен.
А вообще, если я себя правильно понял, в одной заявке указано может быть более одного человека, так что докупать надо больше билетов.

serguei

ну считай у меня 1 заявка=1 человек.

serguei

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

sunni

Почему не Вам? Как раз Вам, но дело в том, что справедливость вероятностная, в каждом конкретном розыгрыше будут разочарованные. но разочарованные в судьбе, случае, а не в молодых коррупционерах из профкома.

serguei

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

sunni

Дело не в халяве, а в трудновыполнимости профкомом процесса докупки билетов. Мы хотим предложить опк,студкомам, и всем-всем-всем эту процедуру. Правда, имеет смысл только, если они открывают информацию о количестве билетов. Иначе - бессмысленно.
Можно считать, что это есть задача о распределении данного дискретного ресурса между сторонами с разными потребностями.

sunni

Обсудим справедливость. Забудем про группы, даны N человек. Среди них будет организована случайная лотерея, m человек выиграют билеты. Но среди них оказалось, скажем, три чуве, барышни которых не выиграли билеты, а чуве, как и раньше, хотят идти только с барышней своей. Они вроде бы должны отказаться от своих билетов, и эти билеты должны снова быть разыграны в случайной лотерее между остальными участниками. При этом три барышни также выбывают, так как их чуве вышли из конкурса, а без них им билеты не нужны. Или же одного чуве лишать билета(случайно) и разрешить остальным двум барышням участвовать в лотерее на него? Какой из вариантов вы считаете справедливым?

shpanenoc

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

sunni

Да, я как раз думал о такой схеме, только вместо среднего арифметического номеров - максимальный номер среди всех членов группы. Получается типа русского лото, когда у каждой группы есть карточка с номерами всех членов, случайно друг за другом вытаскиваются номера. Первая группа, закрывшая все поля своей карточки, получает билеты на всю группу. если недостаточно билетов на очередную группу - пропускаем полностью.
Теперь надо посчитать вероятности выигрышей. Сравнить два вида лотерей между собой и с равномерной лотереей. Если сложно обсчитать вероятностное пространство, то предлагаю для начала рассматривать группы из одного или двух членов.

serguei

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

sunni

Очень неплохо, правильно ли я понимаю алгоритм: раздали участникам баллы, присвоили членам групп их средний бал: b1,b2,...,bK (K групп, по неубыванию баллов). Далее определяем проходной балл по итерации: для самых удачливых групп, таких что bK=b(K-1)=..=b(K-i+1 b(K-i)<b(K-i+1 выдаем их билеты количеством nK +..+n(K-i+1 если это количество небольше количества билетов; если же нет, то ничего не даём этим группам. Повторяем дальше эту итерацию для оставшихся групп с оставшимся количеством билетов, пока не кончатся билеты или группы.
Мне кажется странным, что люди не получают билета в результате случайной лотерее только потому, что ещё много людей получило такой же балл, а он может быть даже максимальным.
И ещё раз: кто может пояснить как должна выглядеть равномерная лотерея, но когда чуве отказывается от своего билета, если барышня не получила билет.

Vlad128

захрена среднее-то, если можно сразу все команды упорядочить в произвольном порядке? :) Распределение-то такое же получается.

sunni

Честно говоря, я не догоняю в конце рабочего дня почему это так.
Если бы была сумма большого числа случайных величин, то понимаю. а когда среднее двух-трех случайных величин?Эти случаи нам и важны.

shpanenoc

В идеальном случае нам бы хотелось (МНЕ бы хотелось чтобы независимо от того, какой размер группы, в которой состоит данный конкретный человек, вероятность его получить билет составляла бы m/N. Но это невозможно!
В качестве примера - тривиальный случай, N=3, две группы 1+2 и 3, 2 билета.
Вероятность 3 получить билет - p Вероятность 1 и 2 получить билеты - очевидно, 1-p, т.к. они получат билеты тогда и только тогда, когда их не получит 3.
p = 1-p = 2/3 - невозможно.
Продолжаем. Если мы каждому человеку назначает номер, а затем группе присваиваем МИНИМУМ номеров ее членов - то p = 1/3, т.к. 3 пойдет только тогда, когда у него номер 1.
Если группе присваиваем МАКСИМУМ номеров членов, то p = 2/3, т.к. 3 пойдет тогда, когда его номер 1 или 2.
Если группе присваиваем среднее арифметическое, то p = 1/2, т.к. 3 пойдет, если его номер 1 и пойдет с вероятностью 1/2, если его номер 2.
Я начинаю подозревать, что оптимально назначать группе максимум, потому что в противном случае вероятность пойти на концерт одиночек составляет меньше m/N, а это "негоже" позволять. Но я это не доказал еще, конечно, это только догадка.

shpanenoc

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

serguei

да, можно и так.

serguei

почему ущемляются права одиночек?

shpanenoc

Рекомендую читать мои вычисления выше.

serguei

ок, я поняла, что ты про свои пишешь, сначала подумала, что про мой пост.

sunni

Хотел бы обсудить алгоритм суперсправедливой, идеальной лотереи.
Кроме справедливости, требуем рациональности="халява не должна тратиться впустую", то есть после лотереи должно остаться как можно меньше неиспользованных билетов. К сожалению, существуют простые примеры, когда билеты точно останутся(нечётное количество билетов и чётное количество человек в любой группе).
Лотерея проводится так. Формально забываем о группах и проводим равномерную лотерею среди N человек. Получилось разделение на m удачников и (N-m) неудачников. Теперь вспоминаем о группах. Группы, которые целиком попали в удачники, получает свои билеты, и нас в дальнейшем не интересуют. Заметим лишь, что получили они свои билеты в равной, "справедливой" борьбе с остальными.
Рассмотрим теперь тех удачников, чьи группы имеют участников-неудачников. Таких удачников пусть будет t, t<m. Что делать с такими удачниками? Они выиграли билет, но пойти не могут без своих групп. Раньше делали так: t участников должны отказаться от билетов своих в пользу неудачников. Но при этом вылетают из лотереи не только t удачников, но и все группы, в которых они состоят. И возможна ситуация, когда эти t билетов уже некому раздавать, так как неудачники все выбыли.
Предлагается следующее: не все t человек лишаются билета. а только один случайным образом. Этот один человек не исключается из лотереи, а становится неудачником. Освободившийся билет разыгрывается в равномерной лотерее среди неудачников. Победитель переводится в удачники. Проверяем, появилась(!) ли группа, целиком состоящая из удачников. Если да, выдаем ей билеты. Потом процесс повторяется, пока не останется такое количество билетов, что оно уж точно не поможет попасть в удачники целиком никакой группе.
Я считаю, что этот алгоритм справедлив, но обладаем сильным минусом: количество итераций может быть большим. На этом этапе, думаю, можно говорить о формализованности задачи. Есть алгоритм, честный, но долгий, вопрос: какой должна быть лотерея, чтобы было также честно, но быстрее.

shpanenoc

не все t человек лишаются билета. а только один случайным образом. Этот один человек не исключается из лотереи, а становится неудачником.
Всех так, почему один? И задача свелась к предыдущей. Должно итераций меньше стать.
Только что-то мне подсказывает, что этот алгоритм аналогичен одному из приведенных выше, где ранг группы = max(рангов участников).

sunni

Этим выделяется самая первая равномерная лотерея как важная. Моделируется, по сути, ситуация: трое чуве с билетами, а их барышни без. Тогда один чуве благородно отдают другу (точнее, барышне его) свой билет. Все счастливы, кроме третьего чуве.
Вместо дружественных отношений мы вводим случайность. Случайно определяем, кто сделает благородный жест.
Суть всего такая. мы не лишаем всех сразу билетов, потому что одна группа, возможно, после первой лотереи, выиграла больше билетов, чем другая, а мы, лишая всех, уравниваем эти группы. Тут, как бы, история успеха важна.
Мне тоже кажется, что похоже. Было бы совсем хорошо.

shpanenoc

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

sunni

У меня пока не получилось хоть как-то упростить суперсправедливую лотерею до лотереи с меньшим количеством итераций, но такую же вероятностно. В общем, up.
Оставить комментарий
Имя или ник:
Комментарий: