公平竞赛问题

mathe

现在有一个挑战项目，每次一个选手挑战，过关概率为p.选手们按一定顺序出场挑战，直到某个选手过关，游戏结束。（选手可以多次出场）
现在假设只有三个选手，请问该如何安排出场顺序，使得三人赢得游戏的概率尽量接近。

gxqcn

每三局，让选手抓阄或猜拳决定排队顺序，是否公平？

mathe

要求选手出场顺序事先确定好

fungarwai

我觉得最公平应该是没有的，但倒是可以考虑他们概率和的方差最小使得比赛更公平
p=0.1
     3     1     2     2     3     1     2     3     1     1     2     1     3     3     2
p=0.9
     1     2     3     3     3     2     3     3     3     2     3     2     3     3     2
概率太高的话显然是第一个会非常有优势

zhouguang

我感觉对于n个选手的情形，只要p不大于1/n，就能实现公平。

zhouguang

比方说，对于n=3，p=1/3的特例，第一个选手去试下，这一次就恰好用尽了他的全部机会，如果他失败了，就只有剩下的两个选手可以有过关的机会了。
于是这个特例就等效于如下问题：
如何将无穷数列“2/3、(2/3)^2、(2/3)^3、(2/3)^4、……、(2/3)^k、……”平均分为两部分，即求一个正整数集合{k}，使sum((2/3)^k)等于1。
这个问题在直觉上是有解的，但是结果是不容易构造的。

zhouguang

对于p不大于1/n的情形，只要每次都让现有已获得通关几率最小的那个选手去闯关就可以了。（这是一个方案，但不是唯一或最佳的方案。）

l4m2

buchong补充一个问题：顺序有几种可能性？

zeroieme

第n场发生的概率是$(1-p)^(n-1)$即前面n-1场都失败了。由此，在第n场胜利的概率修正为$p*(1-p)^(n-1)$
假如A选手分配场次为$(x_1、x_2、……)$场，那么他胜利的总概率是$p*sum((1-p)^(x_i -1))$ 令这个总概率接近1/3 。因为假设有三个选手，同样B选手的$(y_1、y_2、……)$及C选手$(z_1、z_2、……)$也要接近1/3

所以$p>1/3$是明显不公平的。如果固定数字p可以考虑贪婪算法，是否存在循环分配

zeroieme

先放段代码

1. Module[{a={1},b={2},c={3},p=1/10,ap,bp,cp},
   
2. Do[
   
3. ap=Total[p (1-p)^(#-1)&/@a];
   
4. bp=Total[p (1-p)^(#-1)&/@b];
   
5. cp=Total[p (1-p)^(#-1)&/@c];
   
6. If[cp==Min[ap,bp,cp],AppendTo[c,i],If[bp==Min[ap,bp,cp],AppendTo[b,i],AppendTo[a,i]]];
   
7. ,{i,4,600}];
   
8. Print[{a,b,c}];
   
9. Print[Length/@{a,b,c}](*检验长度，当p逼近1/3，abc不等长，下行转置命令出错*);
   
10. Print[Sort[Transpose[{#,{"a","b","c"}}]][[All,-1]]&/@Transpose[{a,b,c}]];
    
11. ]

复制代码