Ожидаемое количество инверсий - от введения к алгоритмам Cormen

Пусть A [1.. n] - массив чисел n distinct. Если я < j и A [i] > A [j], то пара (i, j) называется инверсией A. (См. задачу 2-4 для большей части инверсий.) Предположим, что каждый элемент из A выбирается случайным образом независимо, и равномерно от 1 до n. Используйте случайные переменные индикатора индикатора для вычисления ожидаемого числа инверсий.

Проблема заключается в упражнении 5.2-5 во введении к алгоритмам Кормена. Вот мое рекурсивное решение:

Предположим, что x (i) - число инверсий в [1..i], а E (i) - ожидаемое значение x (i), тогда E (i + 1) можно вычислить следующим образом:
У нас есть i+1 положения, чтобы поместить все числа, если поместить я + 1 в первую позицию, тогда x (i + 1) = я + x (i); если мы поместим я + 1 во вторую позицию, то x (i + 1) = i-1 + x (i),..., поэтому E (i + 1) = 1/(i + 1) * sum ( k) + E (i), где k = [0, i]. Наконец, получим E (i + 1) = i/2 + E (i).
Поскольку мы знаем, что E (2) = 0,5, поэтому мы получаем рекурсивно: E (n) = (n-1 + n-2 +... + 2)/2 + 0,5 = n * (n-1)/4.

Хотя вывод выше, кажется, прав, но я все еще не очень уверен в этом. Поэтому я разделяю его здесь.

Если что-то не так, пожалуйста, поправьте меня.

Ответы

Ответ 1

Я думаю, что это правильно, но я считаю, что правильный способ доказать это - использовать условные ожидания:

для всех X и Y имеем: E [X] = E [E [X | Y]]

то в вашем случае:

E (i + 1) = E [x (i + 1)] = E [E [x (i + 1) | x (i)]] = E [SUM (k)/(1 + i) + x (i)] = i/2 + E [x (i)] = i/2 + E (i)

о втором утверждении:

if:

E (n) = n * (n-1)/4.

то E (n + 1) = (n + 1) * n/4 = (n-1) * n/4 + 2 * n/4 = (n-1) * n/4 + n/2 = E (n) + n/2

Итак, n * (n-1)/4. проверьте рекуррентное соотношение для всех n >= 2 и проверим его при n = 2

Итак, E (n) = n * (n-1)/4

Надеюсь, я понял вашу проблему, и она помогает

Ответ 2

Все решения кажутся правильными, но проблема говорит о том, что мы должны использовать индикаторные случайные величины. Итак, вот мое решение, используя то же самое:

    Let Eij be the event that i < j and A[i] > A[j].

    Let Xij = I{Eij} = {1 if (i, j) is an inversion of A

                        0 if (i, j) is not an inversion of A}

    Let X = Σ(i=1 to n)Σ(j=1 to n)(Xij) = No. of inversions of A.

    E[X] = E[Σ(i=1 to n)Σ(j=1 to n)(Xij)]

         = Σ(i=1 to n)Σ(j=1 to n)(E[Xij])

         = Σ(i=1 to n)Σ(j=1 to n)(P(Eij))

         = Σ(i=1 to n)Σ(j=i + 1 to n)(P(Eij)) (as we must have i < j)

         = Σ(i=1 to n)Σ(j=i + 1 to n)(1/2) (we can choose the two numbers in
                                            C(n, 2) ways and arrange them
                                            as required. So P(Eij) = C(n, 2) / n(n-1))

         = Σ(i=1 to n)((n - i)/2)

         = n(n - 1)/4

Ответ 3

Другое решение еще проще, IMO, хотя оно не использует "индикаторные случайные величины".

Так как все числа различны, каждая пара элементов является либо инверсией (i < j с A[i] > A[j]), либо неинверсией (i < j с A[i] < A[j]). Иными словами, каждая пара чисел находится в порядке или не в порядке.

Итак, для любой заданной перестановки общее число инверсий плюс неинверсии - это просто общее число пар или n*(n-1)/2.

По симметрии "меньше" и "больше, чем" ожидаемое число инверсий равно ожидаемому числу неинверсий.

Так как ожидание их суммы составляет n*(n-1)/2 (константа для всех перестановок), и они равны, каждая из них равна половине или n*(n-1)/4.

[Обновить 1]

По-видимому, моя "симметрия" выражения "меньше" и "больше чем" требует некоторой разработки.

Для любого массива чисел A в диапазоне от 1 до n определите ~A как массив, который вы получите, вычитая каждое число из n+1. Например, если A - [2,3,1], то ~A - [2,1,3].

Теперь заметим, что для любой пары чисел из A, находящихся в порядке, соответствующие элементы ~A не соответствуют порядку. (Легко показать, потому что отрицание двух чисел обменивает их порядок.) Это сопоставление явно показывает симметрию (двойственность) между меньшим и большим, чем в этом контексте.

Итак, для любого A число инверсий равно числу неинверсий в ~A. Но для всех возможных A соответствует ровно один ~A; когда числа выбираются равномерно, обе A и ~A одинаково вероятны. Поэтому ожидаемое число инверсий в A равно ожидаемому числу инверсий в ~A, поскольку эти ожидания вычисляются по тому же самому пространству.

Следовательно, ожидаемое число инверсий в A равно ожидаемому числу неинверсий. Сумма этих ожиданий - это ожидание суммы, которая является константой n*(n-1)/2 или общим числом пар.

[Обновить 2]

Простая симметрия: для любого массива A элементов n определите ~A как одни и те же элементы, но в обратном порядке. Свяжите элемент в позиции i в A с элементом в позиции n+1-i в ~A. (То есть, свяжите каждый элемент с самим собой в обратном массиве.)

Теперь любая инверсия в A связана с неинверсией в ~A, как и при построении в обновлении 1 выше. Таким образом, применяется тот же аргумент: число инверсий в A равно числу инверсий в ~A; оба A и ~A являются одинаково вероятными последовательностями; и др.

Точка интуиции здесь состоит в том, что операторы "меньше" и "больше" являются просто зеркальными изображениями друг друга, которые вы можете увидеть либо путем отрицания аргументов (как в обновлении 1), либо путем их замены ( как в обновлении 2). Таким образом, ожидаемое количество инверсий и неинверсий одинаково, поскольку вы не можете определить, просматриваете ли вы какой-либо конкретный массив через зеркало или нет.

Ответ 4

Еще проще (аналогично Аману выше, но, возможно, более ясному)...

Let Xij be a random variable with Xij=1 if A[i] > A[j] and Xij=0 otherwise.
Let X=sum(Xij) over i, j where i < j

Number of pairs (ij)*:               n(n-1)/2
Probability that Xij=1 (Pr(Xij=1))): 1/2
By linearity of expectation**:       E(X) = E(sum(Xij))
                                          = sum(E(Xij))
                                          = sum(Pr(Xij=1))
                                          = n(n-1)/2 * 1/2
                                          = n(n-1)/4

*  I think of this as the size of the upper triangle of a square matrix.
** All sums here are over i, j, where i < j.

Ответ 5

Использование индикаторных случайных величин:

Пусть X = случайная величина, равная числу инверсий.
Пусть Xij = 1, если A [i] и A [j] образуют инверсионную пару, а Xij = 0 в противном случае.
Число пар инверсии = Сумма за 1 <= я < j <= n of (Xij)
Теперь P [Xij = 1] = P [A [i] > A [j]] = (n выбрать 2)/(2! * n выбрать 2) = 1/2
E [X] = E [суммирование по всем ij-парам таким образом, что я < j of Xij] = сумма по всем парам ij, такая, что я < j из E [Xij] = n (n - 1)/4