выборка случайных элементовл с вероятностью...

[valerchik]

выборка случайных элементовл с вероятностью...

Вобщем такая вот задачка:
есть массив данных, и к каждому элементу массива вероятность.

1 - 0,1
2 - 0,3
3 - 0,5
и т.д.

так вот надо случайным образом выбрать случайный элемент учитывая вероятность.

 

[Кром]

Сначала выбираешь случайно число от 1 до 9 (1 + 3 + 5).
Потом проводишь сравнение с тремя базовыми числами.

 

[che]

Ступил. Все ясно.
Кром
Че-то я не понял, а как обеспечивается соответствие?

 

[iliah]

Кром
респект, классный алгоритм

che
выбираешь наибольшее непревышающее число

 

[che]

Если вероятность одна десятая, то при десяти выборках элемент будет выбран один раз. По алгоритму Крома элемент будет выбран один раз при девяти выборках, то есть вероятность 1/9 что ни в коем разе не равно 0.1 .
Речь идет об элементе с вероятностью 0.1

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

 

[iliah]

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

 

[che]

Originally posted by iliah
т.е. когда сумма вероятностей не больше единицы
поправьте, если я ошибаюсь

Сумма вероятностей всех возможных событий в рассматриваемой ситуации обязана равнятся единице, иначе это не вероятности.

 

[iliah]

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

 

[Tsatur]

есть идейка, может быть не очень удачная, но работать будет,.

число 1 вероятность 5
число 10 вероятность 3
число 7 вероятность 1

создавай массив из 5+3+1=9 элементов
с 1 по 5 элемент пиши 1
с 6 по 8 - 10
в 9 пиши 7

Думаю для современного компа это не внапряг

ЗЫ
Забыл Ну и рэндомь соответственно...

 

[tony2001]

>сумма вероятностей прибытия на одну остановку в ближайшие полчаса автобуса
>или троллейбуса легко может быть больше единицы
это как ?

 

[Gas]

[офтоп]
это - 100 пудово
[.офтоп]

 

[Tsatur]

Автор оригинала: che
Сумма вероятностей всех возможных событий в рассматриваемой ситуации обязана равнятся единице, иначе это не вероятности.

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

 

[che]

Originally posted by Tsatur
есть идейка, может быть не очень удачная, но работать будет,.

Это было первое что я предложил, но стер потому как Кром за это время ответил. То что он предлагает делает то же самое, что предлагаешь ты (и предлагал я) но без массива. Просто надо понять из какого диапазона генерить число. А понять это можно поняв что такое вероятность.

 

[Tsatur]

che
я просто разжевал немного

 

[che]

Originally posted by Tsatur
Ну почему же... главное, чтобы сохранилось процентное содержание... а чтобы не мучиться с процентами, не привязывайтесь к 1...

Ты хоть к чему привяжись. И хоть чем. вероятность события определяется n/m что означает что в m случаях событие произойдет n раз. и если сумма вероятностей всех возможных событий меньше единицы - то кого то забыли, если больше то какие то события происходят одновременно что само по себе является событием и значит события неправильно определены.

Не надо им разжевывать, челюсти атрофируются.

 

[Tsatur]

che
Я понимаю, что m- это 100%. Но чего вы пристали к ним? Почему не нравится вариант с массивом? Или надо миллиарды чисел перебирать?

 

[che]

Originally posted by Tsatur
che
Я понимаю, что m- это 100%. Но чего вы пристали к ним? Почему не нравится вариант с массивом? Или надо миллиарды чисел перебирать?

Имеем два события(числа), вероятность первого 0,34567, второго - 0,65433, каких размеров нужен массив, чтобы генерить нужное с нужной точностью?

 

[Tsatur]

che
Ха! Поэому я и говорю, не привязывайся к единице...

А вообще, нужна ли задавшему вопрос такая точность? Может ему будет достаточно вероятности типа 0,4 и 0,6?
Тогда пусть создается массив из 10 элементов, первое число записывает в первые 4, а второе в оставшиеся 6 И рэндомит

Конечно, если он проводит ядерные испытания и ему необходима такая (вероятность первого 0,34567, второго - 0,65433) такая точонсть, то этот способ выглядит нелепо (создавать массив из 34567+65433 элементов и записывать всего 2 числа )

 

[SiMM]

Автор оригинала: iliah
сумма вероятностей прибытия на одну остановку в ближайшие полчаса автобуса или троллейбуса легко может быть больше единицы, и тогда все-таки, наверное, надо суммировать
???

Идём учить теорию вероятностей и узнаём, что вероятность прибытия на одну остановку в ближайшие полчаса хотя бы одного троллейбуса или автобуса является суммой вероятностей следующих событий:
1. В ближайшие полчаса появится не менее одного автобуса, и ни одного троллейбуса.
2. В ближайшие полчаса появится не менее одного троллейбуса, и ни одного автобуса.
3. В ближайшие полчаса появится не менее одного троллейбуса и не менее одного автобуса.
Оставшееся событие - в ближайшие полчаса не появится ни одного автобуса и ни одного троллейбуса - в сумме с тремя предыдущими даст 1.
Поэтому лично к вам остаётся один риторический вопрос - как вероятность первых трёх событий может быть больше единицы?

 

[che]

Originally posted by Tsatur
che
Ха! Поэому я и говорю, не привязывайся к единице...

Это не я привязан к единице, а теория. Все претензии к создателю.

Конечно, если он проводит ядерные испытания и ему необходима такая (вероятность первого 0,34567, второго - 0,65433) такая точонсть, то этот способ выглядит нелепо (создавать массив из 34567+65433 элементов и записывать всего 2 числа )

Зачем создавать(с инициализацией) массив (неважно каких размеров), если для выполнения поставленной задачи достаточно сгенерить одно число и провести log2(n) проверок, где n число чисел в списке?

Ооох! Дико извиняюсь!. Алгоритм не будет работать, по крайней мере в том виде как предложил его Кром. Имеем десять чисел, вероятность каждого 0.1 А дальше сами.

Ага! Сортируешь массив по возрастанию, заменяешь каждую ячейку суммой предидущих, включая текущую и после этого генеришь число от нуля до единицы, единица включительно(ноль тоже) и проверяешь как было сказано выше. Ух, красота! Объяснять почему это работает?