# Questions tagged [random-walks]

The tag has no usage guidance.

25 questions
Filter by
Sorted by
Tagged with
409 views

### On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)

I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
2k views

### Algorithm to generate self-avoiding random walk on a lattice

Where can I find some code to generate random self-avoiding walks on 2 and 3-dimensional lattices whose side-lengths are powers of two? The walk should pass through every point on the lattice More ...
349 views

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

I want to generate a random connected simple labeled graph with $n$ vertices and $m$ edges, selected uniformly over all connected graphs with such $n$ and $m$. I found this approach. It says: build a ...
334 views

### Examples for directed graphs with super polynomial cover time

The cover time of a graph is the expected number of steps in a random walk on the graph until we visit all the nodes. For undirected graphs the cover time is upperbounded by $O(n^3)$. What about ...
143 views

133 views

### Generate random matrix and its inverse

I want to randomly generate a pair of invertible matrices $A,B$ that are inverses of each other. In other words, I want to sample uniformly at random from the set of pairs $A,B$ of matrices such that ...
52 views

### Sampling in large graph using simple random walk

I'm studying sampling techniques in online social networks. The assumption is we don't have full access to the network(i.e, we donāt know the size of the network). However crawling is supported, i.e, ...
113 views

### Electrical resistance of expander graphs

Let $G$ be a $d$-regular expander graph. What is the electrical resistance of $G$? Is it a constant independent of the number of nodes $n$ once $d$ is large enough? If not, can we give matching upper ...
112 views

### 2D random walk. Should both dimensions be independent?

My assignment is to compare several probability distributions in random walk algorithm. I'd like to analyse it in 2D linear space to make the concept more intuitive. What is the correct approach in ...
123 views

### Graph conductance - program/code/library

Technical question: is there any open source program/code/library which can compute (minimal) conductance of a given graph, probably by some simulated annealing? Think it is quite well-known problem, ...
143 views

### Random walk increasing distance

I'm wondering why if I increase the number of step in a set of simulation of a random walk on a grid the distance from the origin is higher. If I can move on the grid in 4 directions, there are 0.5 ...
160 views

### Random walks on Complete Binary Trees

Let $T$ be a complete binary tree of height $n$ and root $r$. A random walk starts at $r$, and at each step uniformly at random moves on a neighbor. There are $m$ random walkers all starting at $r$ ...
44 views

### Randomized algorithm for 2kCNF satisfiability problem

The problem: Let a formula in $\varphi\in 2kCNF$ where there's an assignment $\alpha$ such that for every clause, $l$ in $\varphi$, $\alpha$ satisfies at least $k$ literals of $l$. Suggest a ...
82 views

### MATLAB script to model biological branching process

I took an introductory MATLAB course a couple of years ago (and since then have only taken a basic C++ course) and am presently stumped as to how to start with a project I am undertaking. As part of ...
132 views

### Probability of finding the maximum element in a heap

You are given a minimum heap, with probability going to left is 50% and going to right is 50%. What is the probability that You will land up on a maximum element in the heap? For this scenario since ...
22 views

### Prior papers on hash walks [closed]

Random walks are well known from probability theory. I have the idea for hash walks. If h(x) is a hash function and a,b,c,d,e,f is a boolean sequence then the sort of hash walk I am talking about is ...
270 views

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

How can I prove that the cover time for a directed graph $G$ can be exponential in the size of $G$? The cover time is the expected length of a random walk that visits all vertices.
### $O(1)$ time, $O(1)$ state random access Brownian motion?
I would like to generate discrete samples $0 = B(0), B(1), \ldots, B(T)$ of a Brownian motion $B : [0,T] \to \mathbb{R}^d$. It is possible to get $O(\log T)$ time random access into a consistent ...