Рандомизация в математике и в жизни

Рандомизация (от английского random — случайный) означает сознательное внесение случайного элемента в какой-то процесс. Когда-то люди, решавшие, как им быть, подбрасыванием монеты или вытаскиванием спичек, почитались за несерьезных. Но теперь пора заняться их реабилитацией: строго доказано, что многие важные задачи требуют для решения бросать жребий. Отвлечемся пока от спортивных страстей далекого прошлого и послушаем ученых.

Теория игр

В 1921 году французский математик Эмиль Борель опубликовал статью, которая в то время никого не заинтересовала. Даже Иоганна фон Неймана, в будущем знаменитого, а тогда еще безвестного немецкого юношу, который пятью годами позже выступил на ту же тему перед собранием Геттингенского математического общества. А в 1943 году тот же фон Нейман, ставший к тому времени из Иоганна Джоном, вместе с другим американским ученым, О. Моргенштерном, опубликовал книгу «Теория игр и экономическое поведение». Один пример из неё стоит того, чтобы его привести здесь. Он относится к столкновению между Шерлоком Холмсом и профессором Мориарти.

Напомним, что Шерлоку Холмсу пришлось бежать из Лондона от своего неумолимого врага в Дувр и дальше во Францию. Но успех бегства с самого начала оказался под вопросом: отъезжая, на перроне в Лондоне Холмс увидел Мориарти, и ему стало ясно, что неизбежна погоня на специальном поезде. У Холмса были две возможности: ехать все же до Дувра или высадиться в Кентенберри, единственном промежуточном пункте, где поезд делал остановку. Те же две возможности были и у его преследователя. Какое решение должны принять оба участника конфликта?

Прежде всего, нужна какая-то количественная мера происходящего, которую Нейман и Моргенштерн предлагают установить, так. Если Холмс высадится в Кентенберри и Мориарти тоже, то это будет для Мориарти стопроцентная удача, как и случай, если оба попадут в Дувр. Если Холмс прибудет в Кентенберри, а Мориарти в Дувр, то это будет ничья (то есть выигрыш Мориарти составит 0 процентов), ибо и цель Холмса — попасть во Францию — не будет достигнута. Наконец, если Мориарти высадится в Кентенберри, а Холмс доедет до Дувра и ускользнет, то преступник будет посрамлен, что авторы оценили в половину стоимости жизни Холмса (стоимости для Мориарти), то есть в виде выигрыша в 50 процентов. Примем указанные числа как непреложные и зададимся вопросом: как должен поступать мудрый, но, увы, не всесильный Холмс, чтобы его шансы остаться в живых были максимальными? И как действовать Мориарти, чтобы добиться успеха?

По Нейману и Моргенштерну, решение задачи таково: обоим участникам конфликта следует рандомизировать свое поведение. Мориарти должен с вероятностью 3/5 оказаться в Дувре, а с вероятностью 2/5 в Кентенберри. Холмс, наоборот, с вероятностью 3/5 в Кентенберри и 2/5— в Дувре. Но как практически реализовать эту рекомендацию?

Понятно, что если бы погоня происходила 100 раз, то Холмсу надо было высаживаться в Кентенберри 60 раз, но так, чтобы Мориарти каждый раз был в неведении относительно его планов. Однако даже великие сыщики располагают только одной жизнью. И как действовать Мориарти, чтобы реализовать свои шансы? К примеру, вот как. Он может взять круглую палочку и выстругать на ней пять одинаковых граней (вряд ли злодей выходит из дому без ножа). Три из граней Мориарти должен пометить крестиками и бросить палочку на перрон. Если палочка упадет на помеченную грань, то Морирати должен ехать до Дувра, а если на чистую — до Кентенберри. В свою очередь Холмс должен пометить только две грани, а в остальном поступать так же.

Счастливая замена одного наилучшего решения многими, которые следует применять с оптимальными частотами,— это, на наш взгляд, одно из главных достижений математики в наше время. И самое поразительное, если одна из сторон уклонится от такого образа действий, то она даст противнику дополнительные шансы на успех. Это сумели показать Борель и другие, и тут сильная сторона их подхода. А слабые стороны? Они есть? К сожалению, да.

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

Теория игр развивалась интенсивно. Она умеет уже описывать случаи, когда участников конфликта не два, а сколько угодно. Даже когда их бесконечно много. Более того, участники конфликта могут вступать, в коалиции друг с другом так, чтобы их интересы в чем-то совпадали. Но всегда остается справедливым такой вывод: если игра не содержит никакой неопределенности, если это игра «с полной информацией», то наилучшее решение в каждой ситуации строго определенной не нуждается в рандомизации. И наоборот, если в игре есть элемент неопределенности (к примеру, вносимый противником), то наилучшее решение носит в общем случае случайный, рандомизированный характер.

Мы обсудили вслед за Нейманом и Моргенштерном случай, когда выбор носил дискретный характер — Кентенберри или Дувр. Но ничто не мешает теперь включить в рассмотрение любой ярд дороги Лондон — Дувр. Если Холмс легко гнул железную кочергу, то и прыжок с поезда был ему, вероятно, по плечам (или по ногам). Но тогда этот шанс пришлось бы оставить и за коварным Мориарти. В таком случае мы получаем задачу не дискретных, а «дифференциальных игр». Этот термин ввел американский ученый Р. Айзеке, причем основное внимание он уделил именно задачам преследования. Кто только за кем ни гоняется в книге Р. Айзекса «Дифференциальные игры»!

Шофер за пешеходом, катер за кораблем, футбольный защитник за нападающим, снаряды за самолетами и даже… чудовище за принцессой! Любопытна формулировка последней задачи. Чудовище ищет принцессу в абсолютно темном помещении. Поимка происходит тогда, когда расстояние между ними станет меньше заданного. Известна максимальная скорость чудовища, а скорость принцессы может быть любой. Какими должны быть стратегии бедняжки и ее мучителя? Р. Айзеке признается, что решение задачи ему неизвестно, но он полагает, что оно должно быть рандомизированным. Действительно, для принцессы обе крайности — стоять на месте или двигаться с огромной скоростью — явно не сулят ничего хорошего. Несмотря на леденящие душу условия задачи, судьба несчастной пока не подвинула ни одного ученого на ее решение.

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

Случайный поиск

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

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

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

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

«Но позвольте,— возразят тут многие читатели,— ведь здесь речь идет не о хитроумном Мориарти, а всего лишь об электродвигателе, который вряд ли враждебен нам и отнюдь не старается помешать выявлению своих оптимальных параметров». И действительно, оптимизация электродвигателя — это вовсе не конфликтная ситуация с неполной информацией. Однако выясняется, что электродвигатель удобно наделить свойствами мыслящего противника, чтобы построить эффективный (хотя и не оптимальный) алгоритм поиска оптимальных параметров. Впрочем, на этот счет еще ведутся споры.

Планирование экспериментов

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

Только рандомизация способна обеспечить объективность эксперимента. К сожалению, известно немало случаев, когда экспериментатор был уверен в своей объективности и не замечал, что вносит в подготовку эксперимента условия, искажающие его результат.

Классический пример такой ошибки — предсказание результатов выборов президента США в 1936 году, когда им стал Ф. Д. Рузвельт. Экспериментатор опрашивал избирателей по телефону и не учел, что в то время владельцы телефонов отражали мнение лишь наиболее обеспеченных граждан. Большинство владельцев телефонов действительно голосовало против Рузвельта, в то время как большинство всего населения — за него. Правильный эксперимент заключался бы в случайном выборе кандидатур для опроса из полного списка избирателей.

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

Статистическое моделирование

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

В математическую модель станции посылаются случайные «звонки» и находится ее реакция. Статистическая модель станции — это всего лишь программа для компьютера, стоит она неизмеримо меньше настоящей станции — семиэтажного здания, набитого всяческим оборудованием. И, тем не менее, такая модель способна дать ответ на вопрос, что ждет клиента, которому срочно понадобится скорая помощь или участливая трепотня приятеля. Соединится ли он с интересующим его объектом за минуту? А за две? И ответы эти можно получить не за год эксплуатации станции, а всего лишь за несколько минут: ведь компьютер позволяет сжимать время. Набор номера, который даже натренированная рука проводит за двадцать секунд, компьютер генерирует за десятитысячную долю секунды.

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

Счастливый случай

Обращение к случаю стало счастливой находкой для многих исследователей. Эпидемия рандомизации охватывает все новые разделы техники, экономики,- социологии. Ученых привлекает почти ничем не ограниченная свобода творчества, отсутствие строгих канонов, порой стесняющих воображение в иных подходах. Иногда, благодаря этой свободе, дело доходит до более или менее полного абсурда. К примеру, один австралийский исследователь предложил случайным образом вводить армирование в железобетонных конструкциях. Дескать, все равно нам не известны в точности законы, связывающие прочность с армированием, как неизвестен и критерий качества железобетонной конструкции. Его коллега, едко возражая против этого подхода, заметил, что логическим развитием такого метода должна быть рандомизация в медицине: поскольку неизвестны причины многих болезней, а диагнозы далеко не всегда точны, то можно рекомендовать врачу после осмотра больного случайным образом брать лекарство с полки.

Но даже если закрыть глаза на крайности, которыми богата современная жизнь науки, то следует признать, что не все ученые разделяют идеи рандомизации в теории решений. Многие заявляют, что лучше уж вкладывать в математические модели самые несовершенные, но зато детерминированные механизмы, чем полагаться на волю слепого (или пусть даже только подслеповатого случая). Это сродни спорам, которые велись в двадцатые годы прошлого века относительно статистических методов в физике. Тогда А. Эйнштейн заявлял, что он не верит, будто Бог, прежде чем назначить положение электрона, бросает кости. Тем меньше оснований, заявляют современные противники рандомизации, заниматься этим малодостойным делом человеку. Человек должен стараться постигнуть законы бытия, устранить белые пятна, а не прятаться от них в скорлупу рандомизации.

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

Автор: М. Высотский.