Вопросы с тегом «random-walks»

30
Пьяные птицы против пьяных муравьев: случайные прогулки между двумя и тремя измерениями

Хорошо известно, что случайное блуждание в двумерной сетке вернется в начало координат с вероятностью 1. Также известно, что такое же случайное блуждание в ТРЕХ измерениях имеет вероятность, строго меньшую 1, возврата в начало координат . Мой вопрос: Есть что-то среднее? Например, предположим, что...

23
Рандомизированная сложность запроса для проблемы со связанными деревьями

Важная статья 2003 года Childs et al.представил «проблему соединенных деревьев»: проблему, допускающую экспоненциальное квантовое ускорение, которое не похоже ни на одну другую подобную проблему, о которой мы знаем. В этой задаче нам дан экспоненциально большой граф, подобный изображенному ниже,...

22
Количество отдельных узлов в случайной прогулке

Время коммутирования в связанном графе определяется как ожидаемое количество шагов в случайном блуждании, начиная с , до посещения узла и затем достижения узла снова. В основном это сумма двух времен удара и .G = ( V, E)гзнак равно(В,Е)G=(V,E)яяiJJjяяiЧАС( я , j )ЧАС(я,J)H(i,j)ЧАС( J , I...

17
Свойства случайно ориентированных графов с фиксированной степенью выхода

Меня интересуют свойства случайных ориентированных графов с фиксированной степенью ddd . Я представляю модель случайного графа, где каждая вершина выбирает d соседей (скажем, с заменой) uar Вопрос : Известно ли что-нибудь о стационарном времени распределения и перемешивания случайных блужданий на...

17
Время покрытия ориентированных графов

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

13
Одноразовый квантовый удар

В статье « Квантовые случайные прогулки идут экспоненциально быстрее» ( arXiv: quant-ph / 0205083 ) Кемпе дает понятие времени удара для квантовых блужданий (в гиперкубе), которое не очень популярно в литературе по квантовым блужданиям. Это определяется следующим образом: Один выстрел Квантовый...

12
Переход от квантовых к классическим случайным блужданиям по прямой

Быстрая версия Существуют ли модели декогеренции для квантового блуждания на линии, чтобы мы могли настроить блуждание так, чтобы оно распространялось как для любого ?1 / 2 ≤ K ≤ 1Θ(tk)Θ(tk)\Theta(t^k)1/2≤k≤11/2≤k≤11/2 \leq k \leq 1 мотивация Классические случайные блуждания полезны при разработке...

10
Перестановка токенов на графе с использованием локальных свопов

Пусть нерегулярный связный граф, степень которого ограничена. Предположим, что каждый узел содержит уникальный токен.G=(V,E)G=(V,E)G= (V, E) Я хочу равномерно перетасовать токены среди графа, используя только локальные перестановки (т.е. обмен токенами между двумя соседними узлами)? Известна ли...

10
Случайное блуждание и среднее время попадания в простой неориентированный граф

Пусть простой неориентированный граф на n вершинах и m ребрах.G = ( V, E)гзнак равно(В,Е)G=(V,E)NNnммm Я пытаюсь определить ожидаемую продолжительность работы алгоритма Вильсона для генерации случайного остовного дерева . Там показано, что O ( τ ) , где τ - среднее время удара : τ = ∑ v ∈ V π ( v )...

10
Найти приблизительное значение argmax, используя только приблизительные максимальные запросы

Рассмотрим следующую проблему. Есть неизвестных значений v 1 , ⋯ , v п ∈ R . Задача состоит в том, чтобы найти самый большой индекс, используя только запросы следующей формы. Запрос задается множеством S ⊆ { 1 , ⋯ , n }, и соответствующий ответ max i ∈ S v i . Цель состоит в том, чтобы использовать...

9
Как я могу случайным образом генерировать деревья с ограниченной высотой?

Для проекта, над которым я работаю, я должен генерировать случайные остовные деревья с ограниченной высотой. В основном я делаю следующее: 1) Создаю связующее дерево. 2) Проверяю осуществимость, если возможно, сохраняю его. 1) Начиная с минимального связующего дерева (Прима или Крускала), я...

9
Технический вопрос о случайных прогулках

(На мой первоначальный вопрос до сих пор нет ответа. Я добавил дополнительные пояснения.) При анализе случайных блужданий (на неориентированных графах), рассматривая случайное блуждание как цепь Маркова, мы требуем, чтобы граф был не двудольным, чтобы применялась основная теорема о цепях Маркова....

9
Время покрытия и спектральный разрыв для обратимых случайных блужданий

Я ищу теорему, которая говорит что-то вроде этого: если время накрытия обратимой цепи Маркова мало, то спектральная щель велика. Здесь спектральная щель означаетто есть мы игнорируем наименьшее собственное значение цепочки.1 - |λ2|1-|λ2|1-|\lambda_2| Единственный результат, который мне удалось...