确定一个排列需要随机比较多少次？
假设KeyTo9_Fans和mathe玩这样一个游戏：有$N$张扑克牌，KeyTo9_Fans和mathe都知道这$N$张扑克牌从大到小是如何排列的。
现在KeyTo9_Fans将这$N$张扑克牌随意排列，排好后让mathe来猜排列顺序。
如果mathe不能确定排列顺序，KeyTo9_Fans就随机选择$2$个位置（每个位置被选中的概率均等【注释$1$】），告诉mathe这$2$个位置上的牌哪张大。
不断重复上面这个步骤，直到mathe可以确定这$N$张扑克牌的排列顺序为止。
假设KeyTo9_Fans一共告诉了mathe$M$次大小关系，问：$M$的期望值是多少？（用含有$N$的式子表示）
——————————
注释$1$：更严格的表述是，$N$个位置选$2$个位置一共有$C(N,2)$种方案，对于每种方案，无论是否被选过，每次被选中的概率相等，均为$1/{C(N,2)}$。
例$1$：当$N=1$时，KeyTo9_Fans不用告诉mathe任何大小关系，所以$M=0$。
例$2$：当$N=2$时，KeyTo9_Fans只需告诉mathe$1$次大小关系，所以$M=1$。
当$N>2$时，情况比较复杂，应该如何计算$M$的期望值？ 显然，分奇偶性考虑，M的最小值均为N-1,最大值为N!/(2^m)<=1,
其他的次数可理解为只需抽到最小的N-1次有效信息，其他的次数均为无效替补信息。则有：
E(m)=(N-1)*1/((N(N-1)/2),(N-1))+N*((N*(N-1)/2-(N-1)),(1))/((N*(N-1)/2),(N))+……+N*((N*(N-1)/2-(N-1)),(m))/((N*(N-1)/2),(m)) 2# rayfekeeper
这个m是 使得N!/(2^m)为整数的最大m吗 “只需抽到最小的$(N-1)$次有效信息”
我觉得这是对的。
“最大值为$(N!)/(2^m)<=1$”
我觉得不对。最大值没有上界。因为KeyTo9_Fans可能会多次告诉mathe同一对牌的大小关系。 有效量的确是N-1，就要碰到次序相邻两牌的信息。
其实问题变为摸C(N,2)个球，指定的N-1个球至少出现1次的概率。 这样可以把球分成有用球和无用球。
首先是(N-1)个有用球与C(N,2)-(N-1)个无用球，摸到有用球的概率是q1= $(N-1)/(C(N,2))$
于是得到第一个有用球的期望E1是1/q1
接着第一个有用球沦为无用球，我们需要的是另(N-2)个有用球，q2= $(N-2)/(C(N,2))$
E2是1/q2
…………
最后我们默默等待最后需要的那个球qn-1= $1/(C(N,2))$
En-1=1/qn-1
E1+E2……+En-1
超越函数？ 6# zeroieme
你是对的。
提问之前我还以为“随机比较”是确定一个排列的好方法，比“两两比较”高效多了。（即$M$的期望值小于$C(N,2)$）。
现在看来“随机比较”根本就不是好方法。$M$的期望值比$C(N,2)$还要大。
根据$6#$ zeroieme的结果，我们有以下猜想：
$M$的期望值是$O(N^2\log(N))$。
该猜想是否成立呢？
我们期待进一步的讨论。 7# KeyTo9_Fans
E1=1/q1=$1/((N-1)/(C(N,2)))=(C(N,2))/(N-1)$
E2=$(C(N,2))/(N-2)$
……
所以M=HarmonicNumber C(N,2) 查阅了一下：
http://mathworld.wolfram.com/HarmonicNumber.html
发现楼上的结果比$7#$的猜想准确多了，是该问题的精确解。
页:
[1]