Я не спец в теории вероятности, так только поверхностно. Поэтому прошу не кидать камнями если есть
какие-то фундаментальные неточности.

Задача: Равновероятно случайно перераспределить деньги между N персонами.

Например есть 10 человек. Изначально у каждого по 10$. На каждой итерации нужно случайно перераспределить деньги.
Но чтобы вероятность получить одну и ту же сумму у каждого была одинаковой.

Пример не правильного распределения:

1. Кладем все деньги в общую кучу размера 100$.
2. Берем случайного человека.
3. Даем ему случайную сумму от 0 до 100$. Например 100$.
4. Остальные 9 человек обламываются, т.к. делить остается 0$.

Примерно правильное решение у меня уже складывается, но пока сформулировать затрудняюсь. Поэтому решил попросить помощи ).

Здравствуйте, C0x, Вы писали:

C0x>Например есть 10 человек. Изначально у каждого по 10$. На каждой итерации нужно случайно перераспределить деньги.
C0x>Но чтобы вероятность получить одну и ту же сумму у каждого была одинаковой.
Произвольно разбиваем $100 на 5 кучек (разбиение должно быть одинаковым при каждой раздаче), рандом сорт, раздаём.

Здравствуйте, Sinix, Вы писали:

S>Здравствуйте, C0x, Вы писали:

C0x>>Например есть 10 человек. Изначально у каждого по 10$. На каждой итерации нужно случайно перераспределить деньги.
C0x>>Но чтобы вероятность получить одну и ту же сумму у каждого была одинаковой.
S>Произвольно разбиваем $100 на 5 кучек (разбиение должно быть одинаковым при каждой раздаче), рандом сорт, раздаём.

Что значит разбиение должно быть одинаковым при каждой раздаче? Если произвольно разбивать на 5 кучек то как я показал в примере
может получится 1 кучка размером 100$ и пять кучек размера 0$. Как избавиться от таких разбиений?

Здравствуйте, 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>Примерно правильное решение у меня уже складывается, но пока сформулировать затрудняюсь. Поэтому решил попросить помощи ).

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

Здравствуйте, Qulac, Вы писали:

Q>Смотря что считать "наиболее равномерным". Можно кинуть жребий и отдать все одному, можно раздавать по кругу по определенной сумме в случае если выпал жребий.

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

Вот что я считаю правильным: cлучайно выбрать 10 чисел, каждое от 0 до 100.
Например выборка [100, 100, 50, 70, 20, 25, 40, 50, 100, 43].
В этом случае я считаю что 1, 2, 9-й чуваки получат одинаковую сумму и эта сумма будет явно больше, чем у всех остальных,
но она не будет равна 100, а будет вычисляться из с учетом результатов полученных для остальных чуваков.

Здравствуйте, C0x, Вы писали:

Генериуешь последовательность из 10 случайных чисел от 0 до 1, потом нормируешь (умножаешь на K), чтобы сумма сошлась?

Здравствуйте, bnk, Вы писали:

bnk>Здравствуйте, C0x, Вы писали:

bnk>Генериуешь последовательность из 10 случайных чисел от 0 до 1, потом нормируешь (умножаешь на K), чтобы сумма сошлась?

Вот жеж..., про нормирование то я и забыл. Это и есть решение. Спасибо!

Здравствуйте, 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 (грань симплекса).
Дальше надо подумать и вспомнить тервер.

C0x>Задача: Равновероятно случайно перераспределить деньги между N персонами.

C0x>Например есть 10 человек. Изначально у каждого по 10$. На каждой итерации нужно случайно перераспределить деньги.
C0x>Но чтобы вероятность получить одну и ту же сумму у каждого была одинаковой.
Поставим все эти 10 человек в круг.
Бегаем по кругу.
Перед каждым челом бросаем монетку.
Выпал орел — отдаем 1 (один) бакс.
Выпала решка — бегим дальше.

Бегаем до тех пор, пока не раздадим все деньги.

http://en.wikipedia.org/wiki/Low-discrepancy_sequence
http://en.wikipedia.org/wiki/Sobol_sequence

Здравствуйте, 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

Здравствуйте, LaptevVV, Вы писали:


LVV>Бегаем до тех пор, пока не раздадим все деньги.


Тут все-таки хотелось бы не за O(N*M) а все-таки за O(N), т.к. N значительно меньше, чем M.
N — кол-во чуваков, M кол-во денег суммарно.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, bnk, Вы писали:

bnk>>Генериуешь последовательность из 10 случайных чисел от 0 до 1, потом нормируешь (умножаешь на K), чтобы сумма сошлась?

К>Неравномерное распределение получается.

Главное что оно честное (равно-вероятное)

Здравствуйте, RiNSpy, Вы писали:

RNS>http://en.wikipedia.org/wiki/Low-discrepancy_sequence
RNS>http://en.wikipedia.org/wiki/Sobol_sequence

А можно либретто по-русски?

Здравствуйте, C0x, Вы писали:

К>>Неравномерное распределение получается.

C0x>Главное что оно честное (равно-вероятное)

В том и дело, что не равновероятное.
А то можно взять N произвольных денежных векторов, где N вообще конечное, например, { (1,0,0...,0) и (0.1,0.1,...,0.1) } и равно-вероятно выбирать между ними.
Что в этом честного?

Равновероятное — это берём всё множество решений x1+...+x10=1, например, с дискретностью по 0.01, и равновероятно случайно выбираем между ними.

Здравствуйте, Mazay, Вы писали:

M>Получается у всех одинаковая вероятность получить одну и ту же сумму:

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

Здравствуйте, Кодт, Вы писали:

К>В том и дело, что не равновероятное.
К>А то можно взять N произвольных денежных векторов, где N вообще конечное, например, { (1,0,0...,0) и (0.1,0.1,...,0.1) } и равно-вероятно выбирать между ними.
К>Что в этом честного?

Равновероятное, так как мы для каждого чувака выбираем долю (от 0 до 1) с одинаковой вероятностью или не?
Это тоже самое, что выбирать из бесконечного числа векторов (x1, ..., xN), где x в диапазоне от 0 до 1.
Потом эти доли нормируем, тут вроде бы как ничто не портит равновероятность.

К>Равновероятное — это берём всё множество решений x1+...+x10=1, например, с дискретностью по 0.01, и равновероятно случайно выбираем между ними.

а разве это не тоже самое что выбирать из бесконечного множества векторов указанных мной выше?

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, 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>Я не хочу, чтобы первая выборка вообще оказывала какое-либо влияние на последующие. Это я считаю наиболее честное распределение будет.

Таким образом, ты хочешь изменить критерий "случайность" в пользу критерия "честность". Почему? И если быть честным важнее — зачем, вообще, распределять с элементом случайности?

Здравствуйте, C0x, Вы писали:


M>>Получается у всех одинаковая вероятность получить одну и ту же сумму:

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

Это невозможно, если доли случайны и сумма долей должна быть равна единице (если раздать все $100).