# Tag Info

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