机器算法验证 - 从 1 到 N 无放回采样，当值小于前一个时停止 - 吾爱随笔录

从 1 到 N 无放回采样，当值小于前一个时停止

机器算法验证可能性分布采样期望值模拟

2022-04-08 12:01:06

我遇到了一个问题如下

假设一个系列包括从 1 到 N 的整数。每次采样一个整数而不从系列中替换。该过程继续，如果 $X_{n}$ >= $X_{n-1}$ ，和 $X_{n}$ 将被保存到另一个系列 $X_{s}$ . 这个过程不会停止，直到 $X_{n}$ < $X_{n-1}$ .

然后它询问预期长度 $X_{s}$ .

下面我尝试在 Python 中模拟输出


import numpy as np

def gen():

    '''
    return length of X_s
    '''

    N = 10000

    raw_data = list(np.arange(N))  #1,2,3,...,N
    X_s = []

    last_value = - float('inf')
    for _ in range(N):
        cur_value = np.random.choice(raw_data)
        raw_data.pop(cur_value)
        if cur_value >= last_value:
            last_value = cur_value
            X_s.append(last_value)
        else:
            break
    return len(X_s)    

a = [gen() for _ in range(1000)]  # simulate 1000 times
np.mean(a)

结果在1.6~1.7左右。我正在寻找预期长度的封闭形式解决方案，有什么想法吗？

1个回答

让 $K$ 是由长度给定的随机变量，因此 $1\le K \le n.$ 它的生存函数是

S (k) = Pr (K > k) .

$S(k) = \Pr(K \gt k).$

事件 $K\gt k$ 可以表征为 $X_1 \lt X_2 \lt \cdots \lt X_k.$ 由于所有 $k!$ 可能的排序与随机抽样同样可能，这个事件有一个概率 $1/k!.$ 因此

S (k) = \frac{1}{k!}, k = 1, 2, \dots, n - 1.

$S(k) = \frac{1}{k!}, \ k = 1, 2, \ldots, n-1.$

微不足道， $S(0) = 1$ 和 $S(k) = 0$ 对于积分 $k \ge n$ （因为序列 $(X_i)$ 之后必须停止 $n$ 观察：没有什么可以采样的）。 这个简单的公式描述了整个分布 $K.$

根据非负整数变量期望的一般公式 $E[K] = \sum_{k=0}^\infty S(k),$ 答案是

$E [K] = 1 + 1 + 1 / 2 + 1 / 3! + \dots + 1 / (n - 1)! .$ $E[K] = 1 + 1 + 1/2 + 1/3! + \cdots + 1/(n-1)!.$

对于大 $n$ 这非常接近，但小于， $e = \exp(1) \approx 1 + 1.71828\ldots.$ 后一个值（一个小于 $E[K]$ ) 可能是您的模拟估计的数字。

这是一个R跟踪的模拟 $K$ 对于许多样本和（当 $n \gt 2,$ 因为对于 $n \le 2$ 长度总是 $n$ ) 执行卡方检验以将观察到的分布与此计算进行比较：

n <- 3
s <- tabulate(replicate(1e4, {
  x <- sample.int(n)       # A sample
  d <- diff(x)             # The successive changes
  min(n, which(d < 0) + 1) # The length, including the first drop (if any)
}), n)
if (n > 2) {
  p <- c(-diff(1 / factorial(1:(n-1))), 1 / factorial(n-1)) # Computed distribution
  chisq.test(s[-1], p=p)                                    # (`s[-1]` is always zero)
}

运行后我发现 $5078$ 实例 $K=2$ 和 $4922$ 在哪里 $K=3.$ 卡方统计量的 p 值为 $0.12:$ 没有重要证据表明该公式是错误的。以较大的值运行 $n$ 继续确认答案的正确性。

其它你可能感兴趣的问题

上一篇为什么变压器架构中需要残差连接？下一篇使用 GLM 进行预测