# Tagged Questions

The tag has no usage guidance.

72 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\}$...
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)$ ...
50 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 ...
150 views

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 ...
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)....
192 views

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}\...
105 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 (...
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 ...
70 views

66 views

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 ...
86 views

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 ...
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) =...
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 ...
470 views

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)$. ...
438 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 polygon ...
37 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 ...
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,\... 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 [...
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 $N$...