# Questions tagged [random-walks]

The tag has no usage guidance.

25 questions
Filter by
Sorted by
Tagged with
427 views

### Expected length of a random walk on a line

I am given the following randomized algorithm for SAT, Input: A satisfiable CNF-formula $\varphi$. Output: An assignment $\rho$, such that $\rho \models \varphi$. The algorithm works as follow: ...
102 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 ...
40 views

### $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 ...
48 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, ...
123 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$ ...
140 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 ...
61 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 ...
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 ...
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 ...
115 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 ...
331 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 ...
893 views

### Generating a random path in a grid without deadlock

I want to write an algorithm that takes an $n \times n$ grid and a number $L$, generate a random walk of length $L$ on the grid that doesn't visit the same cell twice. One simple solution would be ...
202 views

### Random Walk on the Integer Line

Suppose we are doing a random walk on the infinite integer line and that we take $2n$ total steps. At every step of this walk, the position of the walker is an integer point on this line. For the next ...
111 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 ...
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 ...
137 views

451 views

### How many random walks to start from each node?

Assume that we are given a real life graph, DBLP network in my case, where degree distribution of nodes follows a power law (many nodes have 1, 2 neighbors, and only a few nodes have hundreds of ...
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.