确定一个排列需要随机比较多少次？

KeyTo9_Fans

假设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$的期望值？

rayfekeeper

显然，分奇偶性考虑，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))

wayne

2# rayfekeeper
这个m是 使得N!/(2^m)为整数的最大m吗

KeyTo9_Fans

“只需抽到最小的$(N-1)$次有效信息”

我觉得这是对的。

“最大值为$(N!)/(2^m)<=1$”

我觉得不对。最大值没有上界。因为KeyTo9_Fans可能会多次告诉mathe同一对牌的大小关系。

zeroieme

有效量的确是N-1，就要碰到次序相邻两牌的信息。
其实问题变为摸C(N,2)个球，指定的N-1个球至少出现1次的概率。

zeroieme

这样可以把球分成有用球和无用球。

首先是(N-1)个有用球与C(N,2)-(N-1)个无用球，摸到有用球的概率是q₁= $(N-1)/(C(N,2))$
于是得到第一个有用球的期望E₁是1/q₁

接着第一个有用球沦为无用球，我们需要的是另(N-2)个有用球，q₂= $(N-2)/(C(N,2))$
E₂是1/q₂

…………
最后我们默默等待最后需要的那个球q_n-1= $1/(C(N,2))$
E_n-1=1/q_n-1


E₁+E₂……+E_n-1

超越函数？

KeyTo9_Fans

6# zeroieme

你是对的。

提问之前我还以为“随机比较”是确定一个排列的好方法，比“两两比较”高效多了。（即$M$的期望值小于$C(N,2)$）。

现在看来“随机比较”根本就不是好方法。$M$的期望值比$C(N,2)$还要大。

根据$6#$ zeroieme的结果，我们有以下猜想：

$M$的期望值是$O(N^2\log(N))$。

该猜想是否成立呢？

我们期待进一步的讨论。

zeroieme

7# KeyTo9_Fans


E₁=1/q₁=$1/((N-1)/(C(N,2)))=(C(N,2))/(N-1)$
E₂=$(C(N,2))/(N-2)$
……
所以M=HarmonicNumber[N-1] C(N,2)

KeyTo9_Fans

查阅了一下：

http://mathworld.wolfram.com/HarmonicNumber.html

发现楼上的结果比$7#$的猜想准确多了，是该问题的精确解。