凑百分概率游戏的扩展

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)=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变换。不过这个方法可能计算量稍微有点大