凑百分概率游戏的扩展

KeyTo9_Fans

凑百分概率游戏的原版

http://bbs.emath.ac.cn/thread-2472-1-1.html

是一个比较简单的问题，因为每次赚取积分的期望值是一个恒定的值。

如果改变其中一些条件，这个问题可能会变得很困难。

首先是mathe提出的扩展：

扩展问题$1$：

要求积分恰好达到$100.8$，玩$120$次。求达成目标的概率和最佳策略。

Fans认为这是一个困难的问题，最佳答案不像原版中$11#$说的那么简单。

接下来是Fans想到的可能的扩展：

扩展问题$2$：

达到或超过$100$分，$99$次机会，要求不根据前面的得分情况一次性地输入$99$个数。求达成目标的概率和最佳策略。

扩展问题$3$：

达到或超过$100$分，$99$次机会，一次一次地玩。但赚分机制有所变化：

每次输入$x$，则只有$1/x^2$的概率得$x$分，否则得$0$分。

例如：输入$3$就只有$1/9$的概率得$3$分，$8/9$的概率得$0$分。

求达成目标的概率和最佳策略。

扩展问题$4$：

达到或超过$100$分，$99$次机会，要求不根据前面的得分情况一次性地输入$99$个数。

赚分机制同扩展问题$3$。

求达成目标的概率和最佳策略。

扩展问题$5$：

达到或超过$100$分，$99$次机会，要求不根据前面的得分情况一次性地输入$99$个数。赚分机制有所变化：

每次输入$x$，就有$1/x$的概率得$x^2$分，否则得$0$分。

例如：输入$3$就有$1/3$的概率得$9$分，$2/3$的概率得$0$分。

求达成目标的概率和最佳策略。

#####

另外补充一点：

以上扩展都是$1$个人在玩这个游戏。

如果两个人玩，就是一个博弈问题了：

两人都只选$1$个$x$值（只有$1$次赚分机会），得分高者胜，累计胜利局数（而不是积分）。

求不败策略。

此问题虽然已经被mathe秒掉了，在

http://tieba.baidu.com/f?kz=530627072

的22楼。

但Fans仍然很好奇mathe是如何得知密度函数是$u/x^3$的。

056254628

http://tieba.baidu.com/f?kz=530627072中
楼主的方案：  p(x)  表示概率密度
    x<1/3,    p(x)=0
    x >=1/3,  $p(x)=1/(4*x^3)$
-------------------------------------------------
那么无论 对方取什么方案：   楼主的方案都是最优的。
    1. 对方固定取一个值a.   
   2.  对方等概率取任何数。p(x)=1
-------------------------------------------------------------
那么如果对方的方案是：
    x<s,   p(x)=0
   x>=s, P(x)=u/x^n        其中$u=(n-1)/(1/s^(n-1)-1)$
               s,n任意设定。
-----------------------
那么为什么  s=1/3,n=3的方案是最佳的。
请教大师们！

mathe

那个是挺久以前的问题了，现在想不起来当初是怎么计算的。
首先我们需要将模型用数学公式描述出来，假设最佳方案的概率密度函数为p(x),那么就是说，对于对手的任意一个概率密度函数策略q(y),我们都有
$\int_0^1yq(y)dy\int_0^yxp(x)dx+\int_0^1(1-y)q(y)dy\int_0^1xp(x)dx>=\int_0^1yq(y)dy\int_y^1xp(x)dx+\int_0^1yq(y)dy\int_0^1(1-x)p(x)dx$

mathe

于是我们可以记$T(y)=\int_0^yxp(x)dx,S=\int_0^1yq(y)dy$,,得到
$\int_0^1 yq(y)T(y)dy+(1-S)T(1)>=\int_0^1yq(y)(T(1)-T(y))dy+S(1-T(1))$
$int_0^1yq(y)T(y)dy>={T(1)S+S-T(1)}/2$
其中函数T(y)单调增,q(y)为任意密度函数

mathe

然后我们可以试着选择一些特别的函数q(y),比如$q(y)=a{exp(-ax)}/{1-exp(-a)}$

mathe

首先我们应该可以证明对于最佳的T(x),对于任意$x<1/3,T(x)=0$,然后，可以选择类似5#的函数q(y)，但是让$y<1/3$时$q(y)=0$,然后让这些q(y)不等式变成等号，于是，我们可以得到T(x)的Laplace变换。不过这个方法可能计算量稍微有点大