Victor Isaev (torrio) wrote,
Victor Isaev
torrio

Categories:

Датчики дождя и сложные решения простых задач

Саша Якунин рассказал о задачке на теорию вероятностей:
Есть два сенсора дождя, работающие с 75% точностью.
Оба говорят, что идёт дождь.
Какова вероятность того, что дождь действительно идёт?

К нам в гости прилетел dfyz и я рассказал ему о задачке. Сели решать, вспоминать теорию вероятностей.

Для начала решили определить, а независимые ли вообще датчики? Есть основания полагать, что нет: если, скажем, датчик основывается на величине влажности (относительной, абсолютной), и правильно откалиброван, то два датчика будут давать ответы совершенно синхронно, одинаковые. В этом случае совершенно неважно, сколько датчиков в системе, один или много, и можно применять формулу для случая с одним датчиком.

Дальше предположили, что датчики выдают результаты и ошибаются независимо (например, случайным образом в 25% случаев ответ меняется на противоположный).

Какой подход использовать дальше?
1. Один вариант - расписать вероятность по формуле Байеса. Сразу становится ясно, что для ответа нужно знать априорную вероятность дождя: действительно, если дождь идёт всегда, то вы находитесь в Сиэттле и ваш сенсор дождя ошибается только если говорит, что дождя нет.
А если вы находитесь в Сахаре, но напротив, датчик будет врать в тех случаях, когда будет утверждать, что идёт дождь.
Это вообще важное интуитивное соображение: типы ошибок (false positive, false negative) распределены неравномерно, кроме возможно единственного частного случая с априорной вероятностью дождя 50%.

Дальше всё просто, остается только расписать полную вероятность в знаменателе, и получаем ответ.

2. Второй вараинт: интуитивное решение. Для двух датчиков, оба из которых говорят "идёт дождь" расписываем 4 варианта возможных (или невозможных) событий:
A: 1 и 2 говорят правду
B: 1 лжёт, 2 говорит правду
C: 1 говорит правду, 2 лжёт
D: оба лгут

События B & C неосуществимы: они означали бы, что дождь одновременно идёт и не идёт, что невозможно.
"Вероятность" события A: PA = 0.75 * 0.75 * априорную вероятность дождя.
"Вероятность" события D: PD = 0.25 * 0.25 * (1 - априорная вероятность дождя).
A и D покрывают пространство осуществимых событий полностью, сумма их вероятностей должна быть равна 1, поэтому для получения ответа нормируем поделив на (PA + PD):

X = PA / (PA + PD).

Для случая с произвольным числом датчиков оба решения обобщаются одинаковым образом, получающиеся формулы совпадают.

Для проверки sanity прогнали ответ черези симуляцию, сравнили результаты вычислений с симуляцией "сломанных датчиков", всё совпало.
Photo Apr 07, 11 13 12 PM
Photo Apr 07, 11 13 31 PM
Photo Apr 07, 11 13 37 PM


Код решения для задачи с разными априорными вероятностями дождя и разным количеством сенсоров
Tags: США, друзья, программирование, спорт и туризм
Subscribe

  • Ненавязчивый русский мир

    Не удержусь. В общем, судьба-злодейка забросила меня в Домодедово на ночь. Еще из Франкфурта я забронировал отель и, несмотря на внезапную поломку…

  • Три источника

    Как сообщила нам группа "Крематорий", у творчества есть три источника - тунеядство, пьянство, блядство. Спорить с классиками трудно, а местами и…

  • Член семьи врага народа

    Дочитал я "Остров Крым" и, признаюсь, в конце книги плакал. Не знаю, может быть, прочти я книгу года два-три назад, такой эмоциональной реакции не…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments