Skip to main content
deleted 1 character in body
Source Link
Yuval Peres
  • 14.2k
  • 1
  • 28
  • 49

Let $\tau_k$ denotesdenote the number of steps for discrete time simple RW on the integers (started at 0) to exit the interval $[-k,k]$. Let $\gamma:=\cos(\frac{\pi}{2k+2})$ so that $\lambda=1-\gamma$. The formula in [1] page 243, line -5, gives (bounding the alternating series there by twice the first term and using $\cot(x) \le 1/\sin(x) \le \pi/(2x)$ for $x\in[0,\pi/2]$ ) that $$P[\tau_k>n] \le 8\gamma^n \,.$$ The estimate for continuous time RW follows: $$P[T_k>q] \le \sum_n P[{\rm Poisson}(q)=n] \cdot P[\tau_k>n] \,$$ whence $$P[T_k>q] \le \sum_n \frac{q^n e^{-q}}{n!}\cdot 8\gamma^n =8e^{q\gamma-q}=8e^{-q\lambda}\,.$$

[1] Spitzer, Frank. Principles of random walk. GTM Vol. 34. Second edition, Springer.

Let $\tau_k$ denotes the number of steps for discrete time simple RW on the integers (started at 0) to exit the interval $[-k,k]$. Let $\gamma:=\cos(\frac{\pi}{2k+2})$ so that $\lambda=1-\gamma$. The formula in [1] page 243, line -5, gives (bounding the alternating series there by twice the first term and using $\cot(x) \le 1/\sin(x) \le \pi/(2x)$ for $x\in[0,\pi/2]$ ) that $$P[\tau_k>n] \le 8\gamma^n \,.$$ The estimate for continuous time RW follows: $$P[T_k>q] \le \sum_n P[{\rm Poisson}(q)=n] \cdot P[\tau_k>n] \,$$ whence $$P[T_k>q] \le \sum_n \frac{q^n e^{-q}}{n!}\cdot 8\gamma^n =8e^{q\gamma-q}=8e^{-q\lambda}\,.$$

[1] Spitzer, Frank. Principles of random walk. GTM Vol. 34. Second edition, Springer.

Let $\tau_k$ denote the number of steps for discrete time simple RW on the integers (started at 0) to exit the interval $[-k,k]$. Let $\gamma:=\cos(\frac{\pi}{2k+2})$ so that $\lambda=1-\gamma$. The formula in [1] page 243, line -5, gives (bounding the alternating series there by twice the first term and using $\cot(x) \le 1/\sin(x) \le \pi/(2x)$ for $x\in[0,\pi/2]$ ) that $$P[\tau_k>n] \le 8\gamma^n \,.$$ The estimate for continuous time RW follows: $$P[T_k>q] \le \sum_n P[{\rm Poisson}(q)=n] \cdot P[\tau_k>n] \,$$ whence $$P[T_k>q] \le \sum_n \frac{q^n e^{-q}}{n!}\cdot 8\gamma^n =8e^{q\gamma-q}=8e^{-q\lambda}\,.$$

[1] Spitzer, Frank. Principles of random walk. GTM Vol. 34. Second edition, Springer.

added 572 characters in body
Source Link
Yuval Peres
  • 14.2k
  • 1
  • 28
  • 49

You can find such estimatesLet $\tau_k$ denotes the number of steps for discrete time simple RW in Feller oron the integers (started at 0) to exit the interval $[-k,k]$. Let $\gamma:=\cos(\frac{\pi}{2k+2})$ so that $\lambda=1-\gamma$. The formula in Karlin[1] page 243, line -5, gives (bounding the alternating series there by twice the first term and Taylor. Theusing $\cot(x) \le 1/\sin(x) \le \pi/(2x)$ for $x\in[0,\pi/2]$ ) that $$P[\tau_k>n] \le 8\gamma^n \,.$$ The estimate for continuous time RW follows using the tail: $$P[T_k>q] \le \sum_n P[{\rm Poisson}(q)=n] \cdot P[\tau_k>n] \,$$ whence $$P[T_k>q] \le \sum_n \frac{q^n e^{-q}}{n!}\cdot 8\gamma^n =8e^{q\gamma-q}=8e^{-q\lambda}\,.$$

[1] Spitzer, Frank. Principles of a Poisson variablerandom walk. GTM Vol. 34. Second edition, Springer.

You can find such estimates for discrete time RW in Feller or in Karlin and Taylor. The estimate for continuous time RW follows using the tail of a Poisson variable

Let $\tau_k$ denotes the number of steps for discrete time simple RW on the integers (started at 0) to exit the interval $[-k,k]$. Let $\gamma:=\cos(\frac{\pi}{2k+2})$ so that $\lambda=1-\gamma$. The formula in [1] page 243, line -5, gives (bounding the alternating series there by twice the first term and using $\cot(x) \le 1/\sin(x) \le \pi/(2x)$ for $x\in[0,\pi/2]$ ) that $$P[\tau_k>n] \le 8\gamma^n \,.$$ The estimate for continuous time RW follows: $$P[T_k>q] \le \sum_n P[{\rm Poisson}(q)=n] \cdot P[\tau_k>n] \,$$ whence $$P[T_k>q] \le \sum_n \frac{q^n e^{-q}}{n!}\cdot 8\gamma^n =8e^{q\gamma-q}=8e^{-q\lambda}\,.$$

[1] Spitzer, Frank. Principles of random walk. GTM Vol. 34. Second edition, Springer.

Source Link
Yuval Peres
  • 14.2k
  • 1
  • 28
  • 49

You can find such estimates for discrete time RW in Feller or in Karlin and Taylor. The estimate for continuous time RW follows using the tail of a Poisson variable