一维空间中的吃豆子问题

KeyTo9_Fans

假设有一条长度为$1$的线段，左端点是$x=0$，右端点是$x=1$。 线段上有$k$个豆子，wayne在这条线段上移动。

下图是一个$k=1$的例子 一旦wayne的$x$坐标与某个豆子的$x$坐标相等，wayne就会把这个豆子吃掉。 一旦wayne把一个豆子吃掉，一个新的豆子就会立即出现在$[0,1]$区间中均匀分布的一个随机的点上。 wayne的移动速度是每秒$1$单位长度。 wayne可以随时改变移动方向。 wayne总是采取最佳策略，使得吃豆子的平均速率最大。 于是当$k=0$时，wayne吃豆子的平均速率是$0$个每秒； 当$k=1$时，wayne吃豆子的平均速率是$3$个每秒。 问题$1$：当$k=2$时，wayne吃豆子的平均速率是多少？ 问题$2$：当$k=3$时，wayne吃豆子的平均速率是多少？ 问题$3$：当$k=4$时，wayne吃豆子的平均速率是多少？

wayne

问题转化为求 $\sum_{i=1}^{k}|x_i -x_{i+1}|$的期望值， x_i在【0，1】内均匀分布 猜想： $3/k$

KeyTo9_Fans

2# wayne $k=1$当然没问题咯，豆子在哪边wayne就往哪边跑。 可是当$k>1$时就没那么简单了， wayne经常要思考“到底先吃哪边的豆子才能使得吃豆子的平均速率最大呢？” 如下图所示 如果wayne总是吃最近的那个豆子， 那么当$k=2$时，模拟到$10^11$个豆子，结果是…… wayne吃豆子的平均速率是$(4.53704\pm 0.00002)$个每秒。 可是wayne绝顶聪明，不一定总是吃最近的那个豆子， 所以当$k=2$时，wayne吃豆子的平均速率要大于$4.53702$个每秒。 具体大多少，就得知道wayne采取的最佳策略是什么了*_*

wayne

我题意没读懂。 是不是任何时候都有k个豆子存在？ 另外，wayne最初的位置fans安排在哪呢？

KeyTo9_Fans

是的。任何时候都有$k$个豆子存在。 这是因为： “一旦wayne把一个豆子吃掉，一个新的豆子就会立即出现在$[0,1]$区间中均匀分布的一个随机的点上。” wayne最初的位置在哪里都不要紧。 这是因为wayne永远都在这条线段上移动。 当给定时间$t$时，wayne吃豆子的平均速率是${n(t)}/t$， 其中$n(t)$是wayne在$t$时间内所吃的豆子数。 所以无论wayne最初的位置在哪里， $\lim_{t->\infty}{n(t)}/t$的值都是一样的

wayne

5# KeyTo9_Fans 这个假设的"wayne绝顶聪明" 太假了。 过去，现在，将来，................... 过去的状态决定了当前的wayne身处何处， 但将来的状态，即在吃完一个豆子的那一刻，新的豆子将在哪产生，wayne是无法预测的， 用自动控制领域的术语来讲，这里没有反馈因素，是开环控制。 于是， 于是，wayne只能利用现有的位置和当前k个豆子的分布来作为当前决策的依据， 所以，wayne的决策方案 似乎只能是 假设不会产生新豆子，要以最快的速度吃掉当前所有的k个豆子，应该先吃哪个

wayne

5# KeyTo9_Fans fans是不是看到我的头像用的是一只可爱的鸟儿，才故意这么出题为难我的，对么？

wayne

6# wayne

一旦wayne把一个豆子吃掉，一个新的豆子就会立即出现在【0，1】区间中均匀分布的一个随机的点上。

这个条件该怎么加到当前的决策中去呢

KeyTo9_Fans

当$k=2$时，wayne的策略可以用一个$3$元的布尔函数$f$来描述。 $f$的输入是$x_1$，$x_2$，$x_w$。 其中，$x_1$和$x_2$表示豆子的位置，$x_w$表示wayne的位置。 $f$的输出是一个方向，“左”或者“右”。 函数$f$确定之后，wayne的策略也就确定了。 于是我们就可以对wayne的策略进行评价了。 评价的方法如下： 取一个足够大的$t$，然后任取一个开始状态， 然后把wayne和豆子的位置作为函数$f$的输入， 根据$f$的输出来决定wayne下一步吃哪个豆子。 我们用$n(t)$来表示wayne在$t$时间内所吃的豆子数。 ${n(t)}/t$越大，说明wayne的策略越好，${n(t)}/t$越小，说明wayne的策略越差。 如果我们对所有可能的函数$f$都模拟过一遍，我们就知道wayne的最佳策略是什么了。

KeyTo9_Fans

所以。。。所以。。。 $6#$的话都有道理，wayne只能利用现有的位置和当前$k$个豆子的分布来作为当前决策的依据。 只是。。。只是。。。 “当$t$给定，吃豆子数$n(t)$尽可能大”并不意味着“要以最快的速度吃掉当前所有的$k$个豆子”。 我“假设wayne绝顶聪明”，只是假设wayne已经对所有可能的函数$f$的评价结果都了如指掌了，并没有假设wayne可以预测出下一个豆子出现在哪些地方