怎样操作使编号的期望最大

realnumber

一个黑箱里封着n类大小一样，材质一样的珠子，1~n编号，数量足够多，
第一次黑箱会吐出一颗珠子，接下来需要塞一颗珠子回去，才会吐出一颗（约定每类珠子吐出的概率都是$\frac{1}{n}$）.
假定黑箱吐k次后，就不再吐珠子了，问有什么策略使得得到的珠子编号期望最大（比如吐出的珠子是n号，那当然不用塞回去了，可以停下来了），且这个期望值是多少？，n，k都是大于1的正整数.

睡神

回复 1# realnumber
没看懂…你是想问，几个人比赛的话，你拿几号球停下来更稳妥？

睡神

如果是这样的话，机器每次吐球的概率固定不变，人为改变不了，每次的期望都是(n+1)/2，当我取到的球号大于或等于(n+1)/2时停止，否则，一直取到k次机器自动停止…

realnumber

不是的，应该与k有关
比如n=10,你已经取到了7号，如果只有一次机会了，可以肯定不会再塞回去了
但如果还有1000次机会，估计即使取到9也会塞回去，因为1000次里出现10是很有可能的

realnumber

回复 2# 睡神


    可能是吧，是小伙的同学转述的问题，发到论坛上已经转3手了，还都是学编程初中生
所以觉得要补充什么漏洞，尽管补上

睡神

回复 5# realnumber
我觉得与博弈有关。比如玩21点，如果你拿到了18点，并且你无法估计别人的情况，肯定不会再搏；如果你估计别人的比你的要大，那你肯定会继续搏，即使很大可能会爆掉。同样，这游戏也差不多，如果k/n较小时，风险大，当你拿到一个不错的球号时，不会再去搏，除非你知道别人拿到号码更大；如果k/n比较大时，风险小，那你肯定会继续去搏，这样游戏也失去了意义…

realnumber

嗯，你说的也有些道理，问题补充说明如下
就某人一个人玩耍，仅仅是为了得到最高分数。
他该如何制定策略使得所得编号期望最大？

realnumber

和小伙讨论，觉得就这个了，如下
比如n=10,还有k=3次机会，手上是5号
策略1：摸到大于等于6就停止，最后的期望是$\frac{1}{8}\frac{1+2+3+4+5}{5}+\frac{7}{8}\frac{6+7+8+9+10}{5}$
策略2：摸到10号停止，

总结出分治的方法,依次令k=1,2,3,...
如果接下来的“任何一个策略的期望”没有大于手上的编号，则停止.--感觉这个最优了.

tommywong

n=10，如果k只有1，冇策略可以用，期望值係$E_1=5.5$
如果k=2，你知道重抽嘅期望值係5.5，於是乎個策略就係抽到5.5以下就重抽
而咁樣做嘅期望值就係$E_2=0.5\times 5.5+0.5\times 8=6.75$
k=2，你知道重抽嘅期望值係6.75，抽到6.75以下就重抽
$E_3=0.6\times 6.75+0.4\times 8.5=7.45$
$\displaystyle E_{k+1}=\frac{[E_k]}{n}E_k+\frac{n-[E_k]}{n(n-[E_k])}\sum_{k=[E_k]+1}^{n}k
=\frac{[E_k]}{n}E_k+\frac{1}{n}\binom{n+1}{2}-\frac{1}{n}\binom{[E_k]+1}{2}$
5.5
6.75
7.45
7.915
8.2405
8.4924
8.69392
8.855136
8.9841088
9.08728704