0
votes
0answers
48 views

How to prove that the hitting time for a random $(2,k)$-walk is $\mathcal{O}(\frac{k^4}{r})$?

I'm using the following definitions: An $(x, y)$-partial-rectangle is a sequence of x integers $(i_1,i_2,\ldots,i_x)$ such that $0 \leq i_1 \leq i_2 \leq \ldots i_x \leq y$. One ...
3
votes
1answer
192 views

Solving a maze by taking a random walk

I vaguely recall a result like the following from one of my complexity theory classes in school: given a 2d maze (which I guess we can think of as a directed graph with a fixed start node and exit ...