The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
0answers
61 views

Diameter of $n$-unit-vector closed scribble

Suppose one creates a random, closed, likely self-crossing polygon from $n$ unit-length vectors arranged head-to-tail, randomly oriented except for the requirement that their sum is zero (so the ...
2
votes
0answers
53 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 ...
8
votes
1answer
110 views

Random walk on a Penrose tiling

Pólya proved that a random walk on $\mathbb{Z}^2$ almost surely returns to the origin, or, equivalently, returns to the origin infinitely often. It was subsequently established that in $\mathbb{Z}^3$, ...
14
votes
2answers
710 views

Randomly walking a leashed dog

Let a human $h(t)$ random walk on $\mathbb{Z}^2$ by taking a unit-length step at every time step $t$. A dog $d(t)$ on a leash of length $\lambda$ follows $h(t)$, also taking a unit-length step at ...
11
votes
1answer
170 views

Wander distance of self-avoiding walk that backs out of culs-de-sac

Suppose a self-avoiding walk on $\mathbb{Z}^2$, with random steps each one unit long, backs out of culs-de-sac, but retaining the lattice points on which it stepped marked as unavailable for future ...
4
votes
2answers
564 views

Do Random Walks on the Hexagonal Lattice have a limit?

For every positive integer $n$, consider a regular hexagon $\mathrm{H}_n$ such that the distance of each vertex from the center is $\frac{1}{\sqrt{n}}$. That in turn induces a tiling of ...
4
votes
0answers
137 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. ...
6
votes
5answers
369 views

Reference requested: Random walk on groups

I am looking for a good reference to learn about random walks on groups (either finite groups or Lie groups). Ideally, I would like a reference for general theory of random walks on groups that is ...
4
votes
1answer
97 views

Connection between degree of growth and return probabilities of random walks on Lie groups

Let $G$ be a finitely generated group of polynomial growth, let $\mu$ be a non-degenerate symmetric probability measure with finite support on $G$, and let $d$ be the degree of growth of $G$. ...
6
votes
0answers
96 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 ...
3
votes
2answers
181 views

Nonmonotonicity of expected distance of a random walk

What's the simplest example of a reversible random walk $X_n$ on an infinite vertex-transitive graph such that the expected distance from the origin is not increasing, i.e. there exists $n$ such that: ...
8
votes
3answers
335 views

Hitting time for two out of three random walk particles

I'm imagining a simple random walk on $\mathbb{Z}$ with three independent particles (maybe add laziness so they don't jump over each other). Suppose the particles are initially placed at, say, $-10$, ...
8
votes
2answers
151 views

Area covered by Brownian motion of 2D disc

I would like to know the expected value for the area covered by a disc of radius $R$ whose center undergoes Brownian motion (diffusion). Specifically, let $\mathbf{X}_t$ represent a two-dimensional ...
0
votes
0answers
60 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 ...
5
votes
2answers
525 views

Random walk by simplex vertices

I apologize if this question is well-known, but I was unable to find it mentioned anywhere. There exists a bug which moves around in $r$-space. The bug begins at the origin of this $r$-space. If the ...
3
votes
0answers
42 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 ...
7
votes
0answers
114 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?
2
votes
1answer
302 views

Expectation of Maximum of Uniform Multinomial Distribution

Suppose we have a uniform multinomial distribution with $k$ buckets, i.e. we put $n$ items uniformly at random in $k$ buckets leading to $n_1, \dots, n_k$ items in each bucket respectively. Let $m = ...
1
vote
1answer
119 views

Quadratic variation for discrete Martingale

Is there any analogue of continuous martingale quadratic variation for the discrete case? If so, are there any theorems which characterize simple random walk using quadratic variation - similar to ...
5
votes
1answer
152 views

Width of a random convex polygon

Consider a planar (2D) random walk comprised of N steps. Consider the minimum convex polygon enclosing the N points visited by the random walker. Assume the definition of the width of a convex ...
3
votes
1answer
408 views

Random walk in a circle

Suppose we have a circle of radius $R$ centered in the origin of a $x,y$ cartesian reference frame. A particle starting from the center of the circle is moving with a speed given by: ...
0
votes
1answer
84 views

Joint law for number of visits in transient simple random walk

Consider a simple $1$-dimensional random walk $X_n$. Let $p$ and $q$ (with $p+q=1$) be the probability of transitions from $n$ to $n+1$ and from $n$ to $n-1$ respectively, and suppose that $p>q$ ...
4
votes
0answers
63 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 ...
3
votes
2answers
171 views

Methods to approximate the betweenness centrality on large networks

To calculate the between centrality wiki def: $g(v) = \sum_{s\neq v \neq t} \frac{\sigma_{st}(v)}{\sigma_{st}}$ of a node in a graph/network;$\sigma_{st}$ is the ...
5
votes
1answer
173 views

Random walk with positive uniformly distributed steps

Let $U_1,U_2,\ldots$ be iid random variables distributed uniformly on $[0,1]$. I am interested in the random walk $X_i = \sum_{j \leq i} U_j$. In particular, What is the expected number of points ...
1
vote
0answers
54 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 ...
4
votes
2answers
152 views

Estimate size of graph by taking random walks

Let $G$ be a connected, finite graph and let $v_0$ be a vertex of $G$. I'm interested in methods of estimating the number of vertices in $G$, based on local exploration only. What I have in mind is: ...
6
votes
1answer
345 views

Random walk over a function

Let $\{X_n\}_{n\geq 0}$ be a random walk. Let us assume that $\mathbb{E}X_1 =0$ and $\mathbb{E}X_1^2=1$. Let also $\mathbb{E}\exp(c|X_1|)<+\infty$ for some $c>0$ and $X_1$ has a law with ...
6
votes
1answer
278 views

Twisted random walks

Suppose the points of two random walks in $\mathbb{R}^2$ are given the step number (or time) as a third coordinate, so that they become paths in $\mathbb{R}^3$. Here are several pairs of walks of ...
5
votes
1answer
446 views

random walk and Brownian motion on Riemannian manifold

As we know, the random walk on $\mathbb{Z}/n$ will converge(in some sense) to the Brownian motion on $\mathbb{R}$ when $n\to\infty$. I would like to know is there some higher dimensional analogy ...
3
votes
1answer
219 views

Speed of random walks in groups

I've seen some estimates for the decay in $d$ of the probability a SRW makes a distance $d$ in time $n$, but is there any reference for the "speed" of a random walk in a group? I'm interested mostly ...
5
votes
1answer
265 views

Random path in a graph

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given ...
11
votes
0answers
488 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, ...
6
votes
1answer
259 views

The number of lattice paths below y=n/m x for gcd(m,n) = 1

The motivation of my question is the recent preprent of Armstrong, Rhoades and Williams http://arxiv.org/abs/1305.7286 on rational Catalan combinatorics. An important starting point of this paper is ...
11
votes
3answers
401 views

An “inchworm-like” random walk on an integer interval

Imagine I place $k$ stones on an infinite one-dimensional integer interval $Z$ s.t. no stone is more than some distance $d$ from any other stone. For example, if $d=1$ and $k = 5$, we might place the ...
1
vote
2answers
190 views

Random walk on the hypercube

Consider the hypercube $Q_4$. I would like to know how to compute the number of steps of a random walk in this graph such that the probability to be at a vertex is a given number $x$. I think I just ...
1
vote
1answer
155 views

Fundamental inequality of entropy in random walks

I'm looking for a reference for an inequality related to the "fundamental inequality" about entropy and rate of escape of random walks (on the Cayley graph of a group). Namely, $\textbf{Question}$: ...
4
votes
1answer
257 views

Probabilities of a random walk exiting a set

Let $F$ be a finite connected set in a graph (soon to be the Cayley graph of a group) and $\mathrm{Ex}_x^F$ be the function on the vertices in $F^c$ which are neighbour to vertices in $F$ defined as ...
0
votes
0answers
92 views

controlled random walk

consider a controlled random walk in 2 dimensions, with state vector $X = x_{1},x_{2}$. Whenever $x_{1}>x_{2}$ a control is applied with a drift and variance such that drift of $x_{1}$ is more than ...
5
votes
1answer
182 views

Memory of Uniformly Random Dyck Paths

Let $D$ be the set of all Dyck paths on square grid of size $n\times n$. For any particular Dyck path, let $S(t)=X_1+X_2+\ldots +X_t$ store the path, where $X_i=\pm 1$. Being a Dyck path, we have ...
1
vote
1answer
469 views

Hitting time probability in a Random Walk with possibility to die.

A Random Walker can move of one unit to the right with probability $p$, to the left with probability $q$ and it can jump again to the starting point with probability $r$ and die. Naturally $p+q+r=1$. ...
5
votes
1answer
231 views

The minimal norm of a shifted stochastic matrix

Hello, Given a row-stochastic matrix $M$ with singular values $\sigma_{1}\geq\ldots\geq\sigma_{n}$, I am looking for an upper bound on the expression: $\min_{\alpha}\parallel M- ...
1
vote
0answers
266 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
522 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 ...
0
votes
0answers
287 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 ...
1
vote
1answer
67 views

Spanning subgaph with trivial Poisson boundaries

Assume $\Gamma$ is the Cayley graph of an amenable$^{*}$ group and that the simple random walk has non-trivial Poisson boundary$^{**}$. Is there a spanning connected subgraph $\Gamma'$ of some ...
1
vote
1answer
193 views

Stationary distribution for directed graph

I want to implement the algorithm of graph partitioning of sparse directed graph. In this algorithm after computing the transition matrix ,we should compute the stationary distribution of the random ...
12
votes
3answers
456 views

Estimate on currents in Cayley graphs

Take a Cayley graph $\Gamma$ (thought of as an electrical network with all edges having equal resistance) and break one edge $e$ and put a battery there. (Assume the graph has only one end* so that ...
27
votes
1answer
858 views

Prime Number Races in 2 Dimensions

Is the mapping $$f: \ \mathbb{N} \rightarrow \mathbb{Z}[i], \ \ \ n \ \mapsto \sum_{2 < p \leq n \ {\rm prime}} e^{\frac{p-1}{4} \pi i}$$ surjective? In 1999, when I was an undergraduate student, ...
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} - ...