7 votes
Accepted

Expected length of a random walk on a line

The behavior when $p = 1/2$ and when $p > 1/2$ is rather different. When $p > 1/2$, in expectation you move $2p-1$ steps to the left, so you will hit the origin after a linear number of steps. ...
Yuval Filmus's user avatar
6 votes
Accepted

Algorithm to generate self-avoiding random walk on a lattice

A procedure is described in A combinatorial algorithm for effective generation of long maximally compact lattice chains.
Tomoki's user avatar
  • 371
4 votes

Generating uniform random connected graphs: doubt about Wilson's algorithm

Here are two alternative algorithms. There are probably better ones. Large $m$ When $m \gg \frac{1}{2} n\log n$, it is very likely that a $G(n,m)$ random graph will be connected. Generate $G(n,m)$ ...
Yuval Filmus's user avatar
4 votes
Accepted

Random Walk on the Integer Line

Hint: $S_l - S_r$ is the sum of $2n$ independent variables $X_1,\ldots,X_{2n}$, with $\Pr[X_i = 1] = \Pr[X_i = -1] = 1/2$.
Yuval Filmus's user avatar
4 votes

Random walk increasing distance

It's easiest to understand with a one-dimensional random walk. After $n$ steps, the typical value for the distance from the origin is proportional to $\sqrt{n}$. Thus, the more steps you take, the ...
D.W.'s user avatar
  • 159k
4 votes

Algorithm to generate self-avoiding random walk on a lattice

Here are two javascript implementations of an algorithm to sample Hamiltonian paths on 2-dimensional grid graphs: http://clisby.net/projects/hamiltonian_path/ and http://clisby.net/projects/...
Nathan's user avatar
  • 141
3 votes

Random walks on Complete Binary Trees

This answers a previous version of the question, in which the goal was to prove that with high probability, $\max |H_i - \frac{n}{3}| \geq C\sqrt{n\ln m}$ for some constant $C > 0$. When a ...
Yuval Filmus's user avatar
3 votes

Generate random matrix and its inverse

Efficient Generation of Random Nonsingular Matrices by Dana Randall covers exactly this topic. In particular Corollary 1.1 states: We can uniformly generate a matrix and its inverse in time $2M(n) +...
orlp's user avatar
  • 13.4k
3 votes

Average vs Worst-Case Hitting Time

This is an addendum to the answer by Yuval Filmus. Indeed $\phi(n)=\Theta(n)$, and the upper bound is explained in that answer. I don't understand the argument for the lower bound given there, but a ...
Yuval Peres's user avatar
2 votes
Accepted

Randomized algorithm for 2kCNF satisfiability problem

The analysis of Schöning's algorithm (see for example these CMU lecture notes) relies on the fact that if $\alpha$ is a satisfying assignment, $\beta$ is any assignment, and $C$ is an unsatisfied $k$-...
Yuval Filmus's user avatar
2 votes
Accepted

Sampling in large graph using simple random walk

While the algorithm doesn't know the graph, when you are analyzing the performance of the algorithm on a graph, you do know the graph. For a similar example, take the egg dropping puzzle. In this ...
Yuval Filmus's user avatar
2 votes
Accepted

expected running time of Randomwalk for k-SAT

The probability that step 4 brings $X$ closer to the unique satisfying assignment is not $1/k$. Rather, it is at least $1/k$. When $X$ is far away from a satisfying assignment, the probability is ...
Yuval Filmus's user avatar
2 votes
Accepted

How long a graph random walk takes to hit every vertex?

The cover time is at most the maximal hitting time multiplied by the harmonic number $1+\ldots+1/n$. This is the Mathews bound, see, e.g., Section 11.2 in [1]. In fact, the cover time can be ...
Yuval Peres's user avatar
1 vote
Accepted

Probability of reaching a state in asymmetric random walk

Suppose that $S_T > C\ln T$. Let $T_0-1$ be the last time that the random walk reached the origin. Thus if we run an unconstrained biased random walk starting at position $1$ at time $T_0$, we ...
Yuval Filmus's user avatar
1 vote

Random walk increasing distance

A two-dimensional random walk is equivalent to two independent one-dimensional random walks running in parallel. To see this, rotate the plane 45 degrees. The possible steps are all four diagonals, ...
Yuval Filmus's user avatar
1 vote

Generating a random path in a grid without deadlock

You have a solid grid graph, and want to generate a random Hamiltonian path in it. The following paper describes a polynomial-time algorithm to generate such a path, randomly (from a distribution ...
D.W.'s user avatar
  • 159k
1 vote

2D random walk. Should both dimensions be independent?

The usual 2D random walk goes one step in one of the cardinal directions (up, down, left, or right). If you rotate the plane by 45 degrees, you get a random walk which moves up or down and left or ...
Yuval Filmus's user avatar
1 vote

Proving that the cover time for graph is exponential in the worst case

If the digraph is not strongly connected, then the cover time is infinite, so let's assume the digraph is strongly connected. Here is an example: Consider $n>2$ vertices $v_1,\ldots,v_n$, with a ...
Yuval Peres's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible