Хорошо известно, что случайное блуждание в двумерной сетке вернется в начало координат с вероятностью 1. Также известно, что такое же случайное блуждание в ТРЕХ измерениях имеет вероятность, строго меньшую 1, возврата в начало координат . Мой вопрос: Есть что-то среднее? Например, предположим, что...
В связи с загадкой Slither Link мне было интересно: предположим, что у меня сетка квадратных ячеек, и я хочу найти простой цикл ребер сетки, равномерно случайным образом среди всех возможных простых циклов.n×nn×nn\times n Один из способов сделать это - использовать цепь Маркова, состояния которой...
Динамика Глаубера - это марковская цепочка на раскрасках графа, в которой на каждом шаге пытаются перекрасить случайно выбранную вершину в случайный цвет. Он не смешивается для 3-х раскрасок из 5-ти циклов: существует 30 3-раскрасок, но только 15 из них могут быть достигнуты с помощью шагов...
При случайном блуждании на графике время покрытия - это первый раз (ожидаемое количество шагов), когда каждая вершина была поражена (покрыта) блужданием. Известно, что для связных неориентированных графов время накрытия ограничено сверху . Существуют сильно связанные орграфы с показателем времени...
Рассмотрим следующий процесс: Есть корзин, расположенных сверху вниз. Первоначально, каждая корзина содержит один шар. На каждом шагу мыNNn выбрать мяч равномерно наугад иббb переместите все шары из корзины, содержащей в корзину под ней. Если это уже была самая низкая корзина, мы удаляем шары из...
В статье « Квантовые случайные прогулки идут экспоненциально быстрее» ( arXiv: quant-ph / 0205083 ) Кемпе дает понятие времени удара для квантовых блужданий (в гиперкубе), которое не очень популярно в литературе по квантовым блужданиям. Это определяется следующим образом: Один выстрел Квантовый...
Какие конкретные и убедительные приложения для оценки объема выпуклых многогранников того типа, которые рассматривались в более поздних статьях о методах случайного блуждания? В этих работах по оценке объема упоминается численная интеграция как одна из причин. Какие примеры интегралов, которые люди...
Я особенно заинтересован в их использовании в приложениях для проверки моделей. У меня есть открытые, закрытые и смешанные сети очередей с разными классами клиентов по Baskett et al. Любые другие предложения для чтения материала?...