s****r 发帖数: 41 | 1 一家餐馆每次给客人送一个小礼物。总共有五种不同的小礼物。每次一个客人随机得到
5种小礼物中的一种。如果收集到全部5种小礼物,吃饭可以打折。问一个客人要第一次
收集到全部5种小礼物,他去这家餐馆次数的期望值是多少? |
f*****e 发帖数: 2992 | 2 5*(1/1+1/2+1/3+1/4+1/5)
【在 s****r 的大作中提到】 : 一家餐馆每次给客人送一个小礼物。总共有五种不同的小礼物。每次一个客人随机得到 : 5种小礼物中的一种。如果收集到全部5种小礼物,吃饭可以打折。问一个客人要第一次 : 收集到全部5种小礼物,他去这家餐馆次数的期望值是多少?
|
Z*****Z 发帖数: 723 | 3 18.4?
【在 s****r 的大作中提到】 : 一家餐馆每次给客人送一个小礼物。总共有五种不同的小礼物。每次一个客人随机得到 : 5种小礼物中的一种。如果收集到全部5种小礼物,吃饭可以打折。问一个客人要第一次 : 收集到全部5种小礼物,他去这家餐馆次数的期望值是多少?
|
s****r 发帖数: 41 | 4 怎么来的?
【在 f*****e 的大作中提到】 : 5*(1/1+1/2+1/3+1/4+1/5)
|
s****r 发帖数: 41 | 5 how so?
【在 Z*****Z 的大作中提到】 : 18.4?
|
f*****e 发帖数: 2992 | 6 X=X1+X2+X3+X4+1,
Xi indicates 处于 i的阶段的步数或时间数。
由
成功率p,和成功率所需步数组成。
p在变化,每个阶段pi都不一样。
【在 s****r 的大作中提到】 : 怎么来的?
|
t*********h 发帖数: 941 | 7 11.4
【在 s****r 的大作中提到】 : 一家餐馆每次给客人送一个小礼物。总共有五种不同的小礼物。每次一个客人随机得到 : 5种小礼物中的一种。如果收集到全部5种小礼物,吃饭可以打折。问一个客人要第一次 : 收集到全部5种小礼物,他去这家餐馆次数的期望值是多少?
|
s****r 发帖数: 41 | 8 多谢fatalme. 我不是太明白。能说详细点吗?
我的思路是传统的求期望值的方法。
假设T为首次收集到全部5种礼物的就餐次数,很明显
P(T)=0 FOR T =1,2,3,4
P(T=5)=5!*(1/5)^5。 5!表示5种礼物在5次就餐中的排列,每种排列的概率是(1/5)^
5。
当T=6的时候,因为是首次收集到全部礼物,因此第六次的礼物跟前5次都不同。假设5
种礼物是A,B,C,D,E, 最后(第六次就餐时)收集到的礼物是E,前5次就餐总共得到了A
,B,C,D四种礼物。这时问题变成在5次就餐中得到4种礼物的概率是多少。然后把这个概
率乘以5(因为最后得到的礼物可能是ABCDE中的任何一种),就是P(T=6)。T=7,8,9...
的情况类似。最后的期望值应该是
5×P(T=5) + 6*P(T=6) + 7*P(T=7) + .....
一个无穷级数的总和。
但是我没有找到正确计算前5次就餐中得到4种礼物的概率的方法。或者有比这个更聪明
的办法?
【在 f*****e 的大作中提到】 : X=X1+X2+X3+X4+1, : Xi indicates 处于 i的阶段的步数或时间数。 : 由 : 成功率p,和成功率所需步数组成。 : p在变化,每个阶段pi都不一样。
|
f*****e 发帖数: 2992 | 9 algorithm design
P722, Collecting coupons.
)^
5
了A
..
【在 s****r 的大作中提到】 : 多谢fatalme. 我不是太明白。能说详细点吗? : 我的思路是传统的求期望值的方法。 : 假设T为首次收集到全部5种礼物的就餐次数,很明显 : P(T)=0 FOR T =1,2,3,4 : P(T=5)=5!*(1/5)^5。 5!表示5种礼物在5次就餐中的排列,每种排列的概率是(1/5)^ : 5。 : 当T=6的时候,因为是首次收集到全部礼物,因此第六次的礼物跟前5次都不同。假设5 : 种礼物是A,B,C,D,E, 最后(第六次就餐时)收集到的礼物是E,前5次就餐总共得到了A : ,B,C,D四种礼物。这时问题变成在5次就餐中得到4种礼物的概率是多少。然后把这个概 : 率乘以5(因为最后得到的礼物可能是ABCDE中的任何一种),就是P(T=6)。T=7,8,9...
|
h**6 发帖数: 4160 | 10 一家餐馆每次给客人送一套8张欧洲杯球星卡。总共有640张不同的球星卡。每次一个客
人随机得到640张球星卡中的8张。如果收集到全部640张球星卡,吃饭可以免费。问一
个客人要第一次收集到全部640张球星卡,他去这家餐馆次数的期望值是多少? |
|
|
f****0 发帖数: 151 | 11 这么说吧,把整个过程分解成五步:1.拿到第一个 2.拿到剩下四个中的一个 3.拿到剩
下三个中的一个 4.拿到剩下两个中的一个 5.拿到剩下的那一个
这样要完成每一步的期望就分别是 1, 5/4, 5/3, 5/2, 5/1
加起来就是 fatalme 的解了 |
f*****e 发帖数: 2992 | 12 除了recursion,还有简单方法吗?
【在 h**6 的大作中提到】 : 一家餐馆每次给客人送一套8张欧洲杯球星卡。总共有640张不同的球星卡。每次一个客 : 人随机得到640张球星卡中的8张。如果收集到全部640张球星卡,吃饭可以免费。问一 : 个客人要第一次收集到全部640张球星卡,他去这家餐馆次数的期望值是多少?
|
s****r 发帖数: 41 | 13 多谢fatalme和flier0指引方向,现在我明白了。
han6,我想你的问题可不可以认为本质上和每次拿一个球星卡没有不同。假设每次只拿
一个球星卡,总共640个。用faltalme的方法,期望值应该是
E=640*(1/640 + 1/639 + ... + 1/2 + 1)
如果每次拿8个,那么E/8就是han6题目的答案。
请大家指教啊。光顾着编程,把概率都扔一边了。
【在 f****0 的大作中提到】 : 这么说吧,把整个过程分解成五步:1.拿到第一个 2.拿到剩下四个中的一个 3.拿到剩 : 下三个中的一个 4.拿到剩下两个中的一个 5.拿到剩下的那一个 : 这样要完成每一步的期望就分别是 1, 5/4, 5/3, 5/2, 5/1 : 加起来就是 fatalme 的解了
|
c******w 发帖数: 1108 | 14 本质上还是有区别的
E(i) = 还差i张卡的条件下,集齐还需要的时间
P(i,i-j) = 还差i张卡的条件下,一次8张中得到j张新卡的概率
E(i) = P(i,i-0)E(i) + ... + P(i,i-8)E(i-8)
递归算吧
【在 s****r 的大作中提到】 : 多谢fatalme和flier0指引方向,现在我明白了。 : han6,我想你的问题可不可以认为本质上和每次拿一个球星卡没有不同。假设每次只拿 : 一个球星卡,总共640个。用faltalme的方法,期望值应该是 : E=640*(1/640 + 1/639 + ... + 1/2 + 1) : 如果每次拿8个,那么E/8就是han6题目的答案。 : 请大家指教啊。光顾着编程,把概率都扔一边了。
|
C***U 发帖数: 2406 | 15 前面说的解法是对的 不过说的不是很严谨
假设x_i是收集第i个小礼物所需要的次数的随机变量,那么你的问题就是求x=sum x_i
的期望。在已经收集到i-1个小礼物的情况下,再收集一个新礼物的概率是n-i+1/n。然
后这里要用到的一个性质是x_i都是几何分布的。几何分布随机变量的期望就是收集到
新礼物的概率的倒数。
所以Ex=Ex_1+...+Ex_5=5/5+...+5/1。
【在 s****r 的大作中提到】 : 一家餐馆每次给客人送一个小礼物。总共有五种不同的小礼物。每次一个客人随机得到 : 5种小礼物中的一种。如果收集到全部5种小礼物,吃饭可以打折。问一个客人要第一次 : 收集到全部5种小礼物,他去这家餐馆次数的期望值是多少?
|