Из мешка случайным образом выпадает один из 5 предметов

k1a2r3t4a

Нашел интересную задачу.
Из мешка случайным образом выпадает один из 5 предметов: a1,a2,a3,a4,a5. Их вероятности:
p1 = 40/289
p2 = 160/289
p3 = 8/289
p4 = 80/289
p5 = 1/289
Предметы a1, a2, a4 могут выпасть только один раз. Сколько нужно открыть мешков, чтобы получить a5
Судя по всему a1,a2,a4 выпадают только один раз за всю серию испытаний , то есть если в одном мешке a1/a2/a4 найден, то в других он и не появится.

pavloff

Я ничего не понял из условий задачи. Как это выглядит: есть мешок с неизвестно чем, мы его открываем, вытащили предмет, мешок стал пустым? А-ля ящики в steam? Тогда что вообще значит эта фраза?
1) a1,a2,a4 выпадают только один раз в каждом из мешков
И ещё следует определиться с формулировкой "Сколько нужно открыть мешков, чтобы получить a5". Вероятность всегда будет меньше единицы. Можно только спросить, сколько нужно открыть мешков, чтобы вероятность получить a5 была больше x, например, больше 0,95.

k1a2r3t4a

Судя по всему каждый сундук можно открыть только один раз. А значит, если в каком то из мешков выпадет a1/a2/a4 то больше они не появятся в других мешках. И да, в каждом сундуке находится только один предмет. И получается, что ролл предмета зависит от предыдущих исходов. Возможно, тут нужно юзать марковские цепи?
К вопросу о том, что же означает фраза "Сколько нужно открыть сундуков чтобы выпал a5" можно рассмотреть два варианта : сколько в среднем, и сколько с вероятностью 95%.

pavloff

Нужен точный аналитический овтет? Нужна примерная оценка? Оценивать нужно часто? Я б может просто сгенерил 10000 последовательностей по 500-1000 открытий сундука, и уже смотрел статистику.

k1a2r3t4a

Я б может просто сгенерил 10000 последовательностей по 500-1000 открытий сундука, и уже смотрел статистику.
Кстати, хорошая идея. Я б тоже прибег к скрипту. Но мне интересен именно теоретический расчет.

Sensor4ik

Из общих соображений, вероятности p1, p2 и p4 сильно больше p3 и p5. Это означает, что уже за несколько мешков мы с вероятностью, близкой к 1, вытащим их все, и тогда результат открытия сведется к вариантам p3 и p5, которые при этом станут 8/9 и 1/9, а это уже считается просто.

kachokslava

по-моему он бустеры в хартстоуне открывает :grin:
считает сколько в среднем надо бустеров купить, чтобы легендарка выпала

k1a2r3t4a

p3 и p5. Это означает, что уже за несколько мешков мы с вероятностью, близкой к 1, вытащим их все, и тогда результат открытия сведется к вариантам p3 и p5, которые при этом станут 8/9 и 1/9, а это уже считается просто.
Да но на каждом шаге, когда один из предметов a1,a2,a4 выпадает, вероятности пересчитываются. Это несколько усложняет расчет.

k1a2r3t4a

по-моему он бустеры в хартстоуне открывает
считает сколько в среднем надо бустеров купить, чтобы легендарка выпала
Не-а :)

LipkinKS

Да но на каждом шаге, когда один из предметов a1,a2,a4 выпадает, вероятности пересчитываются. Это несколько усложняет расчет.
Но ведь соотношение вероятностей оставшихся событий остается то же, что и в начале?

k1a2r3t4a

ятностей оставшихся событий остается то же, что и в начале?
да

griz_a

А что нужно-то? Распределение? Тогда ответ в любом случае будет довольно уродливый. Можно, например, получить выражение на производящую функцию, а как из нее вычленять явный вид распределения = как разложить получившуюся дробь в ряд Тейлора. Можно на простейшие, если не лень.
Пусть [math]$f_{A}(s) $[/math] - п.ф. числа бросаний до выпадания первого 5ого предмета, если из 1,2,4 остались элементы множества A
Тогда
[math]$f_{1,2,4}(s) = s(p_5 + p_3 f_{1,2,4}(s) + p_4 f_{1,2}(s) + p_2 f_{1,4}(s) + p_1 f_{2,4}(s $[/math]
[math]$f_{1,2}(s) = \frac{s}{1-p_4} (p_5 + p_3 f_{1,2}(s) + p_2 f_{1}(s) + p_1 f_{2}(s $[/math]
Аналогичные уравнения выписываются на [math]$f_{1,4}$[/math], [math]$f_{2,4}$[/math]
[math]$f_{1}(s) = \frac{s}{1-p_4-p_2} (p_5 + p_3 f_{1}(s) + p_1 f_{\emptyset}(s $[/math]
Аналогичные уравнения выписываются на [math]$f_{2}$[/math], [math]$f_{4}$[/math]
И наконец [math]$f_{\emptyset}(s) = p_5 s/(p_3+p_5-p_3 s)$[/math] - геометрическое распределение.
Отсюда
[math]$f_i(s) = \frac{p_i s f_{\emptyset}(s) + p_5 s}{p_1+p_5+p_i-p_3 s}$[/math]
Далее,
[math]$f_{i,j} (s) = \frac{p_i s f_{j}(s) + p_j s f_i(s) + p_5 s}{1+p_4-p_3 s}$[/math]
Наконец,
[math]$f_{1,2,4}(s) = \frac{p_1 s f_{2,4}(s) + p_2 s f_{1,4}(s) + p_4 s f_{1,2} + p_5 s}{1-p_3 s} $[/math]

k1a2r3t4a

- п.ф. числа бросаний до выпадания первого 5ого предмета, если из 1,2,4 остались элементы множества A
Тогда
Аналогичные уравнения выписываются на ,
Аналогичные уравнения выписываются на ,
И наконец - геометрическое распределение.
Отсюда
Далее,
Наконец,
А что здесь s? Количество бросаний?

griz_a

Чтобы понять, что я написал, нужно прочитать, что такое производящая функция. В этот момент вопрос "что такое s" отпадет, думаю

k1a2r3t4a

написал, нужно прочитать, что такое производящая функция. В этот момент вопрос "что такое s" отпадет, думаю
а, понял :) Спасибо большое!

k1a2r3t4a

Взял я производную в точке 0 и получил p5 что явно бред :(.

griz_a

Производная в нуле - это что ровно на первом шаге мы попадем в нужное место. Мне кажется, что это ровно p_5, нет?

k1a2r3t4a

Написал скрипт на питоне:
 
  
import random
import statistics
import numpy as np
import scipy as sp
import scipy.stats
def mean_confidence_interval(data, confidence=0.95):
a = 1.0*np.array(data)
n = len(a)
m, se = np.mean(a scipy.stats.sem(a)
h = se * sp.stats.t._ppf1+confidence)/2., n-1)
return m, m-h, m+h

p10 = 40.0/289.0
p20 = 160.0/289.0
p30 = 8.0/289.0
p40 = 80.0/289.0
p50 = 1.0/289.0


p1_1 = 0
p2_1 = p20/(p20+p30+p40+p50)
p3_1 = p30/(p20+p30+p40+p50)
p4_1 = p40/(p20+p30+p40+p50)
p5_1 = p50/(p20+p30+p40+p50)

p1_2 = p10/(p10+p30+p40+p50)
p2_2 = 0
p3_2 = p30/(p10+p30+p40+p50)
p4_2 = p40/(p10+p30+p40+p50)
p5_2 = p50/(p10+p30+p40+p50)

p1_4 = p10/(p10+p20+p30+p50)
p2_4 = p20/(p10+p20+p30+p50)
p3_4 = p30/(p10+p20+p30+p50)
p4_4 = 0
p5_4 = p50/(p10+p20+p30+p50)

p1_12 = 0
p2_12 = 0
p3_12 = p30/(p30+p40+p50)
p4_12 = p40/(p30+p40+p50)
p5_12 = p50/(p30+p40+p50)

p1_14 = 0
p2_14 = p20/(p20+p30+p50)
p3_14 = p30/(p20+p30+p50)
p4_14 = 0
p5_14 = p50/(p20+p30+p50)

p1_24 = p10/(p10+p30+p50)
p2_24 = 0
p3_24 = p30/(p10+p30+p50)
p4_24 = 0
p5_24 = p50/(p10+p30+p50)

p1_124 = 0
p2_124 = 0
p3_124 = p30/(p30+p50)
p4_124 = 0
p5_124 = p50/(p30+p50)

c1=c2=c3=c4=c5=0
state1=state2=state4=0

print "preved"
print random.random
print p10
print p10+p20+p30+p40+p50
print p1_1+p2_1+p3_1+p4_1+p5_1
print p1_124+p2_124+p3_124+p4_124+p5_124
N=[]
for j in range(10000):
p1 = p10
p2 = p20
p3 = p30
p4 = p40
p5 = p50
state1=state2=state4=0
c1=c2=c3=c4=c5=0
for i in range(10000):
tmp=random.random
# print i, "4astoti: ",c1,c2,c3,c4,c5, "states: ", state1, state2, state4
if tmp<=p1:
c1+=1
state1=1
if(state2==0 and state4==0):
p1=p1_1
p2=p2_1
p3=p3_1
p4=p4_1
p5=p5_1
elif(state2==1 and state4==0):
p1=p1_12
p2=p2_12
p3=p3_12
p4=p4_12
p5=p5_12
elif(state2==0 and state4==1):
p1=p1_14
p2=p2_14
p3=p3_14
p4=p4_14
p5=p5_14
else:
p1=p1_124
p2=p2_124
p3=p3_124
p4=p4_124
p5=p5_124

# print i,tmp,"item1"
elif tmp<=p1+p2:
c2+=1
state2=1
if(state1==0 and state4==0):
p1=p1_2
p2=p2_2
p3=p3_2
p4=p4_2
p5=p5_2
elif(state1==1 and state4==0):
p1=p1_12
p2=p2_12
p3=p3_12
p4=p4_12
p5=p5_12
elif(state1==0 and state4==1):
p1=p1_24
p2=p2_24
p3=p3_24
p4=p4_24
p5=p5_24
else:
p1=p1_124
p2=p2_124
p3=p3_124
p4=p4_124
p5=p5_124
# print i,tmp,"item2"
elif tmp<=p1+p2+p3:
c3+=1
# print i,tmp, "item3"
elif tmp<=p1+p2+p3+p4:
c4+=1
state4=1
if(state1==0 and state2==0):
p1=p1_4
p2=p2_4
p3=p3_4
p4=p4_4
p5=p5_4
elif(state1==1 and state2==0):
p1=p1_14
p2=p2_14
p3=p3_14
p4=p4_14
p5=p5_14
elif(state1==0 and state2==1):
p1=p1_24
p2=p2_24
p3=p3_24
p4=p4_24
p5=p5_24
else:
p1=p1_124
p2=p2_124
p3=p3_124
p4=p4_124
p5=p5_124
# print i,tmp, "item4"
else:
c5+=1
N.append(i)
# print i,tmp, "item5"
if c5>=1:
break
# print i

#print N
print statistics.mean(N)
print statistics.pstdev(N)
print mean_confidence_interval(N)
#def f_0(s):
# return p50*s/(p30+p50-p30*s)
#for i in range(50):
# print f_0(i)


Выдает ответ 10.8362 - среднее из полученной статистики

k1a2r3t4a

Как теперь из известных распределений которые указаны выше прийти к этому ответу ?
Налицо же случайный процесс.

LipkinKS

Выдает ответ 10.8362 - среднее из полученной статистики
Мой скрипт выдает 11.956257, что мне больше нравится (3 за a1, a2, a4 + 9 за вероятность 1/9 выпадения a5 при двух оставшихся предметах - немного из-за того что a5 может иногда выпасть раньше a1, a2, a4).
Еще получается что с вероятностью не менее 95% a5 выпадает за 29 попыток.

griz_a

Если цель была математическое ожидание подсчитать, то система будет проще
[math]$E_{\emptyset}(s) = (p_5+p_3)/p_5$[/math] - среднее геометрического распределения
[math]$E_{1} = 1+ \frac{1}{1-p_4-p_2} (p_3 E_{1} + p_1 E_{\emptyset} $[/math]
откуда
[math]$E_{1}  = \frac{p_1}{p_1+p_5} + \frac{p_5+p_3}{p_5}, $[/math]
если я не обсчитался. Тогда
[math]$E_{2}  = \frac{p_2}{p_2+p_5} + \frac{p_5+p_3}{p_5}, $[/math]
[math]$E_{4}  = \frac{p_4}{p_4+p_5} + \frac{p_5+p_3}{p_5}, $[/math]
[math]$E_{1,2} = 1 + \frac{1}{1-p_4} (p_3 E_{1,2} + p_2 E_{1} + p_1 E_{2} $[/math]
откуда
[math]$E_{1,2} = \frac{p_5+p_3}{p_5} + \frac{p_3+p_5}{p_1+p_2+p_5} + \frac{p_1 p_2}{(p_1+p_5p_2+p_5)} + \frac{p_1 p_2 p_5}{(p_1+p_5p_2+p_5p_1+p_2+p_5)}, $[/math]
Аналогично [math]$E_{1,4}, E_{2,4}$[/math]
И наконец
[math]$E_{1,2,4} = 1 + p_3 E_{1,2,4} + p_4 E_{1,2} + p_2 E_{1,4} + p_1 E_{2,4} $[/math]
откуда
[math]$E_{1,2,4}(1-p_3) = 1 + p_4 E_{1,2} + p_2 E_{1,4} + p_1 E_{2,4} $[/math]

k1a2r3t4a

Вот можно через марковские процессы.

Задача : три предмета. 1ый предмет выпадает только один раз. шанс 2/10. 2й и 3й предметы соотв. выпадают сколько угодно раз с шансами 5/10, 3/10. То есть p1 = 2/10, p2 = 5/10, p3 = 3/10
Найти на каком шаге вероятность попасть в состояние 3 (выпал третий предмет) будет не менее 95%.

griz_a

а) почему их стало 3?
б) чем это отличается от уже изложенного?

LipkinKS

Если цель была математическое ожидание подсчитать, то система будет проще
Попробовал посчитать, математическое ожидание получилось 6393209/534681 или примерно 11.957

k1a2r3t4a

это по последней формуле? E1,2,4(1-p3) = 1 + p4*E1,2 + p2*E1,4 + p1*E2,4 ?
Через графы состояний мне понятней, но там громоздкая схема получается.

и 11 шаг найти будет трудновато.

k1a2r3t4a

 
а) почему их стало 3?
б) чем это отличается от уже изложенного?

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

griz_a

Я пользуюсь формулой полной вероятности.
[math]$ EX = E(X|A_1) P(A_1) + E(X|A_2) P(A_2) + E(X|A_3) P(A_3) ... ,$ [/math]
где [math]$A_i $[/math] - разбиение, в данном случае по результату первого броска.
При этом [math]$E(X|A_5)=1$[/math], т.к мы тут же закончили, [math]$E(X|A_3) = 1 + EX$[/math], поскольку мы один ход потратили и фактически все началось сначала, а
[math]$E(X|A_i)$[/math] при остальных i это та же задача, но с выбывшим из рассмотрения шаром одного из типов.

LipkinKS

это по последней формуле? E1,2,4(1-p3) = 1 + p4*E1,2 + p2*E1,4 + p1*E2,4 ?
Итоговый результат да, по последней.
Через графы состояний мне понятней, но там громоздкая схема получается.
А что означают числа в состояниях? Если предметы которые еще могут выпасть, то почему в некоторых состояниях нет 3?

k1a2r3t4a

А что означают числа в состояниях? Если предметы которые еще могут выпасть, то почему в некоторых состояниях нет 3?
1,2,3,4,5 - значит, что никакой из предметов еще не выпал
1,2,4,5 - значит, что выпал третий предмет

LipkinKS

1,2,3,4,5 - значит, что никакой из предметов еще не выпал
1,2,4,5 - значит, что выпал третий предмет
Почему когда выпадает 3 состояние меняется? Ведь вроде по условию задачи 3 может выпадать неограниченное число раз.

k1a2r3t4a

падать неограниченное число раз.
да все верно, напутал со схемой.

k1a2r3t4a

Я пользуюсь формулой полной вероятности.
где - разбиение, в данном случае по результату первого броска.
При этом , т.к мы тут же закончили, , поскольку мы один ход потратили и фактически все началось сначала, а
 при остальных i это та же задача, но с выбывшим из рассмотрения шаром одного из типов.
Понял, а можете рассмотреть мою более простую задачу и расписать среднее для них с тремя предметами 1,2,3. 1 выпадает сколько угодно раз, 2 - один раз, если выпадает 3 то броски заканчиваются.
вот я начал вычислять вероятности оказаться в состояние i на jом броске:
Матрица переходов:
Pij = p1, p2, p3,
     0, p2/(p2+p3) p3/(p2+p3)
     0, 0, 0
pi(j) - вероятностm оказаться в состояние i на jом броске
p1(0)=1, p2(0)=0, p3(0)=0
p1(1)=p2, p2(1)=p1, p3(1)=p3
p1(2)=p2*p2= 25/100
p2(2)= p2(1)*p2/(p2+p3) + p1(1)*p1 = p1*p2/(p2+p3) + p2*p1 = 255/700
p3(2) = p3(1)+(1-p3(1*(p1(2)*p3+p2(2)*p3/(p2+p3 =
p1(3) = p2*p2*p2 = 125/1000
p2(3) = p2(2)*p2/(p2+p3) + p1(2)*p1 = 0.3352
p3(3) =
p3(4) =
Верно ли, что :
p3(2) = p3(1) + (1-p3(1*(вероятности прийти в состояние 3 из других состояний)...
оффтоп: вы постите формулы как картинки из гугл-апи формул? или из TeXa?

griz_a

Если вы хотите по этой задаче цепь Маркова строить, то нужно состояния брать типа (2,3 не выпадали (2 выпало, 3 нет 3 выпало
Третья строка при этом будет (0,0,1)
Итак, как будет выглядеть для трех. Пусть X - время до 3 в исходном наборе, [math]$A_1,A_2,A_3$[/math] - события ''первый раз выпадет 1", "первый раз выпадет 2", "первый раз выпадет 3".
[math]$X'$[/math] - среднее время ожидания 3, если 2 нет в наборе,
Тогда
[math]$ EX = E(X|A_1) P(A_1) + E(X|A_2) P(A_2) + E(X|A_3)P(A_3)$[/math]
[math]$P(A_i) = p_i$[/math], [math]$E(X|A_1) = EX+ 1$[/math], [math]$E(X|A_2) = EX'+1,$[/math] [math]$E(X|A_3) = 1$[/math]
Аналогично
[math]$ EX' = E(X'|A_1) P'(A_1) + E(X'|A_3)P'(A_3) = (EX' + 1) \frac{p_1}{p_1+p_3} + \frac{p_3}{p_1+p_3}$[/math]
Оставить комментарий
Имя или ник:
Комментарий: