# Tag Info

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. ...
• 277k
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.
• 371

### 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)$ ...
• 277k
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$.
• 277k

### 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 ...
• 159k

### 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/...
• 141
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 ...