Гауссовский процесс назначений

Введение 3
2 Постановка задачи 8
3 Предварительные сведения 8
3.1 Обозначения и определения 8
3.2 Базовые свойства 9
3.3 Вспомогательные утверждения 12
4 Основные результаты 14
4.1 Оценки максимума процесса назначений 14
4.2 Оценки модуля непрерывности 17
4.3 Анализ жадной стратегии 22
4.4 Центральная предельная теорема 25
5 Доказательства лемм 29
6 Заключение 33
Список литературы 34
Купить

В данной работе рассматривается задача о случайном назначении. Задача формулируется следующим образом. Рассмотрим квадратную nх nматрицу (Xij), состоящую из независимых, одинаково распределенных случайных величин, имеющих распределение P, то есть Xij ~ P. Каждой перестановке я : {1, 2,... , ng ! {1,2,..., ng ставится в соответствие сумма
S(я) = XXi,(i).
i=1
В общей постановке задачи требуется изучить свойства случайной величины min S(я) или max S(я) и найти оптимальную перестановку я* такую, что я* = arg min E [S (я)] или я* = arg max E [S (я)].
Задача о назначениях возникает естественным образом из следующей оптимизационной задачи. Допустим, имеется n заказов и n станков, на которых можно выполнить эти заказы. Предположим, что величина Xj отражает стоимость изготовления заказа i на станке j. На каждом станке можно выполнять лишь один заказ. Естественно желание минимизировать суммарную стоимость, потраченную на выполнение всех n заказов. Решением задачи будет являться оптимальное паросочетание на двудольном графе (см. рис.1). В случае с максимумом можно думать о Xijкак, например, о количестве информации, передаваемой из источника i в приемник j.
Разновидности данной задачи встречаются во многих разделах математики, чем и обусловлен повышенный интерес к ней. Более подробно о возможных применениях можно прочитать в [1,2].
Вариант задачи, когда случайные величины (Xj) независимы и имеют равномерное распределение на отрезке [0,1], был изучен в работе Steele [1], а также в работе Mezard и Parisi [3], в которой авторы доказали, что
С (2) + 2<(3) + 4 П, при n !1
n n2
Mezard и Parisi [4] были первыми, кто выдвинул гипотезу, что в экспоненциальном случае (P = Exp(1)) имеет место предельное соотношение:
min S(я)
K2Sn
Используя метод реплик из статистической физики [5], авторы привели нестрогую аргументацию в подтверждение своей гипотезы.
Позднее в [6]Parisi выдвинул гипотезу об аналитическом выражении для математического ожидания минимума процесса назначений в экспоненциальном случае при фиксированном n:
n1
min S(я) = .
^esn k2
Данная гипотеза была подтверждена автором при n = 1, 2 и при n ! 1. Кроме того, он не смог найти противоречий в численных экспериментах при малых n, что мотивировало в поиске доказательства гипотезы. Доценко в своей работе [7] исследовал точное решение задачи в экспоненциальном случае.
Coppersmith - Sorkin [2] и другие [8,9] исследовали точные формулы для связанных задач, например, для случая построения паросочетаний на графе из двух неравных долей размеров mи n. Так, например, Sorkin [8] рассмотрел матрицу Aразмера m х n, состоящую из независимых стандартных экспоненциальных случайных величин и определил функцию A*(k, m, n), которая равна наименьшей сумме kэлементов матрицы A, таких, что никакие два не находятся в одной строке или столбце. Подчеркивается, что случай k = m = n совпадает со стандартной постановкой задачи. Гипотеза утверждает, что
Е[A*(n,n,n)]= X 1;
i=1 b
что совпадает со стандартной гипотезой, выдвинутой Parisi. Данная гипотеза
была доказана в работе Sorkin [8] при малых значениях k,m,n.
В своей работе [10]Aldous дал строгое доказательство предельного соотно-шения в экспоненциальном случае
min S(я) ^esn
тем самым доказав гипотезу, выдвинутую Mezard и Parisi [4]. Также был доказан ряд других гипотез относительно распределения весов ребер в построенном оптимальном паросочетании. В своей работе Aldous продолжил подход, разработанный в одной из своих предыдущих статей [11]. Подход основан на анализе задачи назначения на бесконечном дереве, ребра которого имеют неотрицательные веса, распределенные как Exp(1).
В данной работе рассматривается частный случай задачи о случайном на-значении, когда распределение величин Pявляется стандартным нормальным, то есть P = N(0,1), и исследуется максимум случайного назначения. Далее мы будем называть такой процесс гауссовским процессом назначений. Подчеркнем, что гауссовское распределение имеет неограниченный носитель, что принципиально меняет результаты: математическое ожидание максимума не стремится к конечному пределу, а неограниченно возрастает с ростом п. Из свойства максимума процесса можно получить свойства минимума, поскольку стандартное нормальное распределение симметрично относительно нуля.
Структура работы такова. В разделе2 формально определена задача, которая была поставлена в рамках данного исследования. После этого в разделе3перечислены вспомогательные утверждения, на которые упираются доказательства основных результатов. В части4 доказаны основные результаты, полученные в ходе работы. В разделе4.1 доказаны верхние и нижние оценки математического ожидания максимума гауссовского процесса назначений. Показано, что математическое ожидание максимума гауссовского процесса назначений асимптотически ведет себя как Пд/2 log n. Также в разделе4.2 получены асимптотические оценки математического ожидания модуля непрерывности. В конце работы доказана оптимальность жадной стратегии перестановки с точки зрения математического ожидания и дополнительно доказана центральная предельная теорема.
Купить