概率论笔试题

Question

朋友参加笔试遇到的，题面如下：

给定一个长度为n正整数序列，使用任何一个排序算法可以产出一个排好序的序列，现在假定用于排序的比较俩个整数大小的函数现在由于某种原因会出错，比如比较 5和8原本会正确输出5 < 8, 但是现在以某一概率p会出现返回5 > 8, 在此情形下，并且排序算法并不知情的前提下，就是依旧按原排序算法但基于这个以p概率出错的比较器来排的情况下，问前m (m < n)个里面，原本如果比较器不错正确排序情况下也应在前m里面的数的期望是多少？可以分各种情形分析，闭式解答困难的话近似估计或某些m，n，p组合下的任何观察，近似结论都欢迎。

我数学不大好，只能凭感觉抛块砖：

1. 如果 p = 0.5 ，前m个数的期望应当是所有数的平均值。

2. p越接近1，那么数列就越接近有序（正序），前m个数的期望应当越接近最小的m个数的平均值；p越接近0就正好相反。

看了下@依云的回答，发现自己对题意理解有错，上面的砖头只是针对前m个数，而不是前m个数里头“本应在前m里头”的数的期望。

欢迎继续讨论。

Answer 1

有点意思。

以下是测试程序：

import random
from functools import cmp_to_key

ans = []

for p_ in range(100):
  p = p_ / 100
  def mycmp(a, b):
    if random.random() < p:
      return -(a - b)
    else:
      return a - b

  n = 100
  m = 50

  s = 0
  for i in range(100):
    L = sorted(range(n), key=cmp_to_key(mycmp))
    v = len(set(L[:50]) & set(range(m)))
    print(v)
    s += v
  print('avg:', s/100)
  ans.append((p_, s/100))

with open('ans.txt', 'w') as f:
  f.writelines('%s %s\n' % x for x in ans)

以下是结果（n=100, m=50/30）：