The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
223 views

Integration of independent Brownian motions

I am wondering if the following integral of stochastic Brownian motions has an analytical solution? $$ \int_{0}^{t}e^{\nu \tilde{V}_{\tau} - \frac{1}{2}\nu^{2}\tau}d\tilde{W}_{\tau} $$ where ...
19
votes
0answers
428 views

Time for Langton's ant to cover a “square” torus

Langton's ant is a cellular automaton running as follows: Squares on a plane are colored variously either black or white. We arbitrarily identify one square as the "ant". The ant can travel ...
9
votes
0answers
109 views

Self-avoiding random walks that always turn

I am wondering if the statistics of self-avoiding random lattice-walks on $\mathbb{Z}^2$ that turn left or right at each step (i.e., they cannot continue the direction of the preceding step) have been ...
8
votes
0answers
828 views

Combinatorial proof for the number of lattice paths that return to the axis only at times that are a multiple of 4

Consider lattice paths consisting of $2n$ steps, each of which is either $(1,1)$ or $(1,-1)$. The number of such lattice paths that return to the horizontal axis only at times that are a multiple of ...
7
votes
0answers
122 views

Asymmetric random walk on the line with barriers

The most commonly considered random walk on the line takes one step left or right with equal probability until a barrier is reached (if there are any barriers). More generally, suppose we fix any ...
7
votes
0answers
121 views

Speed on recurrent graphs

Suppose that $G$ is a (locally finite) graph such that the simple random walk on $G$ is recurrent. Does this imply any upper bound on the speed $\mathbb{E}d(X_t,X_0)$ of such random walk?
6
votes
0answers
130 views

How much do the classes of geodesic metrics and Green metrics on a Gromov hyperbolic group differ?

Background Let $G$ be a Gromov hyperbolic group. If $G$ acts properly discontinuously and cocompactly on a proper geodesic metric space $X$, then any bijective identification of $G$ with its orbit ...
5
votes
0answers
148 views

hitting time of a subset

Suppose you have the simple random walk on $L=\mathbb{Z}^n,$ and $A \subset L$ is a subset (in my case, the subset is a union of hyperplanes, so in particular infinite). There is a random variable ...
5
votes
0answers
726 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" ...
5
votes
0answers
235 views

Any approximation algorithms for self-avoiding walks?

I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...
5
votes
0answers
423 views

Compute the expected value of the next step of a sorted random walk

Here's what I'm thinking about. If you have a random walk (move +1 or -1 at each step) of some fixed length, then if you're at the maximum of the walk, the next step you take is -1 with probability 1. ...
4
votes
0answers
187 views

Why is the density function of a sum of many iid random variables (i.e., the Gaussian) self-dual?

In the usual proof of the central limit theorem via characteristic functions, we note that if $X_1, \dots, X_n$ are independent and identically distributed, with probability density function $f(x)$, ...
4
votes
0answers
340 views

Stopping time of two dimensional random walk

Let $U_n=\sum_{i=1}^n X_i,V_n=\sum_{i=1}^n Y_i$, $n\geq 1$, be a two-dimensional random walk with i.i.d. increments $(X_n, Y_n)$, where $X_n, Y_n$ are discrete random variables with joint pmf ...
4
votes
0answers
154 views

Does the concept of connective constant make sense for any tiling of the plane?

First let me define what is the "connective constant" of a two dimensional lattice. Let $c_{n}$ denote the number of $n$ step self-avoiding walks starting from a fixed origin point in the lattice. ...
4
votes
0answers
69 views

Estimates for simple random walks in groups of intermediate growth

I'm looking for references for the rate of escape and return probability for a group of intermediate growth. Let $0<\alpha < 1$. If the volume growth is $\succeq \mathrm{exp}(n^\alpha)$, then ...
4
votes
0answers
398 views

Monotonic properties of harmonic functions on graphs

I have a question concerning monotonic properties of "generalized harmonic functions" on graphs. I am a physicist and I didn't take any separate courses in neither graph theory nor discrete harmonic ...
3
votes
0answers
104 views

Properties of a finite random walk

Consider the simplest random walk - $X_0 = 0$ and from there on (i.i.d), $X_i=X_{i-1}+1$ with probability $p$ or $X_{i-1}-1$ otherwise. Let $Y_N$ be the highest point $X$ have reached on the first ...
3
votes
0answers
85 views

hitting time of the first quadrant for a 2-d random walk

Suppose $(S_n)_{n=1}^{\infty}$ is a simple random walk in $\mathbb{R}^2$. Let $\tau_{(a,b)}$ be the hitting of the first quadrant when $S_0 = (a,b)$. Is there a way to compute or estimate the ...
3
votes
0answers
64 views

Using Crump-Mode-Jagers processes to get logarithmic bound on a random tree height

I am currently pursuing my PhD degree and in my research I came across a family of random trees. I need to prove a logarithmic asymptotic bound for the heights of such trees as their size grows. I ...
3
votes
0answers
180 views

criterion for deciding whether the product of a sequence of Givens rotations can reach the full special orthogonal group

By Givens' rotation $R(1,2;\theta)$ I mean a matrix which has the $$\begin{pmatrix} \hphantom{-}\cos \theta &\sin \theta \cr -\sin \theta & \cos \theta \end{pmatrix}$$ $2 \times 2$ block at ...
2
votes
0answers
58 views

Controlling fluctuations in a Markov chain

For $N>0$, consider the Markov chain $x_n$ on $\{0,1/N,...,1\}$ that moves up by $1/N$ at rate $(c-x_n/2)N$ and down by $1/N$ at rate $(c+x_n/2)N$. As $N\rightarrow\infty$ sample paths approach ...
2
votes
0answers
84 views

1d random walk probability of previous n positions

I have the following question. (May be it is very simple, but I cannot find the answer). Suppose I have a 1d random walk on integer numbers with equal pobabilities of unit step in either direction ...
2
votes
0answers
184 views

$n$-th return of a random walk on $\Bbb Z^d$

Lets define $f_n = P(X_n =0 , X_k \ne 0, k< n)$ the first return distribution of the random walk $X_n$ on $\mathbb{Z}^d$, and lets go ahead and assume that $f_n \approx n^{-(1+\alpha)}$ for some ...
2
votes
0answers
138 views

Reference request for a result on subsets unlikely to be hit by random walks in a group

Suppose we are performing a random walk in a group. More precisely, we have a finite generating set $S$ of a group $G$ and the probability of walking along generator $s$ is given by $\mu(s)$ for some ...
2
votes
0answers
261 views

Cover time for a biased random walk on an 'N'-dimensional integer lattice

Imagine that I have a random walk on an $N$-dimensional integer lattice, $Z^N$, of finite dimensions, $(d_1, ..., d_N)$, where boundaries are fully reflecting and the walker is initialized at some ...
2
votes
0answers
280 views

Self-avoiding Walk with next-nearest neighbors

Background I study polymer physics and am doing experiments testing the model outlined in this paper. Basically, the polymers fall into an integer number of pits, and we create a partition function ...
1
vote
0answers
69 views

Discretization model for Dirac equation in higher dimensions

I'm wondering if there are cases of discretization models (in lattices or graphs) that converge toward the non-linear Dirac equations? While there is a paper on the 2-d and 3-d cases ...
1
vote
0answers
413 views

Random walk on the hypercube

Let $H_N=\{0,1\}^N$ the N-dimensional hypercube. We define the following random walk $X_n$ on $H_N$: start from a point $x \in H_N$ pick at random an integer $k$ in $[1,N-1]$ and exchange $x(k)$ and ...
1
vote
0answers
845 views

asymmetric random walk, hitting time probability

Let's consider an asymmetric Random Walk on $Z$, with transition probabilities $p_{i, i+1}=p$, $~~p_{i, i+1}=q$, $\forall i \in \mathcal{Z}$, $p+q=1$ and $p>q$. I am interested in the probability ...
1
vote
0answers
179 views

A random walk with uniformly distributed steps II

The problem is a improved version of this problem, A random walk with uniformly distributed steps Let us imagine a point on the real axis. At the beginning, it is located at point $O$. Then it will ...
0
votes
0answers
22 views

Is there effective algorithm for finding “minimal discovery time” for large graphs?

Consider a large, probably sparse graph with Markovian random walkers on it. Define discovery time as time to first reach a vertex by random walk from uniform start. Are there effective ways to find ...
0
votes
0answers
362 views

Probability density function of the node positions in a random walk after N time slots

Hello, my question basically is how do I find the probability density function of the position of the nodes in a given area after N discrete time slots when the nodes move following the 2D random walk ...
0
votes
0answers
96 views

Theorem Leads for tied-down random walk

scribd.com/doc/87930409/18/Leads-for-tied-down-random-walk [Theorem 3.7, page 38] Could you explain me the last equality in the proof? I mean this: $$\frac{2[\sqrt{1 - s^2t^2} - ...
0
votes
0answers
244 views

Random Walk in $\mathbb{R}^n$

Have there been papers dealing with random walks in $\mathbb{R}^n$ that are not on the lattice $\mathbb{Z}^n$? Instead of walking in one of the directions possible in $\mathbb{Z}^n$ with probability ...