一维空间中的吃豆子问题

公子相

假设有一条长度为$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吃豆子的平均速率是多少？

litong

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

uajoegecp

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采取的最佳策略是什么了*_*

Geraldufas

我题意没读懂。
是不是任何时候都有k个豆子存在？

另外，wayne最初的位置fans安排在哪呢？

asukrimukozor

是的。任何时候都有$k$个豆子存在。

这是因为：

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

wayne最初的位置在哪里都不要紧。

这是因为wayne永远都在这条线段上移动。

当给定时间$t$时，wayne吃豆子的平均速率是${n(t)}/t$，

其中$n(t)$是wayne在$t$时间内所吃的豆子数。

所以无论wayne最初的位置在哪里，

$\lim_{t->\infty}{n(t)}/t$的值都是一样的

xiaobai

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

ebirugerxos

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

jnetoji

6# wayne

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

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

icakeekohude

当$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的最佳策略是什么了。

singqing

所以。。。所以。。。

$6#$的话都有道理，wayne只能利用现有的位置和当前$k$个豆子的分布来作为当前决策的依据。

只是。。。只是。。。

“当$t$给定，吃豆子数$n(t)$尽可能大”并不意味着“要以最快的速度吃掉当前所有的$k$个豆子”。

我“假设wayne绝顶聪明”，只是假设wayne已经对所有可能的函数$f$的评价结果都了如指掌了，并没有假设wayne可以预测出下一个豆子出现在哪些地方