Глава 2: Прогнозирование президентских выборов с помощью моделирования Монте-Карло

В Лос-Анджелес Таймс был интересный опрос, потому что я всегда был в нем первым. У них было что-то, наверное, современное в опросах, это называлось энтузиазм. Они добавили фактор энтузиазма, и у моих людей был большой энтузиазм, а у людей [Клинтона] энтузиазма не было. — Дональд Трамп (Источник: NY Times)

Если вам нравится эта работа, присоединяйтесь к моим благотворительным занятиям по программированию: https://canvas.instructure.com/enroll/RKFKKP

Введение в моделирование методом Монте-Карло

Одним из многих странных аспектов президентских выборов в США 2016 года было то, что лишь немногие люди правильно предсказали результаты на основе данных опросов, включая статистиков из таких СМИ, как FiveThirtyEight и New York Times. Хотя эти СМИ постоянно предсказывали победу Клинтон, они значительно расходились во мнениях относительно вероятности этой победы (см. рисунок ниже).

СТОП. Обратите внимание, что на рисунке выше две диаграммы имеют одинаковую форму с течением времени. Как вы думаете, почему это так и что, по вашему мнению, вызвало колебания прогнозов?

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

Опросы по своей природе изменчивы. Поскольку мы можем отобрать только небольшой процент голосующих, мы можем только оценить истинный процент избирателей, поддерживающих кандидата. По этой причине большинство опросов включают погрешность или процентное значение по обе стороны от процента опроса. Например, опрос может указать 51 % поддержки одного кандидата с погрешностью 3 %. поддерживают этого кандидата от 48% до 54%.

Мы уделим немного времени обзору того, как проходят президентские выборы в США. Каждый из 50 штатов, наряду с округом Колумбия (округ Колумбия), получает два голоса выборщиков в дополнение к ряду других голосов выборщиков, которые напрямую связаны с их населением. За двумя исключениями (Мэн и Небраска) в каждом штате действует принцип победитель получает все; кандидат, набравший наибольшее количество голосов в штате, получает все голоса выборщиков в этом штате. Общее количество голосов составляет 538 (отсюда и название FiveThirtyEight), поэтому кандидат должен набрать 270 голосов, чтобы стать президентом.

Фактический процесс еще более сложен, поскольку голоса выборщиков используются для «избрания» членов партии от партии победившего кандидата. Это задумано — Коллегия выборщиков была создана, чтобы обеспечить последний барьер, не позволяющий американцам избрать крайне нежелательного кандидата. В 2016 году дезертировали рекордные семь из 538 избирателей (пять демократов и два республиканца), и все они проголосовали за того, кто не участвовал в выборах.

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

Ключевым моментом является то, что мы должны допустить некоторые различия в наших симуляциях, включив случайность, иначе все симуляции окажутся одинаковыми. Принцип использования большого количества рандомизированных симуляций для оценки желаемого результата называется моделирование по методу Монте-Карло.

Моделирование методом Монте-Карло повсеместно используется в практических приложениях. Когда ваш телефон сообщает вам, что вероятность дождя в 15:00 составляет 40 %, это происходит потому, что метеорологи провели множество симуляций и обнаружили, что дождь идет в 15:00 примерно в 40 % этих симуляций. Если вы хотите получить преимущество в ежедневном соревновании по фэнтези-спорту, вы можете запустить множество симуляций Монте-Карло на основе предыдущих результатов, чтобы определить сильный состав игроков. И еще один политический пример: если вы хотите доказать, что законодательные округа были распределены несправедливо, вы можете начертить множество политических карт случайным образом и сравнить, сколько округов поддерживает одну партию в симуляции и в реальности (см. рисунки ниже).

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

Оценка преимущества дома в крэпсе

Симуляция Монте-Карло получила свое название от знаменитого казино в Монако, поэтому давайте посмотрим, как случайная симуляция может ответить на вопрос об азартной игре. В частности, если вы играете в данную игру с фиксированной стратегией, какова ваша средняя выплата или проигрыш в одной игре с течением времени? Поскольку игры построены в пользу казино (или «заведения»), этот средний результат всегда является проигрышем для игрока и называется преимуществом заведения.

Мы можем вычислить преимущество казино в игре с помощью моделирования Монте-Карло, запрограммировав компьютер «играть» в игру миллионы раз с одной и той же стратегией. Компьютер суммирует общую сумму выигрыша/проигрыша по всем этим испытаниям, а затем делит эту выплату/проигрыш на количество испытаний.

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

Большинство игр в казино не являются бинарными, потому что выплаты в них зависят от результата, а также от решений игрока. Вместо этого мы сосредоточимся на простой бинарной формулировке craps, в которой игрок делает делает ставку и бросает два шестигранных кубика. Сумма костей при первом броске может быть обозначена как x, и есть три возможности.

Если x равно 7 или 11, то игрок выигрывает и получает свою ставку обратно в дополнение к сумме ставки.
Если x равно 2, 3 или 12, игрок проигрывает ставку.
Если x имеет другое значение, игрок продолжает бросать кости. При этих последующих бросках игра останавливается, если выпадает x, и в этом случае игрок выигрывает, или если выпадает 7, и в этом случае игрок проигрывает. (Обратите внимание, что это отличается от первого броска, когда 7 является победителем.)

Мы можем вычислить преимущество казино в игре в кости с помощью следующего псевдокода. Эта функция предполагает, что мы напишем подпрограмму PlayCrapsOnce, которая имитирует одну игру в кости и возвращает true, если игрок выигрывает, и false, если игрок проигрывает. Также обратите внимание, что цикл for не называет явной переменной, поскольку она не нужна внутри цикла.

ComputeHouseEdge(numTrials)
    count ← 0
    for numTrials total trials
        outcome ← PlayCrapsOnce()
        if outcome = true
            count ← count + 1
        else
            count ← count − 1
    return count/numTrials

Случайность в ComputeHouseEdge по-прежнему не очевидна, так как мы передали эту деталь в PlayCrapsOnce. Более того, функцию ComputeHouseEdge можно использовать для любой бинарной игры; реализация случайности и правила игры в кости будут переданы подпрограмме. Это пример парадигмы разработки программы, которую мы обсудим в одной из последующих глав.

СТОП. Прежде чем продолжить, попробуйте написать функцию PlayCrapsOnce, которая не принимает никаких параметров в качестве входных данных и возвращает true или false в зависимости от того, выиграл ли симулируемый игрок одну игру в кости. Вы должны предположить, что подпрограмма с именем SumTwoDice не принимает никаких входных данных и возвращает целое число от 2 до 12 на основе суммы двух смоделированных игральных костей.

Теперь мы напишем функцию PlayCrapsOnce. Обратите внимание, что эта функция не принимает никаких входных данных — нас интересует только результат игры, а правила игры встроены в функцию. Реализация этих правил будет основываться на наборе вложенных циклов и операторов if. Кроме того, нас до сих пор не интересуют детали рандомизации, поскольку мы передали их подпрограмме SumTwoDice. Вы можете просмотреть каждую строку приведенной ниже функции в качестве упражнения по интерпретации потока управления.

PlayCrapsOnce()
    firstRoll ← SumTwoDice()
    if firstRoll = 2, 3, or 12
        return false (player loses)
    else if firstRoll = 7 or 11
        return true (player wins)
    else
        while true
            newRoll ← SumTwoDice()
            if newRoll = firstRoll
                return true
            else if newRoll = 7
                return false

СТОП.Разве использование while true не приводит к бесконечному циклу? (Подсказка: вы думаете, что любой, кто играет в кости, когда-либо беспокоится о том, чтобы застрять между своим первым броском и концом игры?)

Мы уже знаем все управляющие структуры, необходимые для реализации ComputeHouseEdge и PlayCrapsOnce на компьютере, за исключением двух строк, которые просят нас вычислить сумму бросков двух игральных костей. Чтобы быть слишком точным, мы могли бы даже сформулировать это как вычислительную проблему.

Задача на сумму двух игральных костей

Ввод:(без ввода)

Вывод:сумма значений двух смоделированных шестигранных игральных костей.

Нам просто нужно реализовать рандомизированный процесс броска двух игральных костей; насколько это может быть тяжело?

Подводные камни генерации (псевдо)случайных чисел

Генератор псевдослучайных чисел среднего квадрата фон Неймана

Найдите минутку, чтобы придумать несколько случайных цифр. (Вот мои: 6, 1, 2, 8, 0, 3, 3, 0, 8, 0, 0, 4, 5, 7, 9.) Вы можете подумать, что числа, которые вы генерируете, случайны, но есть какой-то процесс, происходящий в вашем мозгу, чтобы произвести эти числа, которые не являются случайными. Фактически, эксперименты показали, что люди склонны недооценивать присутствие повторяющихся чисел. (Выбирая лотерейные номера, вы бы выбрали выигрышные номера предыдущего дня?)

СТОП:Вспоминая цитату Добржанского о том, что ничто в биологии не имеет смысла, кроме как в свете эволюции из предыдущей главы, какую эволюционную цель могла бы иметь возможность быстро сделать (на первый взгляд) случайное решение?

Если мы мыслим как древние греки, то можем надеяться, что математическая формула нас спасет. Этого же хотел и Джон фон Нейман, пионер вычислительной техники, который в конце 1940-х годов работал над первым компьютером под названием ENIAC (см. рисунок ниже). В то время генерация случайных чисел была настолько примитивной, что самой современной технологией была книга Миллион случайных цифр со 100 000 нормальных отклонений, над которой работала корпорация RAND. Эта книга в конечном итоге содержала 400 страниц миллиона случайных цифр от 0 до 9, сгенерированных вращением электронной рулетки; 20 из 32 полученных чисел были преобразованы в цифры, а остальные 12 были проигнорированы. Если вам нужно было случайное число, вы открывали книгу на какой-то произвольной странице этой книги и начинали переписывать цифры. Излишне говорить, что был остро необходим лучший вычислительный подход для генерации случайных чисел.

Один из методов, предложенный фон Нейманом для генерации случайных чисел, называется подход среднего квадрата. Он начинается с произвольного n-значного целого числа, называемого начальным числом, и генерирует новое "случайное" n-значное целое число, сначала возводя число в квадрат получить 2n-значное число, а затем взять средние nцифры результата. Например, если n = 4 и наше начальное число равно 1600, то 1600² = 2 560 000; это число, представленное как 8-значное число, представлено как 02,560,000, чьи средние четыре цифры равны 5600. Это число становится нашим первым случайно сгенерированным целым числом; чтобы сгенерировать новое случайное целое число, мы возводим в квадрат 5600 и берем его средние четыре цифры.

Числа, генерируемые методом Мидл-Квадрат, могут казаться случайными, но они генерируются детерминированным методом, который всегда дает одну и ту же последовательность чисел из заданного начального начального числа. Поэтому мы будем использовать термин генератор псевдослучайных чисел или сокращенно PRNG для обозначения детерминированного метода, такого как метод среднего квадрата, который генерирует последовательность чисел в попытке имитировать случайность.

СТОП. При начальном значении 1600 мы увидели, что следующим четырехзначным случайным числом, сгенерированным методом среднего квадрата, будет 5600. Какие следующие три числа будут сгенерированы?

Идеальный ГПСЧ в долгосрочной перспективе будет производить каждое n-значное число с одинаковой частотой, независимо от начального числа. Но, как показывает предыдущее упражнение, проблема метода среднего квадрата заключается в том, что он часто генерирует короткие циклы, в которых повторяются одни и те же числа. Учтите, что 8100² = 65,610,000, 6100² = 37,210,000, 2100² = 04,410,000, и 4100² = 16,810,000, поэтому мы можем сгенерировать только четыре числа из начального числа 8100. Хуже того, если мы выберем 3792 в качестве начального числа, тогда 3792² = 14,379 ,264, поэтому мы снова и снова генерируем одно и то же число во имя случайности.

Плохая производительность подхода среднего квадрата, к сожалению, является нормой, когда мы пытаемся использовать функции, основанные на арифметических операциях, для генерации случайных чисел. Как сокрушался сам фон Нейман,

Любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха. Ибо, как уже неоднократно отмечалось, случайного числа не существует.

Генераторы Фибоначчи с запаздыванием

В действительно случайной последовательности чисел мы ожидаем увидеть повторяющиеся числа — это было бы совсем не случайно, если бы ГПСЧ производил последовательность, содержащую четырехзначное число от 0 до 9999 ровно один раз без каких-либо повторений. Однако подход Мидл-Квадрат страдает критическим недостатком: всякий раз, когда встречается число, которое уже было сгенерировано, вся последовательность чисел, следующих за этим числом, будет сгенерирована снова.

Другими словами, в настоящее время мы думаем о ГПСЧ как о создании нового числа y только из одного предшествующего числа x, и это означает, что всякий раз, когда мы встречаем одно и то же x , мы создадим тот же y. Что, если ГПСЧ вместо этого произвел новое целое число из более чем одного предыдущего целого числа? «Запоминание» более чем одного предыдущего числа позволило бы нам генерировать одно и то же число x несколько раз, не обязательно вызывая цикл.

Простой ГПСЧ с большей памятью основан на последовательности Фибоначчи. Первые два члена этой последовательности равны 1, F(0) = F(1) = 1. Последующие члены определяются как сумма двух предыдущих членов; то есть для n ≥2 F(n) = F(n-1) + F(n-2). Конечно, члены этой последовательности продолжаются до бесконечности (1, 1, 2, 3, 5, 8, 13, 21, 34, …), но мы могли бы сформировать PRNG, называемый генератором Фибоначчи если F(n) будет остатком от F(n- 1) + F(n-2) после деления на некоторое фиксированное значение m. Например, если m = 1 000 000, то для F(n-1) = 832 040 и F(n-2) = 346 269, мы установили бы F(n) равным Remainder(832,040 + 346,269, 1,000,000), что, в свою очередь, равно 178 309.

СТОП. Сколько начальных значений нам потребуется для генератора Фибоначчи?

Обратите внимание, что для генератора Фибоначчи потребуется не одно, а два семени. Если мы изменим F(0) и F(1), то это, скорее всего, приведет к изменению F(2), и в результате мы получим другую последовательность целых чисел, сгенерированную PRNG.

СТОП. У вас возникли проблемы с генератором Фибоначчи?

Несмотря на то, что теперь у нас есть PRNG с более длинной памятью, у генератора Фибоначчи есть существенные недостатки, в основном из-за того, что как только мы увидим два целых числа в последовательности, мы сразу же узнаем следующее число в последовательности. Вряд ли случайно!

Мы можем внести небольшую корректировку в генератор Фибоначчи, если попросим его «запомнить» более ранние значения в последовательности случайных целых чисел.

То есть для некоторых фиксированных положительных целых чисел j и k мы устанавливаем F(n) равным остатку суммы F(n-j) + F(n-k), деленное на m. Полученный PRNG называется запаздывающим генератором Фибоначчи, что удивительно практично, учитывая его простоту. Обычно мы избегаем упоминания конкретных языков, но стоит отметить, что встроенный в Go генератор PRNG использует запаздывающий генератор Фибоначчи с j = 273, k = 607 и m = 2³¹. То есть F(n) равно Remainder(F(n-273) + F(n-607), 2³¹).

СТОП. Как вы думаете, сколько начальных значений нам потребуется для генератора Фибоначчи с запаздыванием? Почему?

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

Это обсуждение заставляет нас задаться вопросом, что делает PRNG приемлемым для использования в таких приложениях, как моделирование методом Монте-Карло? Во-первых, мы надеемся, что если мы будем использовать разные начальные числа, то мы получим последовательности чисел, которые отличаются друг от друга. Мы также надеемся избежать повторяющихся последовательностей чисел, подобных тому, что мы видели в подходе среднего квадрата. Федеральное управление информационной безопасности Германии определило четыре «уровня», которые PRNG должны быть достаточно безопасными для использования в приложениях.

Уровень 1.Различные последовательности, сгенерированные ГПСЧ, обычно должны отличаться друг от друга.

Уровень 2.ГПСЧ должен генерировать числа с теми же свойствами, что и последовательность действительно случайных чисел (например, как часто повторяется число или как часто повторяется данная тройка чисел).

Уровень 3. Хакер не должен использовать последовательность чисел для угадывания любых будущих чисел.

Уровень 4. Хакер не должен использовать последовательность чисел, чтобы угадать какие-либо предыдущие числа.

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

Наконец, прежде чем вернуться к нашей работе с моделированием по методу Монте-Карло, отметим, что отчасти причина, по которой мы уделяем особое внимание пониманию основ ГПСЧ, заключается в том, что они все еще актуальны сегодня. История Wired из 2017 года рассказывает захватывающую историю о команде хакеров из Санкт-Петербурга, которые якобы заработали миллионы на игровом автомате определенной марки, используя понимание генератора случайных чисел, чтобы предсказать, когда автомат сделает крупные выплаты.

СТОП.Если мы можем использовать прошлые результаты для расчета времени выплаты в игровом автомате, то какого уровня не достигает PRNG автомата?

Имитация игры в кости

Бросаем один кубик

Напомним, что для оценки выигрыша казино в крэпсе нам нужно имитировать бросок двух игральных костей. Во-первых, мы рассмотрим более простой процесс имитации одного броска игральной кости, который представляет собой равномерную генерацию псевдослучайного числа от 1 до 6.

Языки программирования содержат пакеты или наборы предварительно написанного кода, которые могут использоваться повторно в различных контекстах. В частности, в большинстве языков есть пакет random со встроенным генератором псевдослучайных чисел. (В Go этот пакет, созданный на основе упомянутого ранее ГПСЧ Фибоначчи, называется rand.) Случайный пакет должен, помимо других функций, включать три полезные функции:

RandInt: не принимает входных данных и возвращает псевдослучайное целое число (в диапазоне целых чисел, допустимом для языка и операционной системы).
RandIntn: принимает одно целое число n в качестве входных данных и возвращает псевдослучайное целое число от 0 до n−1.
RandFloat: не принимает входных данных и возвращает псевдослучайное десятичное число с плавающей запятой в интервале [0, 1).

СТОП.Какую из этих функций следует использовать для имитации броска игральной кости?

Студенты обычно хотят использовать RandIntn для имитации броска кубика, но на самом деле мы можем использовать любую из этих трех функций. Например, если мы сгенерируем псевдослучайное десятичное число из [0, 1), то мы можем разделить этот интервал на шесть подинтервалов одинакового размера длиной 1/6 и присвоить кубику значение, исходя из того, в какой подинтервал попадает наше число.

RollDie()
    roll ← RandFloat()
    if roll < 1/6
        return 1
    else if roll < 2/6
        return 2
    else if roll < 3/6
        return 3
    else if roll < 4/6
        return 4
    else if roll < 5/6
        return 5
    else
        return 6

Более короткие функции используютRandIntn для генерации псевдослучайного целого числа от 0 до 5 включительно, а затем добавляют 1 к полученному числу.

RollDie()
    roll ← RandIntn(6)
    return roll + 1

Но мы также можем применить RandInt, сгенерировав произвольное псевдослучайное целое число, а затем взяв его остаток при делении на 6, чтобы получить целое число от 0 до 5 включительно. Как и в предыдущей функции, мы можем затем добавить 1 к полученному целому числу.

RollDie()
    roll ← RandInt()
    return Remainder(roll, 6) + 1

СТОП. Допустим, у нас есть взвешенная кость, которая дает каждое из 1, 3, 4 и 5 с вероятностью 1/10, а также каждое из 2 и 6 с вероятностью 3/10. . Напишите псевдокод для функции RollWeightedDie, которая моделирует эту взвешенную кость.

Теперь вернемся к задаче на сумму двух игральных костей. В таблице ниже показана сумма на двух костях для каждого из 36 = 6² различных результатов броска двух шестигранных костей. Если предположить, что кости правильные, каждый из этих исходов равновероятен.

СТОП. Напишите функцию SumTwoDice, не принимающую входных параметров и возвращающую смоделированную сумму двух шестигранных игральных костей.

Если мы рассуждаем математически, то заметим, что вероятность выпадения x равна количеству способов, которыми можно выбросить x, деленному на общее количество выпавших результаты (36). Таким образом, вероятность выпадения 2 равна 1/36, вероятность выпадения 3 равна 2/36 и так далее. Это рассуждение заставляет нас применить тот же принцип, который мы видели ранее, чтобы разделить интервал [0,1) на подинтервалы. Мы могли бы разделить [0,1) на 36 подинтервалов одинаковой ширины, но наша функция будет короче, если мы разделим [0, 1) на 11 подинтервалов, где ширина интервала равна вероятности того, что сумма двух игральных костей выпадет. быть одним из 11 целых значений от 2 до 12. Эта идея реализована с помощью следующего псевдокода для функции SumTwoDice.

SumTwoDice()
    roll ← RandFloat()
    if roll < 1/36
        return 2
    else if roll < 3/36
        return 3
    else if roll < 6/36
        return 4
    ... (etc.)

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

SumTwoDice()
    return RollDie() + RollDie()

СТОП. Напишите в псевдокоде функцию SumMultipleDice, которая принимает целое числоnumDiceв качестве входных данных и возвращает сумму результатов броска игральной костиnumDice раз.

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

Моделирование президентских выборов

Функции планирования выборов в псевдокоде

Из нашей работы по вычислению преимущества казино в игре в кости мы можем узнать, что естественный способ запуска многих симуляций выборов — это передать тяжелую работу функции, которая симулирует отдельные выборы. Приведенный ниже псевдокод для функции SimulateMultipleElections делает именно это.

На практике разные опросы имеют разную погрешность, отражающую такие переменные, как количество респондентов или историческую достоверность опроса. Однако мы предполагаем, что предел погрешности — это фиксированный параметр с именем marginOfError. Мы будем использовать этот параметр, чтобывключить случайный отскок в наши симуляции. Если этот параметр равен 0,06, то мы примерно на 95% уверены, что наш опрос штата точен в пределах 6% в любом направлении. Например, если процент избирателей кандидата 1 в Калифорнии составляет 64%, то мы на 95% уверены, что истинный процент избирателей, поддерживающих кандидата 1, составляет от 58% до 70%.

Мы также пока не будем указывать, как будут представлены данные опроса; на данный момент мы просто назовем эти данные pollingData, параметр, который мы передадим вместе с marginOfError в подпрограмму SimulateOneElection, которая каждый раз возвращает количество голосов Коллегии выборщиков. кандидат получает в ходе одних смоделированных выборов.

Теперь мы представим SimulateMultipleElections, который вызывает SimulateOneElection numTrials раз, отслеживая количество побед, накопленных каждым кандидатом (а также количество испытаний). Затем он делит каждое количество побед на общее количество испытаний, чтобы получить расчетные «вероятности» победы каждого кандидата, а также расчетную вероятность ничьей.

SimulateMultipleElections(pollingData, numTrials, marginOfError)
    winCount1 ← 0
    winCount2 ← 0
    tieCount ← 0
    for numTrials total trials
        votes1,votes2 ← SimulateElection(pollingData, marginOfError)
        if votes1 > votes2
            winCount1 ← winCount1 + 1
        else if collegeVotes2 > collegeVotes1
            winCount2 ← winCount2 + 1
        else (tie!)
            tieCount ← tieCount + 1
    probability1 ← winCount1/numTrials
    probability2 ← winCount2/numTrials
    probabilityTie ← tieCount/numTrials
    return probability1, probability2, probabilityTie

Естественный способ представления pollingData — две карты. Карта electoralVotes связывает ключи имени штата с (положительным) целым числом, хранящим количество голосов для этого штата. Карта опросов связывает ключи названий штатов с процентом, с которым кандидат 1 опрашивает в этом штате. См. рисунок ниже.

Чтобы имитировать отдельные выборы, нам нужно использовать эти данные опроса вместе с marginOfError, чтобы получить случайно скорректированный процент опроса для каждого штата. Если этот скорректированный процент больше или равен 50%, то мы предполагаем, что кандидат 1 побеждает в штате (ничья будет крайне маловероятной). Мы скоро вернемся, чтобы обсудить детали этой корректировки; сейчас мы назовем подпрограмму, которая достигает этой цели, AddNoise. Функция SimulateOneElection может возвращать информацию о том, кто из кандидатов победит (или если была ничья), но мы будем использовать эту функцию для возврата количества голосов выборщиков, которое каждый кандидат набирает на смоделированных выборах.

SimulateOneElection(polls, electoralVotes, marginOfError)
    votes1 ← 0
    votes2 ← 0
    for every key state in polls
        poll ← candidate 1's polling percentage
        adjustedPoll ← AddNoise(poll, marginOfError)
        if adjustedPoll ≥ 0.5 (candidate 1 wins state)
            votes1 ← votes2 + electoralVotes[state]
        else (candidate 2 wins state)
            votes2 ← votes2 + electoralVotes[state]
    return votes1, votes2

Как и в нашей работе с крэпсом, мы видим, что рандомизация скрывается внутри подпрограммы, которой в данном случае является функция AddNoise.

СТОП.Как написать AddNoise? Какая случайная функция была бы полезна?

В отличие от нашей предыдущей работы, использование RandInt или RandIntn неестественно, потому что нам нужно сгенерировать случайное десятичное число x, которое мы будем добавлять к кандидатам 1. процент опроса. Одна из идей состоит в том, чтобы сгенерировать значение шума между -marginOfError и marginOfError, сначала сгенерировав псевдослучайное десятичное число от -1 до 1, а затем умножив полученное значение на marginOfError. .

STOP:у нас есть встроенная функция RandFloat, которая возвращает псевдослучайное десятичное число от 0 до 1. Как мы можем использовать эту функцию для получения псевдослучайного десятичного числа между -1 и 1?

Как только мы сгенерируем случайное десятичное число от 0 до 1, мы можем умножить его на 2, а затем вычесть 1 из результата, чтобы получить случайное десятичное число от -1 до 1. Умножение этого числа на marginOfError выдает желаемый x.

AddNoise(poll, marginOfError)
    x ← RandFloat()
    x ← 2 * x (now x is between 0 and 2)
    x ← x – 1 (now x is between -1 and 1)
    x ← x * marginOfError (now it’s in range 😊)
    return x + poll

Однако эта функция AddNoise страдает недостатком, поскольку возвращаемое ею число будет равномерным, а это означает, что вероятность того, что переменная шума окажется в «хвостах» диапазона возможных значений, с такой же вероятностью, как и у в центре. Это также не позволит получить желаемые 5% крайних случаев, когда значение шума выходит за пределы диапазона между -marginOfError и marginOfError.

На практике вероятность генерации заданного значения шума должна быть взвешена так, чтобы значения, близкие к 0, были более вероятными, чем значения в хвостах. Один из способов добиться этого — использовать стандартную нормальную функцию плотности, кривую в форме колокола, знакомую всем, кто прошел курс статистики (см. рисунок ниже). Вероятность образования числа между числами a и b равна площади под функцией между значениями x числа a и b; то есть интеграл стандартной нормальной функции плотности. Поскольку функция плотности выше нуля, вероятность получения числа, близкого к нулю, выше, и эта вероятность уменьшается по мере удаления от нуля. Существует примерно 68,3% вероятность генерации числа от -1 до 1 и 95,4% вероятность генерации числа от -2 до 2.

СТОП: как выглядит функция плотности, если мы равномерно генерируем десятичные числа от 0 до 1?

Таким образом, мы можем получить случайное значение шума в диапазоне от -marginOfError до marginOfError примерно с вероятностью 95 %, сгенерировав псевдослучайное десятичное число в соответствии со стандартной функцией нормальной плотности, а затем умножив это число на marginOfError/2. Но как мы можем получить эти числа?

Помните наш классический учебник по вычислению случайных чисел в докомпьютерную эру Миллион случайных цифр со 100 000 нормальных отклонений? Книга получила вторую половину своего названия, потому что она содержит 100 000 случайных чисел, отобранных под стандартной функцией нормальной плотности. К счастью, нам не нужно обращаться к книге 70-летней давности, потому что языки программирования будут включать функцию RandNormal, которая возвращает случайное число в соответствии со стандартной функцией нормальной плотности, что позволит нам обновить нашу реализацию AddNoise следующим образом.

AddNoise(poll, marginOfError)
    x ← RandNormal()
    x ← x/2 (95% chance of x being between -1 and 1)
    x ← x * marginOfError (now x is in range)
    return x + poll

И вот так, мы закончили! Обратите внимание, как мы сохранили самую сложную часть нашей работы, включая случайность в данные опроса, напоследок? Подробнее об этом мы поговорим в следующей главе.

Реализация нашей работы

В видео ниже мы используем Go для реализации симулятора игры в кости и алгоритма прогнозирования выборов, о которых мы говорили выше. Затем мы применяем этот алгоритм прогнозирования к реальным данным опросов о выборах в США в 2016 году. Что мы найдем?

Если вы хотите увидеть результаты этого прогноза, не применяя его самостоятельно, не стесняйтесь переходить к следующему разделу.

Заключение: размышления о природе прогнозирования выборов

Улучшение нашего алгоритма прогнозирования выборов

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

Говоря более прямо, мы должны спросить: «Хорош ли наш подход к прогнозированию?» Однако мы не можем не заметить, что наш прогноз более уверен в победе Клинтон, чем и New York Times, и FiveThirtyEight. Чем вызвано это несоответствие?

В конце концов, погрешность в 10%, используемая для составления приведенной выше таблицы, намного шире, чем погрешность большинства опросов. Это означает, что даже если кандидат набирает 60% голосов в штате, что является настоящим оползнем, вероятность того, что наш прогноз присудит этот штат кандидату-противнику, превышает 2%. Итак, если наш прогноз в этом отношении более консервативен, чем профессиональные прогнозы, почему он больше склоняется в пользу Клинтон? Что СМИ добавили к своим прогнозам, чего нам не хватает?

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

Во-вторых, из-за небольших размеров выборки, используемой в опросах, по сравнению с населением, прогнозисты обычно использовали колоколообразную кривую, которая «короче» около 0 и имеет «более толстые» хвосты при добавлении шума к значению опроса. Случайная выборка из функции плотности с толстыми хвостами позволяет с большей вероятностью получить скорректированное значение опроса дальше от его текущего значения в AddNoise.

Наконец, при моделировании выборов мы до сих пор рассматривали штаты как независимые. На практике состояния сильно коррелированы; например, очень велика вероятность того, что Северная Дакота и Южная Дакота проголосуют одинаково. Соответственно, если в одной симуляции AddNoise корректирует данный опрос состояния в пользу одного кандидата, то, скорее всего, нам следует корректировать опросы любых коррелированных состояний также в пользу этого кандидата.

Корреляция результатов штатов повышает вероятность победы аутсайдера — в 2016 году Трамп победил в большинстве штатов «ржавого пояса», простирающихся от западного Нью-Йорка через район Великих озер до Висконсина, хотя опросы показали, что у него относительно небольшие шансы на победу в каждом из этих состояний.

Прогнозирование выборов безнадежно?

Мы могли бы легко добавить эти функции, чтобы улучшить наш собственный алгоритм прогнозирования. Однако будет более плодотворно, если мы потратим время на то, чтобы не продолжать кодирование, а вместо этого задуматься о внутренних недостатках прогнозирования любых выборов на основе данных опросов.

Скрытое предположение нашей работы до сих пор заключается в том, что ответы на опрос адекватно отражают решение, которое респонденты примут в уединении избирательной урны. Один из способов возникновения такой асимметрии — если сторонники одного кандидата имеют более высокую явку избирателей. Один общенациональный опрос, Los Angeles TimesDaybreak Poll, был взвешен на основе того, насколько восторженно избиратель относился к соответствующему кандидату. То есть респондент мог указать 60% поддержки Трампа или 80% поддержки Клинтон, а не бинарный ответ. Опрос на рассвете, показанный на рисунке ниже, в 2016 году неизменно отдавал предпочтение Трампу.

СТОП. Является ли тот факт, что опрос Daybreak Poll предсказывает правильного победителя, хорошим опросом?

Тот факт, что прогноз верен, не делает его хорошо разработанным прогнозом. Например, предположим, что ваш местный метеоролог может предсказать дождь на завтра, а ваш сосед предсказывает солнечный свет, основываясь на результате подбрасывания монеты. Если солнечно, вы вряд ли назовете своего соседа экспертом. Самый большой недостаток Daybreak Poll заключается в том, что это общенациональный опрос, несмотря на то, что выборы решаются в каждом штате. На самом деле Клинтон выиграла общенациональное «народное голосование», набрав около трех миллионов бюллетеней, так что в этом смысле опрос на рассвете был столь же неверным, как и прогнозы других СМИ, хотя взвешивание опросов по энтузиазму — интересная идея.

Мы продолжаем аналогию с погодой, прося вас рассмотреть следующий вопрос.

СТОП. Если метеоролог скажет вам, что вероятность дождя в определенный день через три месяца составляет 70 %, поверите ли вы ему?

Мы бы никогда не стали доверять прогнозу погоды на три месяца вперед, но мы, вероятно, могли бы доверять знанию, во сколько взойдет солнце на три месяца вперед. Понимание изъяна во всех симуляциях выборов требует от нас понимания того, чем отличаются эти два примера, и отвлечет нас к фондовому рынку.

На рисунке ниже показаны цены двух акций (называемых «акции А» и «акции Б») за пятилетний период с января 2012 года по январь 2017 года. Представьте, что сейчас январь 2017 года, и мы играем в бинарную игру. Вы ставите 1 доллар и выбираете одну из двух акций. Если за шесть месяцев цена вашей акции увеличилась на 30%, вы выиграете 5 долларов; в противном случае вы потеряете свой доллар. Какую из двух акций вы бы выбрали?

Многие студенты выбирают акции А для своей ставки, потому что они показали лучшие результаты за предыдущие пять лет. Тем не менее, вы с большей вероятностью выиграете свою ставку, если выберете акцию Б, потому что ее цена намного изменчива, чем акция А. На самом деле, в июле 2017 года, через шесть месяцев после того, как была сделана ставка, акции А (Colgate-Palmolive) торговалась по цене около 73 долларов за акцию, что является незначительным приростом по сравнению с ее ценой в январе 2017 года, тогда как акции B (First Solar) взлетели примерно до 45 долларов (см. рисунок ниже). В этом случае вы бы выиграли свою ставку, хотя цена акций могла так же легко упасть, что и произошло в середине 2018 года.

Если вы подумаете о нашей бинарной игре, в которой мы делаем ставку на то, что акции вырастут на 30% за шесть месяцев, то за последние пять лет не будет ни одного момента времени, когда вы бы выиграли эту ставку на Colgate-Palmolive. Иначе обстоит дело с First Solar, где мы находим периоды в середине 2016 года, в начале-середине 2017 года и снова в конце 2018 и начале 2019 года, когда эта ставка была бы выигрышной.

Эти типы ставок могут показаться надуманными, но они являются примером дериватива или инвестиции, цена которой привязана к цене некоторого базового актива. Наша ставка на то, что акции вырастут до определенной суммы K к моменту времени T, является упрощенной формой европейского колл-опциона; если цена акции x в момент времени T, то выплата по опциону равна либо $0, если цена акции меньше K в момент времени T или x-K, если цена x больше или равна K . И ключевым моментом является то, что акции с более высокой волатильностью будут иметь более дорогие колл-опционы, когда K намного выше, чем текущая цена акции.

Мы можем быть уверены в том, когда через три месяца взойдет солнце, потому что, за исключением армагеддона, время восхода имеет очень низкую изменчивость. Напротив, погода очень изменчива, что делает прогнозирование на ближайшие несколько дней очень трудным и невозможным на несколько месяцев вперед.

А как насчет прогнозирования выборов? Мы воспроизводим прогнозы FiveThirtyEight и New York Times ниже. Обратите внимание, как резко меняются прогнозы; в наиболее примечательном случае прогноз FiveThirtyEight в начале августа, который был 50/50, вернулся к прогнозу 80% для Клинтон всего за несколько дней. Эти колебания в прогнозах отражают очень нестабильные опросы, на которые влияют новостные события, а также запланированные события во время кампаний, такие как партийные съезды и дебаты.

Эти средства массовой информации построили красивую визуализацию данных поверх забавного метода прогнозирования выборов, который начинающий программист может реализовать с небольшой помощью. Но они также совершили критическую ошибку, предсказав событие далекого будущего на основе изменчивых данных, при этом иногда продавая свою работу как оценку «вероятности» победы. Гораздо лучшим прогнозом выборов летом 2016 года было бы пожать плечами и заявить, что предсказание любого будущего события в условиях высокой волатильности ничем не отличается от азартной игры.

Спасибо, что прочитали! Если вам нравится это сумасшествие, ознакомьтесь с моим текущим курсом: https://canvas.instructure.com/enroll/RKFKKP