Обложка Колчин В.Ф. Случайные отображения
Id: 260582
677 руб.

Случайные отображения. Изд. 2

URSS. 2020. 208 с. ISBN 978-5-9710-7500-4.
  • Твердый переплет

Аннотация

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

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

Для специалистов в области теории вероятностей и ее приложений, инженеров и студентов старших курсов вузов.


Оглавление
Предисловие к первому изданию............... 5
Глава I. Обобщенная схема размещения частиц и случайные тображения.................. 9
§ 1. Вероятностный подход к перечислительным задачам комбинаторики ................ 9
§ 2. Обобщенная схема размещения и полиномиальное аспределение.................. 13
§ 3. Примеры сведения комбинаторных задач к обобщенной схеме размещения.............. 18
§ 4. О локальных предельных теоремах........ 21
§ 5. Кратности вершин случайного отображения .... 25
§ 6. Связность графов и обобщенная схема размещения ....................... 32
§ 7. Обобщенная схема размещения и случайные подстановки ....................... 41
§ 8. Свойства распределения логарифмического ряда. . . 43
§ 9. Циклы случайной подстановки .......... 52
§ 10. Линейные комбинации длин циклов........ 57
§ 11. Порядок случайной подстановки ......... 65
§ 12. Компоненты случайного отображения и обобщенная хема размещения................ 79
§ 13. Вариационный ряд компонент случайного отображения ...................... 86
§ 14. Дополнения и литературные ссылки........ 95
Глава II. Ветвящиеся процессы и случайные деревья . . . 102
§ 1. Ветвящиеся процессы............... 102
§ 2. Связь ветвящихся процессов и случайных деревьев 112
§ 3. Предельные теоремы для условных распределений ритического ветвящегося процесса ........ 113
§ 4. Условное распределение момента вырождения критического ветвящегося процесса........... 125
§ 5. Предельные распределения характеристик случай- ого дерева.................... 140
§ 6. Дополнения и литературные ссылки........ 148
Глава III. Случайные леса и отображения........ 152
§ 1. Связь лесов и отображений ............ 152
§ 2. Объемы деревьев в случайном отображении..... 157
§ 3. Максимальный объем деревьев в случайном отображении ...................... 166
§ 4. Ветвящиеся процессы и случайные леса....... 173
§ 5. Высота случайного отображения.......... 179
§ 6. Дополнения и литературные ссылки........ 189
Литература ........................ 201

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

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

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

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

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

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

Книга состоит из трех глав. В гл. I излагаются результаты, получаемые с помощью сведения задач к обобщенной схеме размещения частиц. Особое внимание уделяется изучению циклового строения случайных подстановок, взаимно однозначных отображений конечного множества в себя, а также объемам компонент случайного отображения. В гл. II с помощью теории ветвящихся процессов изучаются случайные деревья. В гл. III связь с ветвящимися процессами распространяется на случайные леса и с помощью результатов о случайных лесах исследуются свойства случайных однозначных отображений.

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

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

В книге принята следующая нумерация формул, теорем, лемм и следствий. В каждом параграфе для каждого из этих объектов имеется своя нумерация, используемая при ссылках внутри параграфа. При ссылке на объект из другого параграфа той же главы к его номеру добавляется номер параграфа, а при ссылке на объект из другой главы—еще и номер главы. Так, на теорему 1 из § 2 гл. III ссылаются в § 2 гл. III как на теорему 1, в другом параграфе гл. III как на теорему 2.1 ив другой главе как на теорему 3.2.1. Аналогичного правила придерживаются и при ссылках на параграфы, которые в каждой главе имеют свою нумерацию.

Автор благодарен И. Б. Калугину, замечания которого помогли устранить в рукописи ряд неточностей.

1982 г. В. Ф. Колчин


Об авторе
Колчин Валентин Федорович
Доктор физико-математических наук, действительный член Академии криптографии РФ. Окончил механико-математический факультет МГУ и аспирантуру Математического института имени В. А. Стеклова АН СССР, в котором работал с 1961 г. Был заместителем главного редактора журнала «Математические заметки», членом редколлегии журнала «Random structures and algorithms». Организовал журнал «Дискретная математика»; заместитель главного редактора, а в 2004–2013 гг. — главный редактор. Организатор Петрозаводских конференций по вероятностным методам в дискретной математике; активно участвовал в создании и организации работы Института прикладных математических исследований Карельского научного центра РАН.

В. Ф. Колчин — признанный специалист по теории случайных размещений, случайных графов и системам случайных уравнений над конечными полями; автор работ по теории случайных размещений частиц по ячейкам, случайным подстановкам и отображениям, системам дискретных уравнений, локальным предельным теоремам для сумм случайных величин. Он разработал эффективный метод доказательства предельных теорем в комбинаторных схемах, основанный на представлении изучаемых распределений как условных распределений сумм независимых случайных величин. Автор около 40 статей и трех монографий.