Экзамен ААА — Дискретное любимое: оптимальное распределение по критерию

Условие

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

P(X = 1) ≥ P(X = 2) ≥ ... ≥ P(X = K)

То есть, вероятности невозрастают по i = 1, 2, …, K. Жан Жан хочет посчитать, какое такое распределение даёт максимум/минимум некоторого функционала (например, дисперсии, энтропии или матожидания при фиксированных условиях).

Формулировка задачи

1. Покажите, что у случайной величины X с дискретным распределением и P(X=i) ≥ P(X=i+1), при условии что Σ P(X=i) = 1, матожидание E[X] минимально/максимально достигается на каком-то конкретном виде распределения.
2. Можно посчитать матожидание X для пункта а. Подробнее обоснуйте полученный результат.

Решение

Постановка

Дано: p_1 ≥ p_2 ≥ … ≥ p_K, Σ p_i = 1, p_i ≥ 0. Найти экстремум функционала

E[X] = Σ_{i=1..K} i · p_i

по всем таким распределениям.

Минимум E[X]

Хотим минимизировать Σ i · p_i при ограничениях p_1 ≥ p_2 ≥ … ≥ p_K ≥ 0, Σ p_i = 1.

Перепишем через приращения. Пусть q_i = p_i − p_{i+1} ≥ 0 (где p_{K+1} = 0). Тогда p_i = q_i + q_{i+1} + … + q_K = Σ_{j ≥ i} q_j. Условие:

Σ_i p_i = Σ_i Σ_{j ≥ i} q_j = Σ_j j · q_j = 1

Функционал:

E[X] = Σ_i i · p_i = Σ_i i · Σ_{j ≥ i} q_j = Σ_j q_j · Σ_{i=1..j} i = Σ_j q_j · j(j+1)/2

Минимизируем Σ_j q_j · j(j+1)/2 при Σ_j j · q_j = 1, q_j ≥ 0.

Минимум линейного функционала по q_j ≥ 0 с одним линейным ограничением — это вершина симплекса: всё в одну q_j с минимальным (j(j+1)/2) / j = (j+1)/2.

(j+1)/2 минимально при j = 1: q_1 = 1, остальные q_j = 0.

q_1 = 1, q_2 = … = q_K = 0 → p_1 = 1, p_2 = … = p_K = 0.

E[X] = 1.

Максимум E[X]

(j+1)/2 максимально при j = K: q_K = 1/K, остальные 0.

Это даёт p_i = 1/K для всех i = 1..K (равномерное распределение).

E[X] = Σ_{i=1..K} i · (1/K) = (K + 1)/2

Итог

Аналогия для дисперсии

Для дисперсии аргумент сложнее, но ответ:

• Минимум D[X] = 0 при вырожденной (p_1 = 1).
• Максимум D[X] при невозрастающем условии — НЕ равномерное, а двумерная конструкция; решается через уравнение Лагранжа.

Аналогия для энтропии

H(X) = − Σ p_i log p_i максимальна при равномерном распределении (бесусловно). С условием p_1 ≥ p_2 ≥ … ≥ p_K равномерное всё ещё подходит, поэтому максимум — log K.

Минимум H(X) при невозрастании — 0 при вырожденной (p_1 = 1).

Симуляция-проверка

import numpy as np
from scipy.optimize import linprog
 
K = 5
# Минимизация E[X] = sum i * p_i при p_1 >= p_2 >= ... >= p_K, sum p_i = 1, p_i >= 0.
c = list(range(1, K + 1))
A_ub = []
for i in range(K - 1):
    row = [0] * K
    row[i] = -1
    row[i + 1] = 1
    A_ub.append(row)  # p_{i+1} - p_i <= 0 → p_{i+1} <= p_i
b_ub = [0] * (K - 1)
A_eq = [[1] * K]
b_eq = [1]
 
res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=[(0, 1)] * K)
print("Min E[X]:", res.fun)
print("p:", res.x)
# → p = [1, 0, 0, 0, 0], E[X] = 1

Подводные камни

1. «Невозрастают» — нестрогое неравенство. Допустимы равенства, в т.ч. равномерное распределение.
2. Замена переменных через приращения q_i. Стандартный приём для задач со сравнением порядка вероятностей.
3. Линейный функционал на симплексе. Минимум/максимум — на вершинах. В вершине K − 1 ограничения активны → ровно одна свободная компонента.
4. Равномерное распределение — крайняя точка симплекса с условием невозрастания (когда все равны, ограничение p_i ≥ p_{i+1} активно как равенство).
5. Дисперсия в общем случае. Не сводится к линейным аргументам, требует Лагранжа.
6. E[X²] − (E[X])² для дисперсии — расчёт через Σ i² p_i − (Σ i p_i)².

Эталонный ответ

При условии p_1 ≥ p_2 ≥ … ≥ p_K, Σ p_i = 1:

• E[X] минимально = 1 при вырожденной p_1 = 1.
• E[X] максимально = (K+1)/2 при равномерной p_i = 1/K.

Доказательство — через замену q_i = p_i − p_{i+1} и сведение к линейному программированию на симплексе.