Эта страница переведена с помощью средств машинного перевода. Смотреть оригинал

Доказательство на основе декомпозиции для быстрого смешения марковской цепочки по сбалансированным реализациям совместной матрицы степени.

Авторы
ИзданиеarXiv.org.
Год издания2013

 Совместная матрица степени (JDM) определяет количество связей между узлами заданных степеней в графе для всех пар степени и однозначно определяет степень градуировки графа. Мы рассматриваем пространство всех сбалансированных реализаций произвольной JDM, реализаций, в которых связи между любыми двумя группами степеней размещаются как можно более равномерно. Мы доказываем, что алгоритм свопинга Маркова Чейна Монте-Карло (MCMC) в пространстве всех сбалансированных реализаций {\ em произвольного} графического JDM быстро смешивается, т.е.E., Время релаксации цепи ограничено сверху многочленом от числа узловn. Чтобы доказать быстрое перемешивание, сначала докажем общую факторизационную теорему, аналогичную методу Мартина-Рэндалла для непересекающихся разбиений (разбиений). Эта теорема может быть использована для ограничения снизу спектральной щели с помощью быстрых перемешивающих подцепей в каждом разбиении и оценки на вспомогательную цепь Маркова между разбиениями. Наше доказательство общей теоремы факторизации является прямым и использует методы, основанные на проводимости (неравенство Чигера).

 Представлен, 18 страниц, 4 рисунка Опубликовано: SIAM J. Дискретная математика 29 (1) (2015), 481-499

Ссылка на публикацию
Ердőс П. Л., Миклóс И. , Торокзкаи З.   Доказательство на основе декомпозиции для быстрого смешения марковской цепочки по сбалансированным реализациям совместной матрицы степени. - : , 2013. // arXiv.org, 2013.
Библиография
1.Y. Аманатидис, Б. Зеленый, М. Михаил, Гибкие модели для сложных сетей, Постер в Центре Алгоритмов Случайность и Вычисление, 2008. Также представлена ​​пленарная лекция М. Михаил на ежегодной конференции SIAM по дискретной математике, 2008.
2.Я. Bez? Akov? A, N. Бхатнагар и Э. Вигода, Дискретизация двоичных таблиц сопряженности с жадным началом, случайными структурами и алгоритмами, 30 (1-2) (2007), 168-205.
3.Я. Bez? Akov? A, Образцы двоичных таблиц сопряженности, Comp. Sci. Eng., 10 (2) (2008), 26--31.
4.Я. Bez? Akov? A, N. Бхатнагар и Д. Рэндалл, О цепочке Маркова Дьякониса-Ганголли для выборки таблиц сопряженности с ячейками с ограниченным элементом, Дж. Расческа. Optim. 22 (3) (2011), 457-468.
5.Я. Безаков? А, А. Синклер, Д. Стефанкович и Э. Vigoda, Отрицательные примеры для последовательной валидации выборки двоичных таблиц сопряженности, Алгоритмика 64 (4) (2012), 606--620.
6.J. Бланшет, Важность дискретизации и эффективного подсчета для двоичных таблиц сопряженности, Анналы прикладной вероятности, 19, (2009), 949--982.
7.S. Караччиоло, А. Пелиссетто и А. D. Сокал, Два замечания по моделированию закалки. Неопубликованная рукопись. Доказательство теоремы о факторизации воспроизводится в [? ] Как Thm 3.1.
8.Y. Чен, П. Диаконис, С.П. Холмс и Дж.S. Лю, последовательные методы Монте-Карло для статистического анализа таблиц, журнал Американской статистической ассоциации, 100 (469) (2005), 109-120.
9.С. Купер, М. Дайер и С. Greenhill, Sampling regular graphs и одноранговая сеть, Comp. Prob. Comp., 16 (4) (2007), 557-593.
10.М. Cryan, M.Дайер, Л.A. Голдберг, М. Джеррум и Р. A. Мартин, Быстрое смешивание марковских цепей для выборки таблиц сопряженности с постоянным числом строк, SIAM J. Вычисл. 36 (1) (2006), 247-278.
11.М. Cryan, M. E. Дайер и Д. Рэндалл, Приблизительный подсчет интегральных потоков и таблиц связанных с ячейками, SIAM J. Вычисл. 39 (7) (2010), 2683-2703.
12."? E. Czabarka, A. Dutle, P.L. Эрдос, I. Mikl? Os, О реализации совмещенной матрицы степеней, представленный, arxiv.Org / pdf / 1302.3548v2 (2013).
13.С.Я. Дель Генио, Х. Ким, З. Toroczkai, K.E. Басслер, Эффективная и точная выборка простых графов с заданной произвольной степенной последовательностью, PLoS ONE, 5 (4) (2010), e10012.
14.П. Диаконис и А. Gangolli, прямоугольные массивы с фиксированными полями. Дискретная вероятность и алгоритмы, Под ред.: D. Aldous et al., Springer-Verlag, (1995), pp. 15--41.
15.П. Диаконис и Л. Салофф-Косте, Теоремы сравнения для обратимых цепей Маркова, Ann. Appl. Probab., 3 (2) (1993), 696-730.
16.П. Диаконис и Д. Stroock, Геометрические оценки для собственных значений марковских цепей, Ann. Appl. Probab., 1 (1) (1991), 36-61.
17." П.L. Эрдос, З. S. Поцелуй, я. Mikl? Os, L. Soukup, Построение, выборка и подсчет графических реализаций ограниченных последовательностей степеней, представленных, arxiv.Org / pdf / 1301.7523v2 (2013)
18.T. Федерер, А. Guetz, M. Михаил и А. Сабери, локальная цепь Маркова Маркова на заданных графиках степени с применением в связности одноранговых сетей, FOCS06 (2006), 69--76.
19.М. К. Ganapathy, Робастное смешивание, Ph.D. Диссертация, Университет Чикаго, август 2006.
20.С. Гринхилл, Полином, связанный с временем смешивания марковской цепи для выборки регулярных ориентированных графов, Электронный J. Расческа., 16 (4) (2011), стр. 557-593.
21.М. Джеррум, А. Синклер, Приближение постоянного, SIAM J. Вычисл. 18 (6) (1989), 1149-1788.
22.М. Джеррум, А. Синклер и Э. Вигода, Алгоритм аппроксимации полиномиального времени для постоянной матрицы с неотрицательными записями, J. ACM, vol. 51 (4) (2004), 671-697.
23.ЧАС. Ким К.Я. Дель Генио, К.E. Басслер и З. Toroczkai, Построение и выборка ориентированных графов с заданными последовательностями степени New J. Phys., 14 (2012), 023012.
24.H. Ким, З. Toroczkai, P.L. Эрдос, I. Mikl? Os, L. Sz? Ekely, Градуированная конструкция графа. J Phys A: Математическая теория., 42 (2009), 39.
25.Р. Каннан, П. Тетали и С. Вемпала, Алгоритмы простой марковской цепи для порождения двудольных графов и турниров, Алгоритмы случайных структур, 14 (4) (1999), 293--308.
26.Z. Кирьяли, признавая последовательности графических степеней и генерируя все реализации, технический отчет EGRES TR-2011-11, ISSN 1587-4451 (2012), 1--11.
27.Р. Мадрас и Д. Рэндалл, цепная декомпозиция Маркова для анализа скорости сходимости, Ann. Appl. Probab., 12 (2002), 581-660.
28.Р. Мартин и Д. Рэндалл, Непересекающееся разложение цепей Маркова и схемы выборки в графах Кэли, Комбинация. Probab. Вычисл., 15 (2006), стр. 411-448.
29.«Я. Mikl? Os, P.L. Эрдос, Л. Сукуп, К случайной однородной выборке двудольных графов с заданной степенной последовательностью, Электронная J. Расческа., 20 (1) (2013), P16.
30.A.N. Патринос и С.L. Хакими, Отношения между графами и последовательностью целочисленных пар, Discr. Математика., 15 (1976), 347-358.
31.D. Рэндалл, быстро смешивая цепи Маркова с приложениями в информатике и физике, Comp. Sci. Eng., 8 (2) (2006), pp. 30--41.
32.A. Синклер, Улучшенные оценки скоростей перемешивания марковских цепей и многопотокового потока, Комбинат. Probab. Вычисл., 1 (1992), pp. 351-370.
33.Я. Стэнтон, А. Пинар, Построение и выборка графов с заданным распределением степени распространения, ACM J. Exp. Алгоритмы, 17 (3) (2012), 3.5.

Эта публикация на других ресурсах

Портал arXiv.org

Другие публикации этих авторов
1.Не все простые проблемы последовательности степеней легко
Ердőс П. Л., Миклóс И.
2.Новые классы степенных последовательностей с быстрым перемешиванием своп Марковская цепная выборка
Ердőс П. Л., Миклóс И. , Торокзкаи З.
3.Реализации графов, ограниченные скелетными графами
Ердőс П. Л., Хартке С. Д., Лео В. И., Миклóс И.
4.Построение, выборка и подсчет графических реализаций ограниченных последовательностей степеней
Ердőс П. Л., Кисс С. З., Миклóс И. , Соукуп Л.
5.На swap-расстояниях различных реализаций графической последовательности степеней
Ердőс П. Л., Кирáлу З. , Миклóс И.
6.А-Я-тождества и строгие 2-частичные свойства Спернера в позициях продукта
Аудиниан Х. , Ердőс П. Л.
7.К выборочной случайной выборке двудольных графов с заданной степенной последовательностью
Ердőс П. Л., Миклóс И. , Соукуп Л.
8.Простой алгоритм типа Хавела-Хакими для реализации графических степенных последовательностей направленных графов
Ердőс П. Л., Миклóс И. , Торокзкаи З.
9.Графическое построение на основе степеней
Ким Х. Х., Торокзкаи З. , Ердőс П. Л., Миклóс И. , Сзéкелу Л. А.
10.Квази-ядра и квазисредние в бесконечных графах
Ердőс П. Л., Соукуп Л.
Другие публикации этой тематики
1.Спектральные оценки связности регулярных графов с заданным порядком
Абиад А. , Бримков Б. , Мартинез-ривера Х. , Суил О. , Зхандж Д. Д.
2.Связность графов графов с самоциклами и заданной степенной последовательностью
Нисхимура Д.
3.Не возвращающая теорема Пойя
Кемптон М.
4.Curveball: новое поколение алгоритмов выборки для графиков с фиксированной степенью последовательности
Коррие Д. К., Берджер А. , Строна Д.
5.K-связные степени
Мклауджхлин Д.
6.Равномерная генерация случайных регулярных графов
Джао П. , Вормалд Н. К.
7.О числе керлинга некоторых графов
Кок Д. , Судев Н. К., Судев К.
8.Построение, выборка и подсчет графических реализаций ограниченных последовательностей степеней
Ердőс П. Л., Кисс С. З., Миклóс И. , Соукуп Л.
9.Подграфы плотных случайных графов с заданными степенями
Мккау Б. Д.
10.Замечание о регулярных графах Рамсея
Алон Н. , Бен-схимон С. , Кривелевикх М.