Я не спец в теории вероятности, так только поверхностно. Поэтому прошу не кидать камнями если есть
какие-то фундаментальные неточности.
Задача: Равновероятно случайно перераспределить деньги между 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: Как максимально честно но случайно перераспределить деньги между 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 персонами
C0x>Задача: Равновероятно случайно перераспределить деньги между N персонами.
C0x>Например есть 10 человек. Изначально у каждого по 10$. На каждой итерации нужно случайно перераспределить деньги. C0x>Но чтобы вероятность получить одну и ту же сумму у каждого была одинаковой.
Поставим все эти 10 человек в круг.
Бегаем по кругу.
Перед каждым челом бросаем монетку.
Выпал орел — отдаем 1 (один) бакс.
Выпала решка — бегим дальше.
Бегаем до тех пор, пока не раздадим все деньги.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
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$.
Это решение удовлетворяет условию.
Более того, условию будет удовлетворять даже такой алгоритм:
1. Кладем все деньги в общую кучу размера 100$.
2. Берем случайного человека.
3. Даем ему всю сумму — 100$.
4. Остальные 9 человек обламываются.
Получается у всех одинаковая вероятность получить одну и ту же сумму:
f($0) = 0.9
f($100) = 0.1
Главное гармония ...
Re[2]: Как максимально честно но случайно перераспределить деньги между 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]: Как максимально честно но случайно перераспределить д
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, 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. нормируем.
Почему это решает проблему равномерности, я что-то до конце не въехал.
Но все же.
Если учесть что числа целые, то будет еще один уровень
Здравствуйте, C0x, Вы писали:
... C0x>Очевидно что если я беру и случайно делаю первую выборку от 0 до 100, то все последующие выборки будут ограничены величиной первой. C0x>Я не хочу, чтобы первая выборка вообще оказывала какое-либо влияние на последующие. Это я считаю наиболее честное распределение будет.
Таким образом, ты хочешь изменить критерий "случайность" в пользу критерия "честность". Почему? И если быть честным важнее — зачем, вообще, распределять с элементом случайности?
Re[3]: Как максимально честно но случайно перераспределить деньги между N персон
M>>Получается у всех одинаковая вероятность получить одну и ту же сумму:
C0x>Формулировка у меня неточная. Может так правильнее будет: хотелось что-бы доля, C0x>которую получит каждый не зависела от долей которые получат другие.
Это невозможно, если доли случайны и сумма долей должна быть равна единице (если раздать все $100).