Парадокс дней рождения для марковских цепей

Пусть в году планеты Транай $N$ дней. Будем опрашивать прохожих на транайских улицах, когда у них день рождения, пока одна из дат не повторится. Хорошо известно и несложно видеть, что в среднем потребуется задать порядка $C\sqrt{N}$ вопросов (даже если транайцы в некоторые дни рождаются чаще, чем в другие). На это можно смотреть как на марковский процесс — блуждание по полному графу с петлями, в котором вероятность из вершины $a$ придти в $b$ зависит только от $b$. Вопрос о средней длине путешествия до первого повторения можно ставить и для других марковских цепей. Мы собираемся обсудить результат Назарова–Переса, состоящий в том, что среднее время повторения есть $O(\sqrt{N})$ для равномерных блужданий на графах с $N$ вершинами (из текущей вершины переходим в одну из соседних с равной вероятностью), а также обсудить эту задачу для блужданий по графам, в которых следующая вершина выбирается равномерно среди соседей, отличных от предыдущей.