Tag Info

Hot answers tagged

8

The location density after $n$ moves is $$ \frac1{\sqrt{n}}f\left(\frac{x}{\sqrt{n}}\right) $$ Given that we are currently at $x$, the probability that we will cross the origin on the next move is $$ \int_{t\ge|x|}f(t)\,\mathrm{d}t $$ So the probability that on move $n+1$, we cross the origin is $$ ...


4

Let $Q(s) = \frac{1-\tau(s)}{1-s}$. It is not hard to check that the coefficient $q_n$ of $s^n$ in $Q(s)$ is $$ q_n = 1-\sum_{m=0}^n \tau_m = \Pr[\mathfrak{T}_1 > n] \sim \frac{1}{\sqrt{\pi}} e^{-c} \frac{1}{\sqrt{n}}, $$ using Theorem 1. Clearly $q_n$ is monotonic. Taking $p = 1/2$ and using $\Gamma(1/2) = \sqrt{\pi}$, this shows that $$ q_n \sim ...


2

I believe you want sequence A010566 at OEIS; there are many references. There are many related sequences as well; the general search term you want is self-avoiding [closed] random walk.


2

The probability of $X=t$ ($t\geq 0$) equals the coefficient of $x^t$ in $$\left(\frac{1}{n}x+\frac{1}{n}x^{-1}+\frac{n-2}{n}\right)^\ell=\frac{1}{n^\ell x^\ell}(x^2+(n-2)x+1)^\ell.$$ This coefficient is $$\frac{1}{n^\ell}\sum_{j=0}^{[(\ell+t)/2]}\binom{\ell}{j}\binom{\ell-j}{\ell+t-2j}(n-2)^{\ell+t-2j}.$$


2

You can obviously estimate this probability with Stirling's approximation, but you said you want to use the Central limit theorem. Unfortunately, you cannot do that! Let $S_n$ be the sum of $n$ i.i.d. random variables $(X_k)$, such that $\mathbb{P} (X_1 = 1) = \mathbb{P} (X_1 = -1) = 1/2$ - here, $n=10000$. What you want to estimate is: $$\mathbb{P} ...


2

As noted above, we can also use the De Moivre-Laplace theorem to approximate the central term of the binomial. This is a special case of the lattice form of the central limit theorem (Papoulis 8-5) which is obtained simply by substitution of the pmf for the binomial distribution into the normal pdf sampled at the points on which the probabilities must fall. ...


2

You have $n$ choices of starting node. You then take $k-1$ steps, and at each step you have a choice of $r$ different neighboring nodes. Thus, the number of walks is $nr^{k-1}$.


2

From the get-go we should be able to tell the equation (2) is incorrect, since it equals $$\left(\int_{-\infty}^\infty p(x_1)dx_1\right)\cdots\left(\int_{-\infty}^\infty p(x_{n-2})dx_{n-2}\right)\int_{-\infty}^\infty p(x_{n-1})p(x-x_{n-1})dx_{n-1} \tag{2-bad}$$ which is $1\cdots 1\cdot P_2(x)$ instead of the $P_n(x)$ it's supposed to be. The correct ...


1

We shall consider Bernoulli random variables $X_i$ that take on the value $1$ with probability 1/2 corresponding to a step to the right at step i, and the value $0$ with probability 1/2 corresponding to a step to the left at step i. Define $$Y = \sum_{i=1}^{1000}X_i.$$ We wish to approximate $$P(Y = 5000) = {10000 \choose 5000}\frac{1}{2^{10000}}$$ the ...


1

You can identify the following regimes as $n$ and $\ell$ grow large together: (1) If $\ell/n\to0$, then the expected number of jumps goes to $0$, and the probability of ending at $0$ goes to $1$. (2) If $\ell/n$ converges to a constant, say $c$, then the number of jumps converges to a Poisson($2c$) random variable. More precisely, the joint distribution of ...


1

Note that the variance of $X_{\ell}$ is $$ E[X_{\ell}^2]=E\left[\left(\sum_{i=1}^{\ell}x_i\right)^2\right]=\sum_{i=1}^{\ell}E[x_i^2]=\sum_{i=1}^{\ell}\frac{1}{n}=\frac{\ell}{n}, $$ so assuming a Gaussian form for large $\ell$ (as expected from the central limit theorem) gives $$ P[X_{\ell}=0]\sim\sqrt{\frac{n}{2\pi\ell}} $$ as $\ell/n\rightarrow\infty$.


1

There is a theoretical answer to this, which appears in the derivation of the heat equation from random walks or from Brownian motion. The main result is that if you have a Brownian motion $\sigma B^x_t$ which starts at $x$, then $u(t,x)=E[\sigma B^x_t]$ solves the heat equation $u_t = \frac{\sigma}{2} u_{xx}$. So your diffusion coefficient should be ...


1

\begin{align} & \Pr\left(\sqrt{X^2+Y^2}\le w\right) \\[10pt] = {} & \iint\limits_{\begin{smallmatrix} \text{disk of} \\[2pt] \text{radius } w\end{smallmatrix}} \frac 1 {2\pi} e^{-(x^2+y^2)/2} \,d(x,y) \\[10pt] = {} & \int_0^{2\pi} \int_0^w \frac 1 {2\pi} e^{-r^2/2} \Big( r\,dr\,d\theta\Big) \\[10pt] = {} & 2\pi \frac 1 {2\pi} \int_0^w ...



Only top voted, non community-wiki answers of a minimum length are eligible