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

Верхние границы времени попадания случайных блужданий на разреженных графах.

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

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

 25 страниц, 20 рисунков

Ссылка на публикацию
Фомин Д. В.  Верхние границы времени попадания случайных блужданий на разреженных графах. - : , 2017. // arXiv.org, 2017.
Библиография
1.J.L. Дуб (1953), «Стохастические процессы», J.Wiley & Sons, Inc., Нью-Йорк, N.Y.
2.W. Феллер (1968), "Введение в теорию вероятностей и ее приложения", J.Wiley & Sons, Inc., 3-е издание, Нью-Йорк, Н.Y.
3.Р. Aleliunas, R.М. Карп, Р.J. Lipton, L. Lovasz, C.W. Rackoff (1979), "Случайные блуждания, универсальные последовательности перемещения и сложность проблем лабиринта", Proc. 20 Ann. Symp. На Основах информатики, с.218-223oC.
4.П.Г. Doyle, J.L. Снелл (1984), «Случайные блуждания и электрические сети», Карус Математические монографии, том 22, Математическая ассоциация Америки, Вашингтон, округ Колумбия.
5.Г. Брайтвелл, П. Winkler (1990), "Максимальное время удара для случайных блужданий на графах", J. Случайные структуры и алгоритмы 1, с.263-276oC.
6.L. Lovasz (1993), «Случайные блуждания по графам: обзор», Bolyai Society Mathematical Studies, vol.2, Комбинаторика (Пол Эрдос - Восемьдесят), с.1--46, Кестхей, Венгрия
7.Г. Blom, L. Holst, D. Sandell (1994), «Проблемы и снимки из мира вероятностей», Springer-Verlag, Нью-Йорк, Н.Y.
8.A.К. Чандра, P. Raghavan, W.L. Ruzzo, R. Смоленский, П. Tiwari (1996), «Электрическое сопротивление графика фиксирует время коммутирования и покрытия», Computational Complexity, December 1996, Volume 6, Issue 4, pp.312-340.
9.J. Норрис (1997), «Марковские цепи», Cambridge University Press, Нью-Йорк, Н.Y.
10.С. Godsil, G. Ройл (2001), "Алгебраическая теория графов", Springer-Verlag, Нью-Йорк, Н.Y.
11.D. Олдос, Дж.A. Fill (2002), «Обратимые марковские цепи и случайные блуждания на графах», незаконченная монография
12.O. Reingold (2005), «Непрямая ST-связность в log-пространстве», Труды тридцать седьмого ежегодного симпозиума ACM по теории вычислений, 22-24 мая 2005 г., стр.376--385, Baltimore, MD, USA,
13.Г. Гримметт (2010), «Вероятность на графиках», Cambridge University Press, Нью-Йорк, Н.Y.
14.D. Spielman (2012), «Теория спектральных графов», лекции Йельского университета
15.J. Хопкрофт, Р. Каннан (2014), «Основы науки о данных», незаконченная монография
16.Р. Лион, Y. Перес (2016), «Вероятность на деревьях и сетях», Cambridge University Press, Кембридж, Великобритания

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

Портал arXiv.org