Время покрытия

Время покрытия

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

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

Классическая задача теории вероятностей — задача коллекционера купонов — может быть интерпретирована как результат, что ожидаемое время покрытия полного графа $K_n$ равно $n\ln n+O(1)$. Любой регулярный граф-экспандер с $n$ вершинами также имеет ожидаемое время покрытия $\mathrm{\Theta }(n\log n)$ из любого начальной вершины, и более общо, время покрытия любого регулярного графа равно $$O\left(\frac{n\log n}{1-{\lambda }_2}\right),$$ где ${\lambda }_2$ — второе по величине собственное значение графа, нормированное так, что наибольшее собственное значение равно единице. Для произвольных графов с $n$ вершинами, из любого начальной вершины, время покрытия не превышает $$(\frac{4}{27}+o(1))n^3$$, и существуют графы, время покрытия которых достигает этой величины.

См. также

• Время достижения — количество шагов до первого достижения множества состояний