|
|
 |
Условие
Преподаватель кружка по теории вероятностей откинулся в кресле и посмотрел на экран. Список записавшихся готов. Всего получилось n человек. Только они пока не по алфавиту, а в случайном порядке, в каком они приходили на занятие.
"Надо отсортировать их в алфавитном порядке, – подумал преподаватель. – Пойду по порядку сверху вниз, и, если нужно,
буду переставлять фамилию ученика вверх в подходящее место. Каждую фамилию придётся переставить не более одного раза".
Докажите, что математическое ожидание числа фамилий, которые не придётся переставлять, равно 1 + ½ + ⅓ + ... + 1/n.
Решение
Введём для каждого k индикатор Ik, который равен 1, если k-ю по списку фамилию не нужно переставлять, и 0, если нужно. Общее число фамилий, которые не надо переставлять, равно I1 + I2 + ... In.
Фамилию номер k не нужно переставлять, если и только если среди первых k фамилий она последняя по алфавиту. Поскольку среди этих
k фамилий она с равными шансами может оказаться на любом из
k мест по алфавиту, вероятность того, что она оказалась по алфавиту последней, равна 1/k. Следовательно, математическое ожидание числа не переставляемых фамилий равно 1 + ½ + ⅓ + ... + 1/n.
