<<
>>

Пример: угадывание карт

Чтобы поразить ваших друзей, вы предлагаете им перетасовать колоду из 52 карт, а затем открывать по одной карте. Вы пытаетесь угадать, какая карта будет открыта следующей. К сожалению, ваши способности к ясновидению оставляют желать лучшего, а память не позволяет точно запомнить уже открытые карты, поэтому ваша стратегия заключается в простом случайном равномерном выборе карты из полной колоды.
Сколько попыток окажутся успешными?

Рассмотрим более общую формулировку задачи: колода состоит из n разных карт, а X — случайная переменная, равная количеству правильных предсказаний. Существует неожиданно простой способ вычисления X: случайная переменная X. (для i = 1, 2, ..., n) определяется равной 1, если i-е предсказание было правильным, и 0 в противном случае. При этомX=X1 + X2 + ... + Xn, и

⅜] = О⅛г[А, =Оj + l∙Рг[,⅝', =]]= Рr{ЛТ, = !] = -.

Стоит отметить полезный факт, который неявно следует из предыдущих вы- числений: если Z — случайная переменная, принимающая только значения 0 и 1, то E[Z] = Pr[Z = 1].

п

и

Итак, нам удалось доказать следующее:

(13.9) Ожидаемое количество правильных предсказаний в стратегии без запо- минания равно 1 независимо от n.

Попытка вычислить E[X] непосредственно из определения

создаст куда больше проблем, потому что это потребует гораздо более сложного суммирования. За внешне безобидным утверждением (13.8) скрывается значитель- ный уровень сложности.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Пример: угадывание карт:

  1. § 8. Обязательства по расчетам с использованием банковских карт
  2. 6. Расчеты с использованием платежных карт.
  3. 1. Особенности расчетных обязательств с использованием банковских карт
  4. 3. Исполнение расчетных обязательств с использованием банковских карт
  5. 2. Система договоров при расчетах с использованием банковских карт
  6. Примеры жестокости по отношению к другим (эти примеры более всего относятся к семейной жизни):
  7. ПРИМЕР 2
  8. Пример 1.
  9. ПРИМЕР 2
  10. Пример 2.
  11. Пример 2.
  12. Пример 2.
  13. Пример.
  14. ПРИМЕР
  15. Действенность примеров
  16. ПРИМЕР 2
  17. Пример 4.