Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [random-walks]

The tag has no usage guidance.

24 questions
Filter by
Sorted by
Tagged with
75 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 ...
43 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, ...
110 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 ...
49 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 ...
42 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 ...
102 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 ...
780 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 ...
305 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 ...
172 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 ...
108 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 ...