|
Содержание
Предисловие
Настоящее (расширенное и дополненное) справочное пособие посвящено изложению накопленных к настоящему времени результатов (включая и последние результаты авторов) по анализу дискретных вероятностных моделей. Ранее, в издательстве URSS уже выходили две наши книги, посвященные этой теме: «Одномерные распределения» (2015) и «Многомерные распределения» (2016). Незатухающий интерес к дискретным моделям привел к появлению в математической литературе последнего времени большого числа новых публикаций в этой области, существенно дополняющих и развивающих в самых различных направлениях предыдущие достижения, поэтому их систематизация и единообразное изложение в одной книге представляется нам актуальным и полезным для их практического использования. Отметим здесь общую тенденцию, характерную для последнего времени и связанную со стремлением построения новых, более общих и более адекватных требованиям современной практики дискретных математических моделей. Комбинаторный и вероятностно-статистический анализ этих моделей и порождает вал новых результатов, продвигающих как общую теорию дискретных моделей, так и расширяющих сферу их применений. В качестве характерного примера приведем проблему исследования таких важных для криптографических приложений комбинаторных объектов, каковыми являются подстановки и разбиения конечных множеств. Традиционным до недавнего времени методом исследования различных комбинаторных объектов было введение на множестве рассматриваемых объектов равновероятной меры и последующий анализ различных характеристик этих объектов как случайных величин. Такой вероятностный подход оказался весьма эффективным при решении широкого круга комбинаторных перечислительных задач, когда интересуются подсчетом числа объектов — подмножеств некоторого множества, обладающих теми или иными заданными свойствами. Вместе с тем, в современных приложениях возникают задачи и других типов, для решения которых равномерная модель уже не является адекватной, а именно, когда требуется учитывать различного рода возможные отклонения от равновероятности, и исследовать поведение изучаемых характеристик при альтернативных (по отношению к равномерной) мерах. Общая параметрическая модель для произвольного множества разложимых комбинаторных объектов была предложена в наших работах (2003, 2004, 2007), а ее конкретизация для случайных подстановок и разбиений конечных множеств изложена в работах (2006, 2011, 2017). Достоинством этой модели является наличие в ней большого числа «свободных» параметров (степеней свободы), варьируя которые можно конструировать различные альтернативные распределения на множестве изучаемых объектов. Тем самым, имеется возможность проводить более глубокий вероятностно-статистический анализ (проверка различных статистических гипотез) таких моделей. В то же время и классические конструкции комбинаторных объектов зачастую оказываются уже недостаточными в качестве адекватных моделей для приложений — требуется вводить различного рода усложнения или ограничения на множествах рассматриваемых объектов. Например, в соответствующих задачах требуется рассматривать лишь подстановки без коротких и/или длинных циклов, а также изучать такие разбиения конечного множества, которые не содержат блоков малого и/или большого объема. Так возникают новые конструкции комбинаторных объектов и новые задачи их анализа, которые, в основном, и составили содержание дополнений в настоящей монографии. В книге уделено также внимание моделям, возникающим при анализе случайных комбинаторных объектов, в частности, многочленам над конечными полями и различным функционалам, связанным со схемами размещения частиц. Следует при этом отметить, что при анализе многомерных моделей естественно возникают специфические распределения и различных одномерных характеристик, отражающих существенные особенности модели. Так что в данной книге имеется большое число и новых одномерных распределений, дополняющих их список, приведенный в нашей первой книге (2015). Помимо этого, в книгу включен новый материал (Часть III), посвященный трем знаменитым числовым последовательностям: биномиальным коэффициентам и числам Стирлинга первого и второго рода. Включение этого материала мотивировано той исключительной ролью, которую играют эти числа при решении различных задач комбинаторики, криптографии, математического анализа, теории вероятностей и других разделов математики. Литература, посвященная как исследованию разнообразных и интересных аналитических свойств этих чисел, так и их многообразных применений и обобщений, буквально необъятна, и поток новых публикаций по этой тематике не иссякает. Обзор и систематизация накопленных здесь результатов, представляющих собой необходимый математический инструментарий исследования новых математических моделей, является, на наш взгляд, несомненно, актуальным. В книгу также включены глава «Булевы функции» и два дополнения. При подготовке этого издания мы не могли пройти мимо такого важнейшего, на наш взгляд, современного направления в дискретных вероятностных моделях, как случайные булевы функции и их спектральный анализ. В настоящее время наблюдается бурное развитие таких отраслей математики, как теории конечных функциональных систем, теории информации, теории кодирования и криптографии, в которых рассматриваются проблемы анализа и синтеза дискретных устройств, осуществляющих обработку и преобразование различного рода информации. Булевы функции (более обще — дискретные функции) и являются основным аналитическим аппаратом решения подобных проблем. По этой причине они представляют собой популярный объект математического и криптографического анализа. В книге мы акцентируем наше внимание на важнейшем объекте модели булевой функции — ее спектре Фурье: многие криптографические свойства булевой функции выражаются именно в терминах ее спектральных характеристик. В последние годы для исследования спектра булевой функции весьма эффективно применяется вероятностный подход, когда на множестве рассматриваемых функций вводится та или иная вероятностная мера, приписывающая каждой функции этого множества соответствующий вес (например, равномерная мера, приписывающая каждой функции этого множества одинаковый вес). В этом случае спектр случайно выбранной функции становится случайным вектором, и для исследования различных его особенностей «в среднем» успешно применяются методы теории вероятностей, и в особенности ее предельные теоремы, позволяющие устанавливать полезные асимптотические оценки для различных характеристик спектра. Обзор полученных в последнее время в этом направлении результатов и составляет содержание данной главы. В Дополнении I приводится сборник общих предельных теорем, составляющих инструментарий исследования асимптотических свойств последовательностей неотрицательных действительных чисел и неотрицательных целочисленных случайных величин. Дополнение II посвящено изложению методологии исследования дискретных случайных величин с конечным носителем, основанной на свойствах корней их производящих функций и приводящей к разложению таких величин на простейшие независимые слагаемые. В данную книгу включены модели, которые наиболее часто встречаются в самых разнообразных задачах теории вероятностей, математической статистики и комбинаторного анализа, и значение которых трудно переоценить. Отметим также, что дискретные модели (как правило, многомерные) используются и в различных задачах экономической, финансовой деятельности, в теории исследования операций, социологии и особенно в современных задачах теории защиты информации, теории кодирования и криптографии. При работе над книгой мы использовали как оригинальные публикации, так и различную монографическую и учебную литературу по теории вероятностей, математической статистике и комбинаторике, а также (в некоторых аспектах) аналогичные зарубежные издания: весьма полезный и обширный справочник Johnson, Kotz & Balakrishnan (1996) и др. В отличие от последних изданий, акцент делается нами собственно на изложении результатов (что и представляет, по нашему мнению, главный интерес для пользователей), без детального обсуждения (в большинстве случаев) их генезиса и первоисточников. Далее, наряду с вероятностными аспектами, мы детально освещаем и соответствующие вопросы статистического вывода (оценивание неизвестных параметров распределений и проверка соответствующих статистических гипотез), а также вопросы моделирования и асимптотического анализа, включая важные для приложений темы оценок типа неравенств и больших уклонений. Наконец, мы доводим повествование до наших дней и при этом стремимся, как можно более полно отразить существенный вклад отечественных авторов в развитие этой тематики, чему, к сожалению, не уделяется должного внимания в аналогичных зарубежных изданиях. В то же время, за пределами данного пособия остался ряд важных объектов дискретной математики, так как они уже достаточно детально отражены в соответствующих монографиях и обзорных работах (тем не менее, в приводимой нами библиографии соответствующие публикации отражены). Это: — общие случайные отображения и случайные графы (Колчин В. Ф., Павлов Ю. Л., Степанов В.Е. и др.); — случайные матрицы и системы случайных уравнений над конечными полями и кольцами (Балакин Г. В., Горшков С. П., Коваленко И. Н., Колчин В. Ф., Копытцев В. А., Левитская А. А., Михайлов В. Г., Сачков В. Н., Тараканов В. Е. и др.); — вероятностные модели конечных автоматов (Горчинский Ю. Н., Зубков А. М., Иванов В. А., Максимов Ю.И., Михайлов В. Г. и др.); — распределения на конечных группах (Алиев Ф. К., Горчинский Ю. Н., Капитонов В. М., Круглов И. А., Лапшин А. В., Шерстнев В. И. и др.). Приводимая в конце книги достаточно обширная (но отнюдь не претендующая на исчерпывающую полноту) библиография по дискретной тематике, в основном отражающая (в той или иной степени) вклад в нее российских математиков, является, по нашему мнению, самоценной и будет полезной для пользователей. Преподаватели, студенты, научные работники и инженеры, использующие в своей практической работе вероятностные и статистические методы, постоянно сталкиваются с потребностью в соответствующем кратком сборнике ответов на часто возникающие вопросы (как говорит арабская пословица, знание ответов — великое преимущество). Данное пособие и имеет целью удовлетворить потребность в быстром получении соответствующей информации, которая обычно разбросана по многочисленным и часто трудно доступным источникам. Мы будем признательны читателям за замечания и предложения, направленные на улучшение изложения материала и пополнение его содержания для последующих изданий книги. Мы признательны рецензентам книги и другим коллегам по Академии криптографии за полезные обсуждения, замечания и моральную поддержку при подготовке этой книги. Особую благодарность мы выражаем Шляпниковой Светлане Игоревне за неоценимую помощь в поиске и подборе научной литературы по тематике книги, разбросанной по необъятным просторам Интернета в виде монографий, журналов и различных пособий. В заключение отметим следующее. Математических справочников (как общего характера, так и относящихся к отдельным разделам математики) издано огромное количество, все они об одном и том же о математике, но различаются как по подбору материала, так и по полноте и стилю его изложения, что, в определенной мере, отражает, естественно, и пристрастия их авторов. Это в полной мере относится и к данному пособию. Мы, возможно, уделили больше внимания собственным результатам, но стремились быть объективными и в отражении достижений наших коллег, предшественников, а также зарубежных авторов. И, как говорил Б. Паскаль , «Пусть не корят меня, что я не сказал ничего нового: ново уже само расположение материала; игроки в мяч бьют по одному и тому же мячу, но не с одинаковой меткостью». Октябрь 2018 Авторы
Об авторах
 Ивченко Григорий Иванович Доктор физико-математических наук, профессор. Специалист в области теории вероятностей, математической статистики, дискретной математики и их приложений. Действительный член Академии криптографии РФ. С 2016 г. — главный научный сотрудник. Автор более 200 научных работ, в том числе свыше 10 учебников и учебных пособий по специальности «прикладная математика» для вузов. Имеет правительственные награды.
 Медведев Юрий Иванович Доктор физико-математических наук, профессор. Специалист в области теории вероятностей, математической статистики, дискретной математики и их приложений. Действительный член Академии криптографии РФ (с 1998 г. — член президиума). Лауреат Государственной премии СССР (1975), заслуженный деятель науки РФ. Автор более 200 научных работ, в том числе свыше 10 учебников, учебных пособий и монографий по специальности «прикладная математика». Имеет государственные награды.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||