The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
45 views

N random walkers that hit node v in a graph

Consider a finite, undirected graph G, with uniform edge weights. Assume that there are n number of random walkers that will start at different nodes (lets say n=3, hence the random walkers will start ...
12
votes
0answers
498 views

Random Walk on $\mathbb{R}$ with Uniformly Distributed Steps and “Reflective” Boundary at Origin

A particle lies on the real number line at the origin. For each step taken, the particle moves from its current position a distance (and direction) chosen equi-probably from range $[-1,r]$. However, ...
8
votes
0answers
646 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
115 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
108 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
141 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
641 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
228 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
368 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
76 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
273 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
141 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
66 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
386 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
47 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
167 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
73 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
174 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
136 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
254 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
267 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
57 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
316 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
583 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
170 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
76 views

Modification of a state in a random walk to be partially absorbing after a walker's position is well-approximated by a stationary distribution

Consider a random walk $(X_0, X_1, X_2, ...)$ on the interval $[0, N]$ starting from some position $k$, where $0$ and $N$ are reflecting barriers. The forward $+1$ transition probability is $p$, the ...
0
votes
0answers
295 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
91 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
236 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 ...