Здравствуйте, C0x, Вы писали:
C0x>Я не спец в теории вероятности, так только поверхностно. Поэтому прошу не кидать камнями если есть C0x>какие-то фундаментальные неточности.
C0x>Задача: Равновероятно случайно перераспределить деньги между N персонами.
C0x>Например есть 10 человек. Изначально у каждого по 10$. На каждой итерации нужно случайно перераспределить деньги. C0x>Но чтобы вероятность получить одну и ту же сумму у каждого была одинаковой.
Выделенное — единственное строгое условие задачи.
C0x>Пример не правильного распределения:
C0x>1. Кладем все деньги в общую кучу размера 100$. C0x>2. Берем случайного человека. C0x>3. Даем ему случайную сумму от 0 до 100$. Например 100$. C0x>4. Остальные 9 человек обламываются, т.к. делить остается 0$.
Это решение удовлетворяет условию.
Более того, условию будет удовлетворять даже такой алгоритм:
1. Кладем все деньги в общую кучу размера 100$.
2. Берем случайного человека.
3. Даем ему всю сумму — 100$.
4. Остальные 9 человек обламываются.
Получается у всех одинаковая вероятность получить одну и ту же сумму:
f($0) = 0.9
f($100) = 0.1
Главное гармония ...
Re: Как максимально честно но случайно перераспределить деньги между N персонами
C0x>Задача: Равновероятно случайно перераспределить деньги между N персонами.
C0x>Например есть 10 человек. Изначально у каждого по 10$. На каждой итерации нужно случайно перераспределить деньги. C0x>Но чтобы вероятность получить одну и ту же сумму у каждого была одинаковой.
Поставим все эти 10 человек в круг.
Бегаем по кругу.
Перед каждым челом бросаем монетку.
Выпал орел — отдаем 1 (один) бакс.
Выпала решка — бегим дальше.
Бегаем до тех пор, пока не раздадим все деньги.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[3]: Как максимально честно но случайно перераспределить д
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, bnk, Вы писали:
bnk>>Генериуешь последовательность из 10 случайных чисел от 0 до 1, потом нормируешь (умножаешь на K), чтобы сумма сошлась?
К>Неравномерное распределение получается. К>Начать с того, что многим наборам исходных чисел соответствует один результат: {0.1, 0.1, ..., 0.1} <=> {0.2, 0.2, ..., 0.2} <=> ... <=> {1.0, 1.0, ..., 1.0} К>А одному набору {0, 0, ..., 0} вообще ничего не соответствует.
К>Вообще, в 10-мерном единичном гиперкубе есть 9-мерная поверхность — x1+...+x10=1 (грань симплекса). К>Дальше надо подумать и вспомнить тервер.
Ага, и правда. На stackoverflow приводится "фикс" на это дело.
1. Берем не N, а N-1 случайных чисел от 0 до 1.
2. добавляем 0 и 1.
3. сортируем
4. в качестве набора N берем расстояния между соседними.
5. нормируем.
Почему это решает проблему равномерности, я что-то до конце не въехал.
Но все же.
Если учесть что числа целые, то будет еще один уровень
Я не спец в теории вероятности, так только поверхностно. Поэтому прошу не кидать камнями если есть
какие-то фундаментальные неточности.
Задача: Равновероятно случайно перераспределить деньги между N персонами.
Например есть 10 человек. Изначально у каждого по 10$. На каждой итерации нужно случайно перераспределить деньги.
Но чтобы вероятность получить одну и ту же сумму у каждого была одинаковой.
Пример не правильного распределения:
1. Кладем все деньги в общую кучу размера 100$.
2. Берем случайного человека.
3. Даем ему случайную сумму от 0 до 100$. Например 100$.
4. Остальные 9 человек обламываются, т.к. делить остается 0$.
Примерно правильное решение у меня уже складывается, но пока сформулировать затрудняюсь. Поэтому решил попросить помощи ).
Re: Как максимально честно но случайно перераспределить деньги между N персонами
Здравствуйте, C0x, Вы писали:
C0x>Например есть 10 человек. Изначально у каждого по 10$. На каждой итерации нужно случайно перераспределить деньги. C0x>Но чтобы вероятность получить одну и ту же сумму у каждого была одинаковой.
Произвольно разбиваем $100 на 5 кучек (разбиение должно быть одинаковым при каждой раздаче), рандом сорт, раздаём.
Re[2]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, Sinix, Вы писали:
S>Здравствуйте, C0x, Вы писали:
C0x>>Например есть 10 человек. Изначально у каждого по 10$. На каждой итерации нужно случайно перераспределить деньги. C0x>>Но чтобы вероятность получить одну и ту же сумму у каждого была одинаковой. S>Произвольно разбиваем $100 на 5 кучек (разбиение должно быть одинаковым при каждой раздаче), рандом сорт, раздаём.
Что значит разбиение должно быть одинаковым при каждой раздаче? Если произвольно разбивать на 5 кучек то как я показал в примере
может получится 1 кучка размером 100$ и пять кучек размера 0$. Как избавиться от таких разбиений?
Re: Как максимально честно но случайно перераспределить деньги между N персонами
Здравствуйте, C0x, Вы писали:
C0x>Я не спец в теории вероятности, так только поверхностно. Поэтому прошу не кидать камнями если есть C0x>какие-то фундаментальные неточности.
C0x>Задача: Равновероятно случайно перераспределить деньги между N персонами.
C0x>Например есть 10 человек. Изначально у каждого по 10$. На каждой итерации нужно случайно перераспределить деньги. C0x>Но чтобы вероятность получить одну и ту же сумму у каждого была одинаковой.
C0x>Пример не правильного распределения:
C0x>1. Кладем все деньги в общую кучу размера 100$. C0x>2. Берем случайного человека. C0x>3. Даем ему случайную сумму от 0 до 100$. Например 100$. C0x>4. Остальные 9 человек обламываются, т.к. делить остается 0$.
C0x>Примерно правильное решение у меня уже складывается, но пока сформулировать затрудняюсь. Поэтому решил попросить помощи ).
Смотря что считать "наиболее равномерным". Можно кинуть жребий и отдать все одному, можно раздавать по кругу по определенной сумме в случае если выпал жребий.
Программа – это мысли спрессованные в код
Re[2]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, Qulac, Вы писали:
Q>Смотря что считать "наиболее равномерным". Можно кинуть жребий и отдать все одному, можно раздавать по кругу по определенной сумме в случае если выпал жребий.
Очевидно что если я беру и случайно делаю первую выборку от 0 до 100, то все последующие выборки будут ограничены величиной первой.
Я не хочу, чтобы первая выборка вообще оказывала какое-либо влияние на последующие. Это я считаю наиболее честное распределение будет. Но как это
реализовать пока не могу сообразить.
Вот что я считаю правильным: cлучайно выбрать 10 чисел, каждое от 0 до 100.
Например выборка [100, 100, 50, 70, 20, 25, 40, 50, 100, 43].
В этом случае я считаю что 1, 2, 9-й чуваки получат одинаковую сумму и эта сумма будет явно больше, чем у всех остальных,
но она не будет равна 100, а будет вычисляться из с учетом результатов полученных для остальных чуваков.
Re[2]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, bnk, Вы писали:
bnk>Здравствуйте, C0x, Вы писали:
bnk>Генериуешь последовательность из 10 случайных чисел от 0 до 1, потом нормируешь (умножаешь на K), чтобы сумма сошлась?
Вот жеж..., про нормирование то я и забыл. Это и есть решение. Спасибо!
Re[2]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, bnk, Вы писали:
bnk>Генериуешь последовательность из 10 случайных чисел от 0 до 1, потом нормируешь (умножаешь на K), чтобы сумма сошлась?
Неравномерное распределение получается.
Начать с того, что многим наборам исходных чисел соответствует один результат: {0.1, 0.1, ..., 0.1} <=> {0.2, 0.2, ..., 0.2} <=> ... <=> {1.0, 1.0, ..., 1.0}
А одному набору {0, 0, ..., 0} вообще ничего не соответствует.
Вообще, в 10-мерном единичном гиперкубе есть 9-мерная поверхность — x1+...+x10=1 (грань симплекса).
Дальше надо подумать и вспомнить тервер.
Перекуём баги на фичи!
Re: Как максимально честно но случайно перераспределить деньги между N персонами
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, bnk, Вы писали:
bnk>>Генериуешь последовательность из 10 случайных чисел от 0 до 1, потом нормируешь (умножаешь на K), чтобы сумма сошлась?
К>Неравномерное распределение получается.
Главное что оно честное (равно-вероятное)
Re[2]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, C0x, Вы писали:
К>>Неравномерное распределение получается.
C0x>Главное что оно честное (равно-вероятное)
В том и дело, что не равновероятное.
А то можно взять N произвольных денежных векторов, где N вообще конечное, например, { (1,0,0...,0) и (0.1,0.1,...,0.1) } и равно-вероятно выбирать между ними.
Что в этом честного?
Равновероятное — это берём всё множество решений x1+...+x10=1, например, с дискретностью по 0.01, и равновероятно случайно выбираем между ними.
Перекуём баги на фичи!
Re[2]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, Кодт, Вы писали:
К>В том и дело, что не равновероятное. К>А то можно взять N произвольных денежных векторов, где N вообще конечное, например, { (1,0,0...,0) и (0.1,0.1,...,0.1) } и равно-вероятно выбирать между ними. К>Что в этом честного?
Равновероятное, так как мы для каждого чувака выбираем долю (от 0 до 1) с одинаковой вероятностью или не?
Это тоже самое, что выбирать из бесконечного числа векторов (x1, ..., xN), где x в диапазоне от 0 до 1.
Потом эти доли нормируем, тут вроде бы как ничто не портит равновероятность.
К>Равновероятное — это берём всё множество решений x1+...+x10=1, например, с дискретностью по 0.01, и равновероятно случайно выбираем между ними.
а разве это не тоже самое что выбирать из бесконечного множества векторов указанных мной выше?
Re[3]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, C0x, Вы писали:
... C0x>Очевидно что если я беру и случайно делаю первую выборку от 0 до 100, то все последующие выборки будут ограничены величиной первой. C0x>Я не хочу, чтобы первая выборка вообще оказывала какое-либо влияние на последующие. Это я считаю наиболее честное распределение будет.
Таким образом, ты хочешь изменить критерий "случайность" в пользу критерия "честность". Почему? И если быть честным важнее — зачем, вообще, распределять с элементом случайности?
Re[3]: Как максимально честно но случайно перераспределить деньги между N персон
M>>Получается у всех одинаковая вероятность получить одну и ту же сумму:
C0x>Формулировка у меня неточная. Может так правильнее будет: хотелось что-бы доля, C0x>которую получит каждый не зависела от долей которые получат другие.
Это невозможно, если доли случайны и сумма долей должна быть равна единице (если раздать все $100).
Главное гармония ...
Re[4]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, 1303, Вы писали:
1>Таким образом, ты хочешь изменить критерий "случайность" в пользу критерия "честность".
Случайность заменяю в пользу равновероятности.
1>Почему? И если быть честным важнее — зачем, вообще, распределять с элементом случайности?
Допустим 10 человек играют в игру. Скидываются по 10 баксов. И перераспределяют деньги. Интерес играть в игру, такой, что каждый отдельно взятый
игрок может хорошо подзаработать, но может и продуть. Деньги перераспределяются случайно. Честность тут состоит в том, что каждый должен иметь
одинаковый шанс получить любую сумму от 0..100. То есть вариант когда выбирается случайный игрок и получает случайно 100$ не прокатывает, т.к.
все остальные игроки уже не играют так как делить больше нечего.
Равномерность распределения тут так же не играет никакой роли, вполне допустима и такая раскладка (100, 0, 0, 0...,0).
Re[5]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, C0x, Вы писали:
C0x>Допустим 10 человек играют в игру. Скидываются по 10 баксов. И перераспределяют деньги. Интерес играть в игру, такой, что каждый отдельно взятый C0x>игрок может хорошо подзаработать, но может и продуть. Деньги перераспределяются случайно. Честность тут состоит в том, что каждый должен иметь C0x>одинаковый шанс получить любую сумму от 0..100. То есть вариант когда выбирается случайный игрок и получает случайно 100$ не прокатывает, т.к. C0x>все остальные игроки уже не играют так как делить больше нечего. C0x>Равномерность распределения тут так же не играет никакой роли, вполне допустима и такая раскладка (100, 0, 0, 0...,0).
Тогда с нормировкой равномерно-случайного вектора в гиперкубе дело не пойдёт. Потому что значения, близкие к 0.1, будут гораздо более вероятны, чем значения, близкие к 1 и даже к 0.
Простой пример, рассмотрим 3-мерный случай. Пространственное воображение работает хорошо?
Берём куб.
Пространство искомых векторов — это треугольник между диагоналями XY, YZ, XZ.
Процедура нормировки — проводим линию от точки 0 до (случайно выбранной) точки в кубе, находим пересечение этой линии с плоскостью треугольника.
Плотность вероятности каждого решения, поскольку точки куба равновероятны, равна длине луча, проходящего через 0 и данную точку треугольника, и до границы куба.
Очевидно, что чем ближе к ребру куба (и углу треугольника), тем эти лучи короче, а чем ближе к главной диагонали (и центру треугольника), тем длиннее.
То есть, самое вероятное решение — это (1/3, 1/3, 1/3).
Чтобы найти плотность вероятности значений одной компоненты, проведём в треугольнике изолинию. Через неё проходят лучи из 0, образующие плоскость. Эта плоскость, пересекая куб, даёт
— линию — ребро куба (для значения 1)
— квадрат — грань куба (для значения 0)
— 3-, 4- или даже 5-угольник (для промежуточных значений)
Лень считать, но суть проста: значение "1" имеет НУЛЕВУЮ плотность вероятности, а где-то посередине между 0 и 1 есть максимум.
Помня о проклятии размерности, легко предположить, что в 10-мерном кубе ситуация ещё более острая, и пик вероятности будет именно около 0.1, а все остальные значения почти невероятны.
Перекуём баги на фичи!
Re[5]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, C0x, Вы писали:
C0x>Честность тут состоит в том, что каждый должен иметь одинаковый шанс получить любую сумму от 0..100.
На самом деле, это в принципе несбыточно.
Рассмотрим пространство решений x1+...+x10 = 100. Для простоты, пусть оно будет дискретно.
Вероятность Pi(v) — вероятность того, что xi = v.
Мы желаем, чтобы Pi(0)=...=Pi(100) = 1/101.
Таким образом,
— или неравномерность величины выигрыша
— или несимметричность
или неравномерность и несимметричность, но за такое дело точно канделябром дадут!
Перекуём баги на фичи!
Re[6]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, C0x, Вы писали:
C0x>>Честность тут состоит в том, что каждый должен иметь одинаковый шанс получить любую сумму от 0..100.
К>На самом деле, это в принципе несбыточно.
К>Рассмотрим пространство решений x1+...+x10 = 100. Для простоты, пусть оно будет дискретно. К>Вероятность Pi(v) — вероятность того, что xi = v. К>Мы желаем, чтобы Pi(0)=...=Pi(100) = 1/101.
К>Обозначим P(v1,...,v10) вероятность определённой раскладки.
К>P1(100) = P(100,0,0,...,0) К>P1(0) = P(0,100,0,...,0) + P(0,0,100,...,0) + ... + P(0,0,...,100) + P(0,99,1,...,0) + ... К>P1(0) = P2(100) + P3(100) + ... + P10(100) + P(.....)....
К>Получается, P(100) = (по нашему желанию) = P(0) = (по требованию симметрии) = 10*P(100)+Q К>P(100) = 10*P(100) + Q К>0 = 99*P(100) + Q К>ой. Вероятности-то положительные!
Так что получается, что P1(100) != P2(0)? Или вероятность P(x11....x1n) != P(x21....x2n)?
Re[7]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, C0x, Вы писали:
C0x>Так что получается, что P1(100) != P2(0)? Или вероятность P(x11....x1n) != P(x21....x2n)?
Вероятности конкретных векторов P(.....) могут различаться, но вероятности событий для каждого участника Pi(v) — мы хотели, чтобы они были одинаковы для всех участников, P1(v)=P2(v)=...=P10(v), и ещё, чтоб они были вообще одинаковы, Pi(0)=Pi(1)=...=Pi(100).
Вот я и показал, что эти условия одновременно достичь невозможно.
Можно обеспечить симметрию по участникам, но распределение выигрышей всё равно будет неодинаковым: максимальная вероятность — остаться при своих; и исчезающе малая — сорвать банк.
Перекуём баги на фичи!
Re[8]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, Кодт, Вы писали:
К>Вероятности конкретных векторов P(.....) могут различаться, но вероятности событий для каждого участника Pi(v) — мы хотели, чтобы они были одинаковы для всех участников, P1(v)=P2(v)=...=P10(v), и ещё, чтоб они были вообще одинаковы, Pi(0)=Pi(1)=...=Pi(100). К>Вот я и показал, что эти условия одновременно достичь невозможно.
Ага, вроде бы интуитивно это тоже понял. По сути мы изначально равновероятно всем выдали какую-то сумму от 0 до 100, но потом когда нормируем, вероятности получения этих сумм меняются
в зависимости от сумм которые получили остальные игроки при равновероятном распределении. То есть тут уже вероятность получения конкретной суммы конкретным игроком зависит от сумм
которые получены остальными на первом шаге.
К>Можно обеспечить симметрию по участникам, но распределение выигрышей всё равно будет неодинаковым: максимальная вероятность — остаться при своих; и исчезающе малая — сорвать банк.
То есть если число экспериментов стремиться к бесконечности, то сумма с которой останется конкретный игрок стремится к его изначальной сумме с которой он пришел?
Re[9]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, C0x, Вы писали:
К>>Можно обеспечить симметрию по участникам, но распределение выигрышей всё равно будет неодинаковым: максимальная вероятность — остаться при своих; и исчезающе малая — сорвать банк. C0x>То есть если число экспериментов стремиться к бесконечности, то сумма с которой останется конкретный игрок стремится к его изначальной сумме с которой он пришел?
Нет. Если казино не имеет интереса, а игроки симметричны, то в любом случае, бесконечно наигравшись, игрок уйдёт с изначальной суммой.
Даже если мы оставим в пространстве векторов только (100,0,...,0) или, например, (33,33,33,1,0,...,0).
В этом случае, понятное дело, искусственно задраны вероятности 0, 100, или 0,33,1 — но никак не 10.
Перекуём баги на фичи!
Re: Как максимально честно но случайно перераспределить деньги между N персонами
Здравствуйте, C0x, Вы писали: C0x>Например есть 10 человек. Изначально у каждого по 10$. На каждой итерации нужно случайно перераспределить деньги. C0x>Но чтобы вероятность получить одну и ту же сумму у каждого была одинаковой.
"закольцевать десятку" и выбрать на кольце 5 точек равномерно распределенных. полученные отрезки мне кажется удовлетворяют условиям.
Re[2]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, __kot2, Вы писали:
__>Здравствуйте, C0x, Вы писали: C0x>>Например есть 10 человек. Изначально у каждого по 10$. На каждой итерации нужно случайно перераспределить деньги. C0x>>Но чтобы вероятность получить одну и ту же сумму у каждого была одинаковой. __>"закольцевать десятку" и выбрать на кольце 5 точек равномерно распределенных. полученные отрезки мне кажется удовлетворяют условиям.
А можно пример? А то не могу въехать в идею.
Re[3]: Как максимально честно но случайно перераспределить деньги между N персон
Здравствуйте, C0x, Вы писали: C0x>А можно пример? А то не могу въехать в идею.
пока мылся в душе сообразил что мы можем выбрать первое место разреза ноль и даже в круг сворачивать отрезок не нужно
в общем, идея такова. вот у нас есть окружность, длина которой равна 10. мы берем эту окружность рассекаем на 5 частей выбирая точки рассечения произвольно равновероятно. получим несколько кусков окружности. суммарная длина их равна 10. какой-то корреляции их длин друг с другом, кроме суммарной, я не вижу. а значит, это по ходу то, что нам надо.
Re[4]: Как максимально честно но случайно перераспределить д
если формализовать, то это наверное универовская задачка типа
ест вот там n точек принадлежащие равномерн распред. от 0 до 1 докжите что
x(1) — 0, x(2) — x(1) ... 1 — x(n) где x(i) порядковые статистики (или как их там) принадлежат равномернму распределению от 0 до 1/n
но я фиг знает как это делать — больше 10 лет назад подобное решал. ну и конечно всега есть шанс подвоха. вдруг это не так но по ходу так
Здравствуйте, C0x, Вы писали:
C0x>Например есть 10 человек. Изначально у каждого по 10$. На каждой итерации нужно случайно перераспределить деньги. C0x>Но чтобы вероятность получить одну и ту же сумму у каждого была одинаковой.
Решение за O(M), где M — общее количество денег:
1) все деньги в одну кучу;
2) берем по 1$ из общей кучи и равновероятно (P = 1 / N) решаем, кому отдать;
3) продолжать, пока деньги в общей куче не закончатся.
Распределение денег у некоторого человека в таком случае есть просто биномиальное распределение с p = 1 / N.
Re: Как максимально честно но случайно перераспределить деньги между N персонами
Пишем на 10 бумажках имя персоны. Для каждого одного доллара из ста тянем жребий-бумажку кому из персон этот доллар достанется.
А, в принципе похожее уже предлагали
Здравствуйте, beyv, Вы писали:
B>Здравствуйте, C0x, Вы писали:
B>Пишем на 10 бумажках имя персоны. Для каждого одного доллара из ста тянем жребий-бумажку кому из персон этот доллар достанется.
Ух ты, даже работает
#include "stdafx.h"
#include <stdlib.h>
#include <time.h>
int _tmain(int argc, _TCHAR* argv[])
{
int persons[10] = { 0 };
srand((unsigned)time(NULL));
for (int i = 0; i < 100 ; i++){
int n = rand() * 10 / RAND_MAX;
n = __min(9, __max(0, n));
persons[n]++;
}
return 0;
}
Здравствуйте, C0x, Вы писали:
LVV>>Бегаем до тех пор, пока не раздадим все деньги.
C0x>Тут все-таки хотелось бы не за O(N*M) а все-таки за O(N), т.к. N значительно меньше, чем M. C0x>N — кол-во чуваков, M кол-во денег суммарно.
Метод, предложенный Лаптевым, дает распределение Бернулли, которое в пределе стремится к нормальному.
То есть, аналогичное решение можно получить, сгенерировав N случайных чисел по нормальному(гауссовому) распределению, с центром M/N и произвольной сигмой.
На питоне это будет типа
import numpy as np
N=10 #number of players
M=100. #total money
s=1.0 #default standard deviation
np.random.normal(M/N, s, N)
А если надо самому, то из десяти равномерно распределенных чисел(стандартный рэндом) 10 нормально-распределенных делаются вот этой формулой.
Там, правда, общая сумма, скорее всего, чуть-чуть не сойдется — но разницу можно равномерно поделить между игроками.
хотел уже на боковую
папаху снял и сапоги
но в комментариях проснулись
враги