一维空间中的吃豆子问题

dianyancao

是不是和产生的伪随机数分布有很大关系?
当吃过极大的数量的豆子后，是不是满足豆子位置坐标的均值=1/2?

dianyancao

在有限的时间内产生0到1之间的任意实数，算法实现的时间复杂度和产生的实数的有效二进制位之间有什么关系？

KeyTo9_Fans

没关系。只要伪随机数的性质足够好，我们的实验结果就会无限接近理论结果。

对于吃过的豆子而言，均值是$1/2$。

对于每次吃剩的$(k-1)$个豆子而言，则不一定。

要产生$n$个$0$到$1$之间的$m$位的随机数，需要$O(nm)$的时间。

#####

试了一下新的策略：

$g(x_1,x_2)={\max\{x_1,x_2\}}/(1+|x_1-x_2|)$，

结果为$0.2190061\pm 0.0000005$，

比zgg____的原始策略$g(x_1,x_2)=(x_1+x_2+1/2*p)/(2+p)$好，

但比zgg____改进后的策略稍微差了一丁点儿。

由于新的策略还没有带参数，所以可以改进的余地很大。

该策略带了参数之后能不能刷新目前的记录呢？请静候佳音

dianyancao

若吃过的豆子位置均值接近1/2
关于预测下一个豆子有什么好办法，下一个豆子的权重设置为多少，会更符和随机数的分布？

wayne

直接先验的假设Puffin (一只可爱的海鸟) 的位置的概率分布是稳定的，即时不变的(time-invariant)，我暂时还不能接受。
按我的思路，就当做一个时间序列的问题来做：
引入时间这个量，以吃豆子个数来标定，即t时刻就是Puffin已经吃掉t个豆子的时候。

豆子x₁ x₂的在t时刻的位置$x_1(t)$,$x_2(t)$均服从均匀分布，即概率密度函数是1，我们暂时搁置着。
接下来，我们集中注意力讨论Puffin的位置的概率分布情况。
1) Puffin未来时刻的位置$w(t+1)$只可能取值$x_1(t)$,$x_2(t)$  2种。
2) $w(t+1)$只与祂当前的位置$w(t)$有关，与过去的$w(t-1),w(t-2),...,w(0)$无关， 俗称具有一阶马尔科夫性质，
     即Puffin在位置$w(t+1)$处的概率函数应该是 $f(w(t),x_1(t),x_2(t))$，(其中$w(0),x_1(t),x_2(t)$ 是服从均匀分布的随机变量)，
3) Puffin不可能舍近求远的吃豆子，又由于新豆子只在吃完一个豆子才出现，所以必定有
   $w(t+1) =x_1(t)$, when $w(t)<x_1(t)<x_2(t)$
   $w(t+1) =x_2(t)$, when $x_1(t)<x_2(t)<w(t)$

mathe

对于一般情况$g(x_1,x_2)$,其中$0<x_1<x_2<1$,必然$g$关于$x_1,x_2$都是单调增，而且$x_1<g(x_1,x_2)<x_2$
我们记$g_0(x_2)=g(0,x_2)$,于是对于任意$g_0(x_2)<w<x_2$,都存在$x_1<x_2$使得$g(x_1,x_2)=w$,我们记为$x_1=h(w,x_2)$,也就是对于任意$g_0(x_2)<w<x_2<1$必然有$g(h(w,x_2),x_2)=w$,也就是相当于将$x_2$看成常数后h是g的逆。

在$w>g_0(c)$时
$d(c,w)=\int_0^{h(w,c)}(c-w)du+\int_{h(w,c)}^w(w-u)du+\int_w^c(u-w)du+\int_c^1(c-w)du={h(w,c)^2}/2+(c-2w)h(w,c)+w^2-w-{c^2}/2+c$
在$2w<g_0(c)$时为
$d(c,w)=\int_0^w(w-u)du+\int_w^c(u-w)du+\int_c^1(c-w)du=-c^2/2+w^2+c-w$
而最终平均移动距离为
$2\int_0^1\int_0^cp(c,w)d(c,w)dwdc$
其中特别的，如果我们选择$h(w,c)$总是线性函数（其中$h(g_0(c),c)=0,h(c,c)=c$),那么表达式将相对比较简单,可以同样用41#中类似代码计算。（其中应该包含了zgg的模型，但是Fans扩展的不行，h表达式比较复杂）。

mathe

而对于一般一些的函数h,如果h可以近似写成w,c的多项式，那么我们可以用44#的方法，对p进行多项式拟合，由于这是对于g函数只需要数值结果，所以可以通过h求出。而最后待积分表达式也就可以表示为w,c的高次多项式了，从而可以得出较好的结果

dianyancao

输出的值是布尔值，下一个位置只能是左边最近的豆子或右边最近的豆子
可以预测下一个豆子，当吃掉一个豆子后，局面才会发生变换
对于下一个豆子的预测位置x(.)，和其可信度T(.)，可以得到吃k+1个豆子的策略H(.)

如果进行预测的豆子更多，预测的豆子数量为d,如何得到吃k+d个豆子的策略呢？
（d个豆子是吃完当前豆子后,一个接一个出现的）

mathe

发现没法总是选择h也就是g是线性函数。这个是因为根据对称性，我们需要有g(w,c)=1-g(1-c,1-w).而线性的函数不满足这个条件。而满足这个条件，至少需要分段线性。所以至少要使用67#的方法拟合，那就要复杂很多了

dianyancao

谢谢KeyTo9_Fans的讲解，试试这个策略