Content of present website is being moved to . Registration of will be discontinued on 2020-08-14.
Quantitative Analysis
Parallel Processing
Numerical Analysis
C++ Multithreading
Python for Excel
Python Utilities
Printable PDF file
I. Basic math.
II. Pricing and Hedging.
III. Explicit techniques.
IV. Data Analysis.
V. Implementation tools.
VI. Basic Math II.
1. Real Variable.
2. Laws of large numbers.
3. Characteristic function.
4. Central limit theorem (CLT) II.
5. Random walk.
A. Zero-or-one laws.
B. Optional random variable. Stopping time.
C. Recurrence of random walk.
D. Fine structure of stopping time.
E. Maximal value of random walk.
6. Conditional probability II.
7. Martingales and stopping times.
8. Markov process.
9. Levy process.
10. Weak derivative. Fundamental solution. Calculus of distributions.
11. Functional Analysis.
12. Fourier analysis.
13. Sobolev spaces.
14. Elliptic PDE.
15. Parabolic PDE.
VII. Implementation tools II.
VIII. Bibliography
Notation. Index. Contents.

Recurrence of random walk.

ccording to the proposition ( Infinitely often zero-or-one law ), for a random walk $S_{n}$ MATH


(Recurrent value of random walk) The number $x\in\QTR{cal}{R}$ is called "recurrent value" of random walk MATH if MATH

The set of recurrent values is denoted by $\Re$ .


(Possible value of random walk) The number $x\in\QTR{cal}{R}$ is called "possible value" of random walk MATH if MATH


(Structure of recurrent values) The set $\Re$ is described by one of the following statements.

1. $\Re=\not 0 $ .


3. $\Re=\QTR{cal}{R}$ .

4. MATH .


Let $x,y\in\Re$ . Then for any $n$ and almost any path $\omega$ MATH Hence, MATH The r.v. MATH is distributed like $S_{n_{1}-n_{2}}$ . Therefore, $x-y\in\Re$ . We proved that the set $\Re$ is an additive group.

One may show by a similar argument that the set $\Re$ is closed.

Let $c\in\Re$ . The $c$ cannot have a bounded neighborhood around it that is also included in $\Re$ . Indeed, by additivity of $\Re$ one then expands such neighborhood beyond any boundary. Hence, either $\Re$ is $\QTR{cal}{R}$ or it consists of singular points. In the latter case $\Re$ is either $\left\{ 0\right\} $ or has the form MATH due to closeness with respect to addition.


(Extension of Borel-Cantelli lemma to random walk). For a random walk $S_{n}$ ,

1. MATH $\ \Rightarrow$ MATH .

2. MATH $\ \Rightarrow$ MATH .

Note that MATH means $0\not \in \Re$ and MATH means $0\in\Re$ .


The statement 1 is a direct consequence of the proposition ( Borel-Cantelli lemma, part 1 ). The statement 2 does not follow from ( Borel-Cantelli lemma, part 2 ) because MATH are not independent events. Hence, we proceed with the proof of 2.

By the definition ( Limsup and liminf for sets ), for a family of sets MATH MATH then MATH Thus, for any $\varepsilon>0$ , MATH According to the section ( Operations on sets and logical statements ), the statement MATH means MATH . Therefore, we continue MATH The above statements within the union are disjoint: MATH Note that MATH and MATH imply MATH . Hence, MATH and the events MATH and MATH are independent: MATH Note that $S_{n}-S_{m}$ is distributed as $S_{n-m}$ : MATH . Hence, the second probability is $m$ -independent: MATH If follows that if MATH then we must have MATH .

Next, we complete the proof by showing that MATH for any $k=1,2,...$ . We introduce the event MATH and note that the events MATH are disjoint. Hence, we have MATH and, consequently, MATH We now repeat the argument that lead to MATH starting from MATH .


(Recurrence lemma 1) For a random walk MATH , any $\varepsilon>0$ and any MATH we have MATH


We calculate MATH We define MATH and include the event MATH in the union MATH : MATH The term MATH joins the $\sum_{j=0}^{n-1}$ as the $n$ -th term: MATH We change the order of summation: MATH The $p$ and $j$ sums are separate: MATH


(Recurrence lemma 2) Let MATH be a family of positive numbers such that

1. MATH is increasing in $m$ and MATH as MATH .

2. MATH .

3. MATH as MATH .



Assume the contrary. We calculate MATH by 2: MATH by 1: MATH We pass the inequality MATH to the limit $m\rightarrow\infty$ and apply 3 with $\delta=\frac{1}{A}$ then MATH for arbitrary $A$ . This is a contradiction.


(Recurrence result 1) If MATH in pr. then $\Re\not =\not 0 .$


We apply the proposition ( Recurrence lemma 2 ) with MATH . The condition MATH yields the condition 3 of the proposition ( Recurrence lemma 2 ) and the proposition ( Recurrence lemma 1 ) yields the condition 2 of the proposition ( Recurrence lemma 2 ). We derive MATH Thus $0\in\Re$ according to the second part of the proposition ( Extension of Borel-Cantelli lemma to random walk ) applied to $S_{n}/\varepsilon$ .


(Recurrence result 2) Suppose that at least one of MATH or MATH is finite. Then $\Re\not =\not 0 $ iff MATH . Otherwise MATH iff MATH and MATH iff MATH .


The statement is a consequence of the propositions ( Strong law of large numbers for iid r.v. ) and ( Recurrence result 1 ).

Notation. Index. Contents.

Copyright 2007