凑百分概率游戏
假设我们要凑$100$积分。有一个赚积分的机器，工作机制如下：
————————————————————————————————
每次输入一个不小于$1$的实数$x$，就有$1/x$的概率获得$x$的积分。
————————————————————————————————
例如，输入$5$就有$20%$的概率获得$5$分，输入$1$就直接得$1$分。
现在给你$10$次赚分机会。
问能获得$100$积分的概率是多少？赚分策略是怎样的？
如果给你$50$次赚分机会，能获得$100$积分的概率是多少？策略是怎样的？ 看来剩下的(1-1/x)的概率是得0分了。
如果前9次就积到100分了，第10次机会可以放弃么？应该可以吧，否则，就算第10次输入10000，万一得分了岂不溢死了。 是的，剩下$(1-1/x)$的概率得$0$分。
可以放弃机会，但我觉得不必要。 这个不难，动态规划即可，是否也可以分析一下积分很大的情况 没有注意到x可以是任意实数。如果这样，动态规划只能得到近似值了。 有个问题，积分超出算不算完成任务？比如得到100.2分？ 假设积分超出也算完成，那么积分目标为T,给定步数为K(K<T),那么最优策略达到目标的概率为K/T（而显然，$K>=T$时，概率为1）。而策略时，如果余下步数为k,而还需要积分t(k<t),那么选择x=t-k+1即可达到目标。 1<=x<=100, 1<=n<=100.(n为次数），n次成功概率记为P(n)。n=1 或100不用说，需要要考虑的是n=2~99. 实际上不能取99<x<100，否则得分的话差的分小于1就补不上了。
记p(x)=1/x, q(x)=1-p(x)
n=2时
策略1：每次输入100分，得分就停。P(2)=p+p(1-p)=1.99%
策略2：先输入x分，得分后输入(100-x)分，不得分就输入100分。
p(2)=p(x)p(100-x)+q(x)p(100)=1/100，所以取x=99 时得到最大值p(2)=2% 如果要求积分正好达到目标才能够算完成，那么7#的策略对于$T>=K$还是有效的，但是对于$T<K$的情况，会比较有意思也比较复杂。不过对于本题来说，我们不需要考虑那种极端的情况。
所以对于Fans这里的两问，无论是否要求积分正好达到目标，概率都是0.1和0.5 同意楼上的答案。
无论我们怎么选择$x$，每次赚取积分的期望值都是$1$。
玩$10$次能赚取积分的期望值是$10$。
如果我们玩$10$次能以超过$0.1$的概率赚取$100$分，
那么就说明我们玩$10$次能赚取积分的期望值大于$100$×$0.1$=$10$，
这与赚分机器的工作机制不符。
所以最多以$0.1$的概率赚$100$分。
事实上我们采取的策略在其余$0.9$的概率下，得分都是$0$。
说明我们为了达成目标，一点积分也没有浪费，已经达到骗取积分的最高境界了。
玩$50$次也是类似的，$0.5$的概率得$100$分，$0.5$的概率得$0$分。
页:
[1]
2