Здравствуйте, 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 нормально-распределенных делаются вот этой формулой.
Там, правда, общая сумма, скорее всего, чуть-чуть не сойдется — но разницу можно равномерно поделить между игроками.
хотел уже на боковую
папаху снял и сапоги
но в комментариях проснулись
враги
Перекуём баги на фичи!
