The tag has no usage guidance.

learn more… | top users | synonyms

3
votes
0answers
52 views

Do the normal forms for braid groups really conceal information about better than randomly applying the braid relations?

In braid based cryptography, one typically wants to conceal the way a certain braid $b$ has been obtained. One therefore puts $b$ into some normal form. Since every braid has a unique normal form, the ...
0
votes
0answers
27 views

Basic Definition and Notations in RWRE [on hold]

From the definition of Zeitouni's lecture notes on RWRE: $(V, E)$ is a special graph, and $N_v:= \{k \in V: (v,k) \in E\}$ is the neighborhood of $v \in V$. $\Omega = \prod_{v \in V} M_1(N_v)$ ...
0
votes
1answer
74 views

Exact formula for computing n-step transition probability of random walks with self-transitions

Consider a semi-infinite random walks $X_n$, $n=0,1,2,\ldots$, whose state space is a set of consecutive integers and whose one-step transition probabilities are $P_{ij}=\mathrm{Pr}\{X_{n+1}=j|X_n=i\}$...
4
votes
1answer
159 views

Number of walks on integer lattice with self-edge at zero

Consider the graph with vertices $V=\mathbb Z$ and edges $$E=\{(n,n+1):n\in\mathbb Z\}\cup\{(0,0)\},$$ that is, the usual integer lattice with a self-edge at zero. For some fixed parameters $a,b,n\in\...
7
votes
0answers
114 views

Winding number of a random walk on the square lattice before hitting the origin

Let us consider a simple random walk on $\mathbb{Z}^2$ started at $(x,0)$ and killed upon hitting the origin. Define the total winding number $w_x$ around the origin to be the (signed) number of ...
1
vote
0answers
34 views

Expression for Joint-PDF of Langevin equation?

How to derive exact or approximate analytical expression for time-dependent joint-PDF (velocity-coordinate PDF) for Langevin equations of Brownian motion? Langevin equations is: $\dot{x}=v$ $\dot{...
1
vote
0answers
69 views

Diagonal of Green's Function

I am looking to numerically calulate the diagonal of Green's function. I am interested in Green's functions of elliptic PDEs and in those that arise from stochastic processes (discrete and continuous)....
3
votes
1answer
148 views

Range of random walk

I have a random walk on $\mathbb{Z}$ with starting point $0$ and with length $n$ and possible steps to right, left or stay where you are, all with the same probabilities. I am interested in exact ...
4
votes
0answers
192 views

Self-adjusting random walk

Let $X_t$ be a random process such that \begin{eqnarray} X_1 &=& 0\\ X_t &=& X_{t-1} + \left\{\begin{array}{ll} A_t, & X_{t-1} \geq 0\\ B_t, & X_{t-1} < 0 \end{array}\...
3
votes
2answers
163 views

The necessary sufficient condition for recurrence of a Markovian random walk

Suppose $\sigma_{1},\sigma_{2},...$are i.i.d random variables.$S_{0}=0$. Define $S_{n}=S_{0}+\sum_{i=1}^{n}\sigma_{i}$, then ${S_{n}}$ is a Markovian random walk. I want to figure out the necessary ...
6
votes
1answer
325 views

Liouville property - a very basic question

Let $\mathbb{F}_2$ be the free group on two generators. By a result of Kaimanovich and Vershik, for each measure $\mu$ on $\mathbb{F}_2$ such that the support of $\mu$ generates $\mathbb{F}_2$, we ...
2
votes
0answers
70 views

Question about martin boundaries of random walks induced on transient subgroups

Suppose $\Gamma$ is a discrete, finitely generated, non-amenable group, and consider a random walk given by a measure $\mu$. Assume the measure is symmetric, finitely generated, and the support of $\...
4
votes
0answers
66 views

Most visited vertex in a random walk with place dependent drift

Consider the following Markov chain on $\mathbb{Z}$: $$ P(x,x+1)=1-P(x,x-1)=\frac{1}{2}+e^{-|x|}\cdot \mathbf{1}_{\{x\neq 0\}} $$ Do there exist constants $c,C>0$ such that $$ c\cdot P^t(z,z) \...
1
vote
1answer
60 views

Choose uniformly from fixed-length paths in $[0,n]\cap\mathbb{Z}$ with fixed start and end

Let $X_k$ be a symmetric (discrete time) random walk on $\mathbb{Z}$ and let $m,n\in\mathbb{N}$. I want to chose uniformly from the paths of $X_k$, which start at $0$ stay in $[0,n]\cap\mathbb{Z}$ ...
0
votes
0answers
19 views

Large-$t$ expected distance from origin in non-trapping, self-avoiding random walks

Consider two variants on Self-(vertex-)Avoiding Random Walks on $\Bbb{Z}^2$: (A) "Legal" steps consist of any step not ending on a vertex previously visited, and the probabilities of each of the 1, 2,...
3
votes
1answer
179 views

Expected visits to the origin by a symmetric random walk on the integers

Consider the first $2n$ steps of a simple random walk on the integers, starting at the origin. A simple binomial argument shows that regardless of $n$, the origin gets visited the most (in expectation)...
7
votes
2answers
200 views

Robustly recurrent random walk

Is there a probability measure $\mu$ on $\mathbb{Z}$ such that, for every $0 < \alpha \leq 1$ and every finitely supported (¹) probability measure $\nu$ on $\mathbb{Z}$, it holds that the $\alpha \...
1
vote
0answers
46 views

Expected number of forward jumps to reach a given quantile of a rv [closed]

I'm a noob in randomized algorithm and ran into a problem(definitely not home work. I'm doing a self study out of my interest with help of my friends. I'm pursuing research career in a machine ...
2
votes
1answer
101 views

Random Walk 2D with dependent weights [closed]

I have spent a lot of time trying to solve this problem but have had no luck so far! Any help would be highly appreciated! Suppose I have a 3x3 grid as shown below. (3,1) (3,2) (3,3) (2,1) (2,2) (...
0
votes
0answers
26 views

Unidirectional continuous path discrete time random walk

Is there any material available to study on unidirectional continuous path discrete time random walk on a line interval. To say "unidirectional continuous path discrete time random walk on a line ...
3
votes
1answer
185 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
1answer
126 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 ...
0
votes
1answer
86 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) \...
0
votes
1answer
163 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 ...
2
votes
1answer
101 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 ...
1
vote
1answer
165 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 ...
9
votes
2answers
349 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 ...
4
votes
4answers
423 views

Order of magnitude 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
169 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
70 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 ...
2
votes
2answers
187 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
1answer
131 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 $1$...
1
vote
2answers
73 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 ...
8
votes
2answers
270 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 ...
5
votes
2answers
177 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)$. ...
0
votes
1answer
140 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 ...
4
votes
3answers
303 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)$, $m_n=\min(S_1,S_2,\...
1
vote
1answer
128 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 ...
9
votes
1answer
359 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 [...
3
votes
0answers
68 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 G$)?...
2
votes
1answer
191 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
163 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
75 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$ $...
0
votes
0answers
75 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
59 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 (0,\...
1
vote
1answer
181 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)$ known?...
1
vote
1answer
135 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
185 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
123 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
240 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 ...