arrays - 尝试在随机数字数组中查找运行最大值时调用了多少次更新最大值？

Question

假设我们有一个整数数组 -N 到 N，数组大小为 2N + 1。我们首先打乱数组中的元素，然后尝试通过从第一个元素到第一个元素遍历数组来找到最大整数最后一个元素:(代码示例在 Java 中)

int called = 0;
int max = Integer.MIN_VALUE;
for (int i : array) {
    if (i > max) {
        called++;
        max = i;
    }
}

遍历数组后 called 值的期望值(多次运行的平均值)是多少？

编辑:

我如何发现它接近 ln(array.length):

public static void main(String args[]) {
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < 1000000; i++) list.add(i);

    int called = 0;
    int runs = 100;

    for (int i = 1; i <= runs; i++) {
        Collections.shuffle(list);
        int max = -1;
        for (int num : list) {
            if (num > max) {
                called++;
                max = num;
            }
        }
    }
    System.out.println("Expectation: " + called/runs);
}

Answer 1

让我们考虑随机打乱的数组。我们要估计 K - 第 i 个元素比其所有前任元素都大的次数。

K 的期望值等于第 i 个元素大于其所有前任元素的概率之和。 E(K) = Σ₁^2N+1 P_i.

现在我们要找到 P_i。考虑我们数组的长度为 i 的前缀。前缀中最后一个元素最大的概率是 1/i。所以我们有 P_i = 1/i。

因此:E(K) = Σ₁^2N+11/i。我们可以通过定积分将这个和估计为 ln(2N+1)+O(1)。

所以，答案是ln(2N+1)+O(1)。

还有蒙特卡洛模拟来证明:

constexpr size_t N = 1000;
std::array<int, 2 * N + 1> arr;
std::iota(arr.begin(), arr.end(), -N);
std::random_device rd;
std::mt19937 g(rd());
double moving = 0;
for (double trial = 1; trial < 10001; ++trial) {
    std::shuffle(arr.begin(), arr.end(), g);
    int called = 0;
    int max = std::numeric_limits<int>::min();
    for (int i = 1; i < arr.size(); ++i) {
        if (arr[i] > max) {
            ++called;
            max = arr[i];
        }
    }
    if (trial > 1) {
        moving = moving * ((trial - 1) / trial) + called / trial;
    }
    else {
        moving = called;
    }
}
cout << "actual:   " << moving << endl;
cout << "expected: " << std::log(2 * N + 1) << " + O(1)" << endl;

actual:   8.1581   
expected: 7.6014 + O(1)