The tag has no usage guidance.

learn more… | top users | synonyms

2
votes
1answer
81 views

How many times does a simple symmetric random walk of length n return to the origin?

Consider the simple symmetric random walk on the integers starting from the origin of length $n$. More precisely, I will denote an $n$ step random walk $w$ as $$ w:= \omega_0 \omega_1 \ldots ...
0
votes
0answers
44 views

continuous vs discrete random walk [on hold]

For 1D random walk in discrete case the probability $P_N(X)$ of finding walker at position $X$ after $N$ steps has a binomial distribution, moreover when $N+X$ is odd then probability is 0. Let's ...
0
votes
1answer
105 views

Transition probabilities for the symmetric random walk on the integers

I found that most references for the symmetric random walk on the integers are for the discrete time case, i.e. the ones that gives us explicit transition probabilities. Now, I am looking at a random ...
-1
votes
0answers
8 views

Hypothesis testing for independent and non-identical distribution [migrated]

I want to apply the hypothesis for my problem. According to A. Wald regarding sequential hypothesis, he used independent and identically distributed (iid) observations or samples but in my case my ...
0
votes
1answer
83 views

Weak convergence of process

Background: I am trying to compute the weak limit of the following model from mathematical biology that is supposed to exist: Let $$L(f)(\eta)= \sum_{x \in \mathbb{Z}}\frac{1}{2}\left(1_{\eta(x+1) ...
-1
votes
1answer
78 views

Mixing time of lazy random walk on the directed cycle $C_n$

Briefly: A hint (if this is easy), reference or derivation would be of great help. The question Let $C_n$ be the directed cycle with loops in each of its $n$ vertices, and consider the random walk ...
0
votes
0answers
133 views

Shortest distance on a combinatorial chess board

Consider a random $n\times n$ combinatorial $0/1$ square matrix over field $\Bbb F$ of rank $r$ with every row distinct and every column distinct as a chess board. Definition of combinatorial ...
11
votes
1answer
466 views

Distribution of maximum of random walk conditioned to stay positive

I have an $n$ step random walk which starts at zero $X_0 = 0 = S_0$ where the steps $X_i$ are independent uniform random variates in $[-1,1]$, but the walk is conditioned on the hypothesis that it ...
2
votes
1answer
93 views

Resources to study self-avoiding walks

What would the best resources be for someone who wants to study self-avoiding walks from a mathematical standpoint? I'm talking about seminal/important papers, good textbooks perhaps, things of that ...
5
votes
1answer
451 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
1answer
141 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 ...
1
vote
1answer
162 views

Does walk on $Z^d$ with steps $(\pm 1,\pm1,\ldots,\pm 1)$ return to origin?

If the steps are iid uniform as in the title, is the return probability known? Is it positive? Answers, comments, references welcome. Clearly each of these steps is not equivalent to $d$ steps of type ...
0
votes
1answer
127 views

Discrete random walk with uniformly distributed transition p, set initially

I've been working on a discrete version of the "unreliable friend" distribution. It would seem that what I've come up with is equivalent to the following random walk: Choose $p$ from $U(0,1)$ Start ...
9
votes
2answers
311 views

Adaptive version of the Azuma–Hoeffding inequality

The Azuma inequality states that if we have a martingale $X_1,\ldots,X_N$ that satisfies a bounded difference condition: $$|X_k - X_{k-1}| \leq c_k$$ Then: $$\Pr\left[X_N - X_0 \geq \sqrt{2\sum_kc_k^2 ...
1
vote
1answer
1k 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 ...
3
votes
2answers
179 views

Distribution of the hitting time of a random walk

Consider the random walk on $\mathbb R$ with $X_0 = a >0$ and $$X_{n+1} = X_n + U_n,$$ where $U_0, U_1, U_2,\ldots $ is an i.i.d. sequence of uniform random numbers in $[-1,1]$. How does the ...
4
votes
1answer
156 views

Random walk with continuously distributed steps on [-1,1]

A simple random walk $S_n = X_1 +\cdots +X_n$, where $P(X_i = 1) = p \not = 0.5$ and $P(X_i=-1)= q \triangleq 1-p$, admits the following probability $$P(S_n \textrm{ reaches } a \textrm{ before} -b) ...
3
votes
0answers
57 views

What is the influence of unreliable comparisons on the results of sorting

Considering sorting algorithms based solely on binary comparisons of the elements to be sorted(algorithms such as insertion sort, selection sort, quicksort, and so on), what problems do we face when ...
1
vote
1answer
421 views

The probability that a 2d continuous time random walk avoids the origin

I am trying to find a reference of a proof of a continuous time version of a result of Dvoretzky and Erdos from their paper "Some problems on random walk in space" that says the probability ...
2
votes
2answers
168 views

Bound that random walk stays within with constant probability?

For one-dimensional random walk, it is well-known that if the walk goes for $n$ steps, with constant probability it ends within $\pm\sqrt{n}$. What is the bound, in terms of $n$, such that if the ...
1
vote
2answers
72 views

Position likelihood in a 2D graph [closed]

I am looking for general principles or specific answers to this generic example. Assume a 2d grid with no boundaries and a roving dot (ant/drunk guy/particle) that is initially located at some ...
1
vote
1answer
119 views

Two types of random walkers on square lattice

Consider a two dimensional square lattice ($n$ by $n$), which is our space $S$ (each point labelled by an index $1\to n^2$), containing two types of particles, distinguished here by either an index ...
7
votes
2answers
254 views

Distribution of $\max_{n \ge 0} S_n$, random walk

Say we have a random walk that is a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the ...
1
vote
1answer
118 views

A deterministic and explicitly described walk which is like random ones

Consider a sequence $(X_i)_{i = 1}^{\infty}$ which every $X_i$ is $-1$, $0$ or $+1$ and lets define $Y_n = X_1+ \cdots + X_n$. We say the sequence $(X_i)_{i = 1}^{\infty}$ a Good Sequence if $Y_n \neq ...
5
votes
2answers
162 views

Recurrence of Poisson binomial distributed random walk

Let $X_n$ be the outcome of a Bernoulli trial where the probability of getting 1 is $p_n$ and the probability of getting 0 is $1-p_n$, and let $S_n = \sum_{i=1}^n \left(X_i - \textrm{E} X_i \right)$. ...
8
votes
1answer
396 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 ...
1
vote
0answers
35 views

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

Consider a large, probably sparse graph with Markovian random walkers on it. Define the discovery time as the expected time to first reach a vertex by random walk from a uniform start. Are there ...
4
votes
3answers
275 views

Maximum difference between heads and tails in absolute value

I toss a fair coin $n$ times. Some notation: $S_i=$ difference between #heads and #number of tails after the first $i$ tosses, $1\leq i\leq n$. $M_n=\max(S_1,S_2,\dots,S_n)$, ...
9
votes
1answer
338 views

Lattice random walk under gravity

Suppose a random walk on $\mathbb{Z}^2$ takes a step left or right with probability $\frac{1}{4}$, but up with probability $\frac{1}{2} p$ and down with probability $\frac{1}{2} (1-p)$, where $p \in ...
5
votes
1answer
339 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 ...
1
vote
2answers
411 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 ...
1
vote
1answer
165 views

Arc Sine law for Random Walk conditioned to non-absorption or not?

Let $S_n$ be simple symmetric Random walk on the integers in $[-N,N]$ with states $N$ and $-N$ absorbing. Let $\tau$ be the time to absorption when $S_0 = 0$. Is the $E(S^{2}_{n}| \tau \geq n)$ ...
2
votes
1answer
167 views

Gradient of Probability Distribution

Given a random walk on a lattice $L$ (not necessarily centered - we allow $E[X_i] \neq 0$ for the i.i.d. increments $X_i$), let $p_t(x)$ denote the probability measure of state $x \in L$ after $t$ ...
3
votes
0answers
66 views

Is the family of probabilities generated by a random walk on a finitely generated amenable group asymptotically invariant?

Is the family of probabilities $\mu^n$ (convolution) generated by a random walk $\mu$ on a finitely generated amenable group $G$ asymptotically invariant ($\|g\mu^n-\mu\|_{L^1}\to 0$ for any $g\in ...
3
votes
0answers
161 views

Uniform sub-linearity of sub-additive functions on groups

Suppose $G$ is a finitely generated group and suppose $f: G \to \mathbb{R}$ is subadditive function, that is: $f(g_1\circ g_2) \leq f(g_1) + f(g_2)$. One example of such $f$ is the word length in some ...
2
votes
1answer
71 views

More precise statement about lower bounds on the cover time of general graphs

Uriel Feige has shown in 1995 in his paper "A Tight Lower Bound on the Cover Time for Random Walks on Graphs", the following result: For any graph $G$ on $n$ vertices, and any starting vertex $u$ ...
7
votes
5answers
765 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 ...
0
votes
0answers
71 views

Markov chains on a polyhedron

A modification of a question from Gerard Letac (1976): A m-sided q-adjacent-faced polyhedron has one of its faces "up." Each round, the polyhedron rolls so that any of the adjacent faces is now up. ...
2
votes
0answers
48 views

probabilistic interpretation of a finite difference scheme

Let me start with some simple background. Consider the heat equation : $ \frac{\partial p}{ \partial t} = \frac{1}{2} \frac{\partial^2 p}{\partial y^2} \quad \mbox{in} \quad \mathbb{R}\times ...
1
vote
0answers
100 views

Scaling of First-passage times for Random Walk on integer lattices

Consider simple symmetric random walk $S_{n} = (S_{n}^{(1)},\dots, S_{n}^{(d)})$ on the d-dimensional integer lattice with starting point the origin. Let $\tau_{N}$ be the first time $S_{n}$ exits ...
2
votes
1answer
172 views

Random walk on a sphere along latitude-longitude grid

Suppose a sphere is partitioned by a latitude-longitude grid, with grid quadrilaterals $\Delta \times \Delta$. All grid nodes have degree $4$, while the North & South poles have degree $2 \pi / ...
1
vote
0answers
111 views

Horizontal vs Vertical sides Exit from a Rectangle for simple symmetric Random Walk on $\textbf{Z}^{2}$

Consider simple symmetric random walk, $X_{n} = (X_{n}^{(1)}, X_{n}^{(2)})$ with $X_0= (0,0)$, on the 2 dimensional integer lattice, $\textbf{Z}^{2}$. Let $T_{M}, T_{N}$ be the smallest $n$ such ...
4
votes
2answers
228 views

First collision time of $n$ random walkers on a cycle

My question is somehow related to the one here First Collision Time for k Random Walkers on a Torus but, unfortunately, the answer does not cover my concern. My problem is: consider $n$ walkers on ...
0
votes
1answer
311 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 ...
3
votes
1answer
124 views

General ballot theorem

I am looking for a version of the Ballot Theorem for general step distributions. Specifically, let $X_1,X_2,\ldots$ be i.i.d. real random variables with some distribution. Let $S_n = S_1 + \cdots + ...
6
votes
2answers
239 views

A variant of random walk

Standard random walk assumes a sequence of iid RVs $\{X_i\}_{i\geq 0}$ and studied the distribution of $S_n=\sum_{i=0}^n X_i$. Here, I am wondering whether there is some work on $T_n=\sum_{i=0}^n ...
10
votes
0answers
186 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 ...
2
votes
1answer
213 views

Hitting probabilities for conditioned oriented random walk monotonic?

Consider an oriented random walk on $\mathbb Z^2$ (i.e. only steps $\rightarrow$ and $\uparrow$ with equal probability.) Say we let the walk go $2m$ steps then start guessing sites at distance $2m$ ...
17
votes
2answers
842 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
2answers
182 views

Tail sigma-algebra of a branching random walk

I am looking for any known results about the tail sigma-algebra of a branching random walk. To be specific, let $T$ be the nodes of an infinite binary tree rooted at $r \in T$. Let $\{X_t\})_{t \in ...