Definition of the Poisson process

• Counting processes N_t are continuous time stochastic process which counts the number of events occuring up to time t: N_t = \textrm{total number of events occuring up to time } t e.g. the number of accidents reported to an insurance company, the number of earthquakes in California, and so on.

• The Poisson process is the simplest counting process, intuitvely characterized by the following properties:

  1. The number of events occuring in disjoint time intervals are independent.
  2. The rate at which event occur is constant over time.
     
  3. The events occur one at a time.

• More formally a Poisson process N_t with rate paratmeter \lambda is a continuous time stochastic process such that

  • Independent increments: Given times s_1\le t_1 \le s_2 \le t_2 \cdots \le s_n \le t_n the random variables X_{t_i}-X_{s_i} (that is the number of events occurring in the disjoint time intervals [s_i,t_i]) are independent.

  • The rate at which events occur is denoted by \lambda>0 and for any (small) time interval [t, t + \Delta t] we have
    \begin{aligned} P \{ N_{t + \Delta t } = N_t \} &= 1- \lambda \Delta t +o(\Delta t) & \\ P\{N_{t + \Delta t}= N_t +1\} &= \lambda \Delta t +o(\Delta t) & \textrm{ with } \lim_{\Delta t \to 0}\frac{o(\Delta t)}{\Delta t}=0 \\ P\{N_{t + \Delta t}\ge N_t +2\} & = o(\Delta t) & \end{aligned} \tag{1.1}

Distribution of the Poisson process

Poisson process and exponential random variables

• Poisson processes and exponential (and gamma) random variables are intimately related. Given a Poisson process we consider the interarrival times T_1, T_2, \cdots: T_1 is time of the occurence of the first event, T_2 is the time elapsed between the first and second event, and so on.

Poisson process and uniform distribution

Let us start with a special case and assume assume that N_t=1, that is exactly one event has occured in [0,t]. Since the Poisson process has independent increments it seems reasonable the event may have occur with equal probability at any time on [0,t]. Indeed for s\le t we have, using the independence of increments. \begin{aligned} P\{T_1 \le s | N_t=1\} & = \frac{P\{T_1 \le s , N_t=1\}}{P\{N_t=1\}} = \frac{P\{\textrm{1 event in }(0,s] \textrm{ and no event in (s,t]} \}}{P\{N_t=1\}} \\ &= \frac{ \lambda s e^{-\lambda s} e^{-\lambda(t-s)} }{\lambda t e^{-\lambda t}} = \frac{s}{t} \end{aligned} and thus the density of the arrival time T_1 conditioned on N_t=1 is uniform on [0,t]

We study further the properties of the arrival times S_1< S_2 <\cdots of a Poisson process. The following result tells us that they follow a uniform distribution on [0,t].

Simulation of Poisson process

The characterization of the Poisson process in terms of exponential random variables suggest immediately a very simple algorithm to simulate N_t.

Simulation of a Poisson random variable

• It is not easy to simulate directly a Poisson random variable X from its pdf/cdf but we can do it elegantly using its relation with exponential random variable. To do this generate independent exponential random variable until they sum up to 1 (so as to generate X=N_1) and use the relation between exponential and uniform.
  \begin{aligned} X =n & \iff \sum_{k=1}^n T_k \le 1 < \sum_{k=1}^{n+1} T_k \iff \sum_{k=1}^n - \frac{1}{\lambda} \ln(U_k) \le 1 < \sum_{k=1}^{n+1} - \frac{1}{\lambda} \ln(U_k) \\ & \iff \ln( \prod_{k=1}^n U_k) \ge - \lambda > \ln( \prod_{k=1}^{n+1} U_k) \iff \prod_{k=1}^n U_k \ge e^{-\lambda} > \prod_{k=1}^{n+1} U_k \end{aligned}

• Algorithm to simulate a Poisson random variable with parameter \lambda: Generate random numbers until their product is smaller than e^{-\lambda}.

  • Generate random number U_1, U_2, \cdots.
  • Set X=n if n+1 = \inf \left\{ j \,:\, \prod_{k=1}^{j} U_j < e^{-\lambda} \right\}

Long-time behavior of the Poisson process

• We investigate the behavior of N_t for large time. We prove a CLT type result, namely that
  \lim_{t \to \infty} \frac{N_t-\lambda t}{\sqrt{\lambda t}} = Z \textrm{ in distribution} where Z is a standard normal RV.

• Recall that the characteristic function of a Poisson RV Y with parameter \mu is E[e^{i\alpha Y}]= e^ {\mu (e^{i\alpha} -1)}. Therefore E\left[ e^{i \alpha \frac{N_t - \lambda t}{\sqrt{\lambda t}}} \right] = e^{\lambda t \left( e^{i \frac{\alpha}{\sqrt{\lambda t}}} -i \frac{\alpha}{\sqrt{\lambda t}} -1\right)} Expanding the exponential we have \lambda t \left(e^{i \frac{\alpha}{\sqrt{\lambda t}}} -i \frac{\alpha}{\sqrt{\lambda t}} -1\right) = - \frac{\alpha^2}{2} + O( \frac{1}{\sqrt{\lambda t}}) and thus \lim_{t \to \infty} E\left[ e^{i \alpha \frac{N_t - \lambda t}{\sqrt{\lambda t}}} \right]=e^{-\frac{\alpha^2}{2}}.

• The same computation shows also that, for any fixed t, \lim_{\lambda \to \infty} \frac{N_t-\lambda t}{\sqrt{\lambda t}} = Z \textrm{ in distribution} since rescaling the parameter is equivalent to rescaling time.

Sampling a Poisson process

• We can sample or split a Poisson process. Suppose that every event of a Poisson process (independently of the other events) comes into two different types, say type 1 with probability p and type 2 with probability q=1-p.

The coupon collecting problem

• We revisit the couplon collector but we relax the assumption that all the toys are equally probable. We assume that any box contains toy i with probability p_i. How do we compute now the expected number of boxes needed to collect all the M toys? The argument used earlier does not generalize easily.

• We use the following trick or radomizing the time between boxes. Instead of collecting boxes at fixed time interval, we collect them at times which are exponentially distributed with paramter 1. Then the number of boxes collected up to time t a Poisson process N_t with rate \lambda=1 (on average it takes the same time to get a new box). We have now M types of events (getting a box with toy i) and we split the poisson process accordingly. Then by Theorem 1.4 the number of toys of type i collected up to time t, N^{(i)}_t is a Poisson process with rate \lambda p_i=p_i and the Poisson processes N^{(i)}_t are independent.

• We now consider the times T^{(i)} = \textrm{ time of the first event for the process } N^{(i)}_t that is the time where the first toy of type i is collected. The times T^{(i)} are independent since the underlying Poisson processes are independent, and are exponential with paramter p_i. Furthermore S = \max_{i} T^{(i)} = \textrm{ time until one toy of each type has been collected}. By independence we have P\left\{ S \le t \right\} = P\left\{ \max_{i} T^{(i)} \le t\right\} = \prod_{i=1}^M P\left\{ T^{(i)} \le t \right\} = \prod_{i=1}^M (1- e^{-p_it})

Poisson process with variable rate

• We can generalize the Poisson process by making the rate \lambda(t) at which event occur depend on time: a nonhomogeneous Poisson process N_t with rate paratmeter \lambda(t) is a continuous time stochastic process such that

• Independent increments: Given times s_1\le t_1 \le s_2 \le t_2 \cdots \le s_n \le t_n the random variables N_{t_i}-N_{s_i} (that is the number of events occurring in the disjoint time intervals [s_i,t_i]) are independent.

• We have \begin{aligned} P \{ N_{t + \Delta t } = N_t \} &= 1- \lambda(t) \Delta t +o(\Delta t) & \\ P\{N_{t + \Delta t}= N_t +1\} &= \lambda(t) \Delta t +o(\Delta t) & \textrm{ with } \lim_{\Delta t \to 0}\frac{o(\Delta t)}{\Delta t}=0 \\ P\{N_{t + \Delta t}\ge N_t +2\} & = o(\Delta t) & \end{aligned} \tag{1.2}

• One way to construct a nonhomgeneous Poisson process is by sampling it in a time-dependent manner. Suppose \lambda(t) is bounded (locally in t), then we pick \lambda > \lambda(t). We consider a Poisson process M_t with constant rate \lambda, and if an event occurs at time t then we decide to keep this event with probability p(t)=\frac{\lambda(t)}{\lambda} and we discard the event with probability 1-p(t). By the same argument we used in the section Sampling a Poisson process we see the number of kept events satisfies the definition of a non-homogeneous Poisson process in Equation 1.2

• Let us consider an event for the process M_t which occured in the interval [0,t]. By our analysis of arrival time we know that this event occured a time which is uniformly distributed on the interval [0,t]. Therefore the probability that this event was accepted and contribute to N_t is therefore p_t = \frac{1}{t}\int_0^t \frac{\lambda(s)}{\lambda} \, ds

Queueing model with infinitely many servers

• Assume that the the flow of customers entering an onine store follows a Poisson process N_t with rate \lambda. The time S spent in the store for a single customer (browsing around, checking out, etc..) is given by tis CDF G(t)=P\{ S \le t\} and we assume that the customers are independent of each other.

• To figure out how to allocate ressources one wants to figure out what is number of customers, M_t, which are still in the sytem at time t.

• To find the distribution of M_t let us consider one of the customer by time t. If he arrived at time s\le t then he will have left the system at time t with probability G(t-s) and will still be in the system by time t with probability 1-G(t-s). Since the arrival time of that customer is uniform on [0,t] the distribution of M_t is Poisson with mean E[M_t] = \int_0^t (1- G(t-s))ds = \lambda \int_0^t (1 - G(s))ds,.
  For large t, we see that E[M_t] \approx \lambda E[S].

Compound Poisson process

• Suppose that the number of claims receieved by an insurance follows a Poisson process. The size of each claim will be different and it natural to assume that claims are independent from each other. If we look at the total claims incurred by the insurance company this leads to a stochastic process called a compound Poisson process.

• A stochastic process X_t is called a compound Poisson process if it has the form X_t = \sum_{k=1}^{N_t} Y_k where N_t is a Poisson process and Y_1, Y_2,\cdots are IID random variables which are also independent of N_t.

• The process X_t has stationary independent increments. Using that N_t-N_s is a Poisson process X_t-X_s = \sum_{k=N_s}^{N_t} Y_k \textrm{ has the same distribution as } X_{t-s}= \sum_{0}^{N_{t-s}} Y_k

• We can compute the MGF of X_t (or its charactersitic function) by conditining on N_t. Suppose m_Y(\alpha)=E[e^{\alpha Y}] is the moment generating function of Y and using the MGF for the Poisson RV we find \begin{aligned} m_{X_t}(\alpha)& =E\left[ e^{\alpha X_t}\right] = E\left[ e^{\alpha \sum_{k=1}^{N_t} Y_k} \right] = \sum_{n=0}^\infty E\left[ e^{\alpha \sum_{k=1}^{N_t} Y_k} | N_t =n \right] P\{n_t=n\} \\ & = \sum_{n=0}^\infty m(\alpha)^n P\{n_t=n\} = e^{\lambda t ( m(\alpha) -1 )} \end{aligned}

Exponential random variables

To construct a Markov we will need lots of exponential random variables. Recall that an exponential random variable T with paramter \lambda has the pdf f_T(t)=\lambda e^{-\lambda t}, for t \ge 0 the cdf F_T(t) = 1- e^{-\lambda t} and mean E[T]=\frac{1}{\lambda}.

Definition of a continuous time Markov chain

• As for the Poisson process we will give two equivalent definition of the process, the first one describe infinitesinmal rate of change and leads to a system of ODEs describing the evolution of the pdf of X_t. The second definition use exponential random variables and waiting times and leads to an algorithm to simulate a continuous time Markov chain, often called the stochastic simulation algorithm.

Example

A = \begin{matrix} 1 \\ 2 \\ 3 \\ 4 \end{matrix} \begin{pmatrix} -1 & 1 & 0 & 0 \\ 1 & -3 & 1 & 1 \\ 0 & 1 & -2 & 1 \\ 0 & 1 & 1 & -2 \end{pmatrix} The (right) eigenvalues of A are 0, -1, -3, -4 and we can diagonalize A and find D=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & -3 & 0 \\ 0 & 0 & 0 & -4 \\ \end{pmatrix} = Q^{-1} A Q where the rows of Q are the corresponding eiegenvectors: Q=\begin{pmatrix} 1& 1 & 0 & -\frac13 \\ 1& 0 & 0 & 1 \\ 1& -\frac12 & -\frac12 & -\frac13 \\ 1& -\frac12 & \frac12 & \frac13 \\ \end{pmatrix} \quad \quad Q^{-1}=\begin{pmatrix} \frac14 & \frac14 & \frac14 & \frac14 \\ \frac23& 0 & -\frac13 & -\frac13 \\ 0& 0 & -1 & -1 \\ -\frac14& \frac34 & -\frac14 & -\frac14 \\ \end{pmatrix} Then we find P_t = e^{tA} = Q e^{tD} Q^{-1} =

Alternative description

We can also construct the Markov chain X_t using exponential random variable.

• If X_t=i consider (independent) random variable T(i,j) with parameter \alpha(i,j) for j \not =i. Think of those as exponential clocks and when the first of the clocks rings, say clock j, then the Markov chain moves to state j.

• Using Proposition 2.1 we see that the chain moves from the state i to j if the clocks associated to the pair (i,j) rings first and this occur with probability Q(i,j) = \frac{\alpha(i,j)}{\sum_{j \not= i}\alpha(i,j)} = \frac{\alpha(i,j)}{\alpha(i)}

• The matrix Q(i,j) is the transition matrix for a discrete time Markov chain Y_n which has the same junmps probabilities as X_t but the transition occur at each unit time.

• Then a new set of clocks with rates \alpha(j,k) is produced and the process starts anew until the Markov chain moves to a new state.

• By Proposition 2.1 we can express this slightly differently. If in state i we use a single clock with rate \alpha(i) and when this clock rings then we move to state j according to the discrete time Markov chain Q(i,j).

Uniformizable chain

• Consider a Markov chain Y_n with transition matrix Q and we assume that Q(i,i)=0. Then we pick rate \lambda(i)=1 for all states i. The times at which the Markov chain has transition is thus a sum of IID exponential, that at time descriebed by a Poisson process. In other terms we have X_t = Y_{N_t} where N_t is a Poisson process with rate 1.

Stationary distributions and detailed balance

• A probability vector \pi is a stationary distribution for the Markov chain with generator A if
  \pi P_t = \pi \quad \textrm{ for all } t =0 which, by Komlogorov equation, is equivalent to \pi A = 0

• In terms of the rate \alpha(i,j) we see that \pi is stationary if ansd only if \sum_{i \not= j} \pi(i) \alpha(i,j) = \pi(j)\alpha(j) = \sum_{i \not=j} \pi(j) \alpha(j,i) which we can interpret as a balance equation: \pi(i)\alpha(i,j) is the rate at which the chain in a state \pi changes from i to j.

• As for discrete time we say that a Markov chain satisfies detailed balance if \pi(i) \alpha(i,j) = \pi(j) \alpha(j,i) \textrm{ for all } i \not= j and detailed balance obviously implies stationarity.

Convergence to the stationary distribution

If the state space is finite and the chain is irreducible then we have convergence to equilibrium.

Transient behavior

To study the transient behavior in continuous time we can use similar ideas as in discrete time.

• Absorption probabilities: the absorption probabilities do not depend on the time spent in every state so they can be computed using the transition matrix Q(i,j) for the embedded chain Y_n and the formula in Section [Absorption probabilities]

• Expected hittiing time: For example we have the following result

Explosion

• For a continuous time Markov chain X_t let us consider the time of the successive jumps S_1=T_1, S_2=T_1+T_2, S_3=T_1+T_2+T_3, \cdots Here the T_i are independent exponential but, in general, no identically distributed with paramters \alpha_i which depends on the state being visited. We have then E[S_n]= \sum_{i=1}^n \frac{1}{\lambda_i}

• Explosion: To see what can happen consider a Markov chain with rate \alpha(i,i+1)=(n+1)^2 and all other rates equal to 0. Then the Markov chain moves up by 1 at every jump like a Poisson process but at accelerated pace. We have then E[S_\infty]= \sum_{n=1}\frac{1}{n^2} < \infty so S_\infty < \infty with probability 1. So there are infinitely many jumps in finite time and X_t=+\infty after a finite time. This is called explosion.

Transience, recurrence, and positive recurrence.

• The recurrence and transience for a continuous time Markov chain can be defined as for discrete time. A an irreducbile Markov chain X_t is recurrent if the chain starting from a state i returns to i with probability 1 and transient if X_t never return to i with some non-zero probability.

• Transience/recurrence has nothing to do with the actual time spent in every state and so we have immediately X_t \textrm { with rates } \alpha(i,j) \textrm{ is } \begin{array}{l} \textrm{transient} \\ \textrm{recurrent}\end{array} \iff Y_n \textrm{ with transition } Q(i,j)=\frac{\alpha(i,j)}{\alpha(i)} \textrm{ is } \begin{array}{l} \textrm{transient} \\ \textrm{recurrent}\end{array}

• For positive recurrence we need to define the first return to a state i. This is most easily defined in terms of the return for the embeded Markov chain Y_n and its first return time \tau(i). The time until X_0 returns to i will the sum of the time spent in each state. If S_n denotes the time of the jumps and \tau(i)=n after visiting the state j_0, j_1, \cdots j_{n-1}, j_n=i then the return time is \sum_{k=0}^{n-1}(S_{k+1}- S_k) where S_{k+1}-S_k is exponential with paramter \alpha(j_k). The first return time to state i for the Markov chain X_t is given \Sigma(i) = \sum_{k=0}^{\tau(i)-1}(S_{k+1}- S_k)

Stationary distribution for recurrent chains

Ergodic theorem for positive recurrent Markov chains

We have the following theorem which is the exact counterpart of the discrete time case (and is proved very similarly so we will omit the proof).

Birth and death process

• A general birth and death process is a continuous time Markov chain with state space \{0,1,2,\cdots\} and whose only non-zero transition rates are \begin{aligned} &\lambda(n) = \alpha(n,n+1) & = \textrm{ birth rate for a population of size } n & (\textrm{ for } n\ge 0) \\ &\mu(n)=\alpha(n,n-1) & = \textrm{ death rate for a population of size } n & (\textrm{ for } n\ge 1) \end{aligned}

• The Kolmogorov equations for the distribution of X_t are, for n\ge 1 \frac{d}{dt}p_t(n) = \underbrace{ \mu(n+1) p_t(n+1)}_{\textrm{ increase due do death} \atop \textrm{in a population of size } n+1} + \underbrace{\lambda_{n-1} p_t(n-1)}_{\textrm{ increase due do birth} \atop \textrm{in a population of size } n-1} - \underbrace{(\lambda(n) + \mu(n))p_t(n)}_{\textrm{ decrease due do birth/death} \atop \textrm{in a population of size} n}. For n=0, the eqation reads \displaystyle \frac{d}{dt}p_t(0)= \mu(1) p_t(1) - \lambda(0) p_t(0).

• The generator has the form \begin{matrix} 0 \\ 1 \\ 2\\ \vdots \end{matrix} \begin{pmatrix} -\lambda(0) & \lambda(0) & 0 & 0 & \dots \\ \mu(1) &-\lambda(1) -\mu(1) & \lambda(1) & 0 & \dots \\ 0 & \mu(2) &-\lambda(2) -\mu(2) & \lambda(2) & \dots \\ \vdots & \ddots & \ddots & \ddots & \\ \end{pmatrix}

Examples

• Poisson process: There is no death and the birth rate is constant \mu(n)=0 \quad \textrm{ and } \quad \lambda(n)=\lambda

• Queueing models: Imagine a Poisson process (with rate \lambda) describing the arrival of customers. In the systems there are k service station at which the service time is exponential with rate \mu. If one service station is empty, upon arrival a customer immediately enter a service station and stay in the system until being served. If all stations are currently busy serving other customers, the customer wait until one stay becomes free. These models are called M/M/k queues where M statnds for Markovian and k is the number of queues, the first M describing the arrival process and the second M the service time (which is exponential).
  

• M/M/1 queue: If there is only one service station \lambda(n)=\lambda \quad \textrm{ and } \quad \mu(n) =\mu

• M/M/k queue: If there is k service station then the rates are \lambda(n)=\lambda \quad \textrm{ and } \quad \mu(n) = \left\{ \begin{array}{cl} n \mu & n \le k \\ k \mu & n > k \end{array} \right.

• M/M/\infty queue: If there is k service station then the rates are \lambda(n)=\lambda \quad \textrm{ and } \quad \mu(n) =n\mu

Transience

• To study transience we use the embedded Markov chain and ?@thm-criteriontransience. Choosing the reference state 0 we look for a solution a(n) with a(0)=1 and 0 < a(n)< 1 for n\ge 1 of the system of equations \lambda(n) a(n+1) + \nu(n) a(n-1) = (\lambda(n) + \mu(n)) a(n) This leads to a(n+1) - a(n) = \frac{\mu(n)}{\lambda(n)} (a(n+1) - a(n)) = \cdots = \prod_{j=1}^n\frac{\mu(j)}{\lambda(j)} (a(1) - 1)

and thus, by telescoping, a(n+1)= 1 + \sum_{k=0}^{n} (a(k+1) -a(k)) = 1 + \left[1+ \sum_{k=1}^{n} \prod_{j=1}^k\frac{\mu(j)}{\lambda(j)}\right] (a(1) - 1) Taking n \to \infty we must have a(n)\to 0 and \sum_{k=1}^\infty \prod_{j=1}^k\frac{\mu(j)}{\lambda(j)} < \infty and we find the solution a(n)=\frac{\sum_{k=n}^\infty \prod_{j=1}^k\frac{\mu(j)}{\lambda(j)}}{1+ \sum_{k=1}^\infty \prod_{j=1}^k\frac{\mu(j)}{\lambda(j)}}

Recurrence

• To study postive recurrence we simply solve for the stationary distribution \pi A=0. The first equation (for n=0) gives \mu(1) \pi(1) - \lambda(0)\pi(0) =0 \tag{2.3} and \lambda(n-1) \pi(n-1) + \mu(n+1) \pi(n+1) - (\mu(n)+ \lambda(n))\pi(n)=0 \textrm{ for } n\ge 1 or
  \mu(n+1)\pi(n+1)-\lambda(n) \pi(n)=\mu(n)\pi(n)-\lambda(n-1) \pi(n-1) \tag{2.4} Combining Equation 2.3 and Equation 2.4 gives \pi(n) = \prod_{j=1}^n \frac{\lambda(j-1)}{\mu(j)} \pi(0) and thus we have a stationary distribution if and only if \sum_{k=1}^\infty \prod_{j=1}^k \frac{\lambda(j-1)}{\mu(j)} <\infty\,.

Definition of Brownian motion

• The Brownian motion X_t, t\ge 0, is a stochastic process taking value in \mathbb{R} (or \mathbb{R}^d ) and a model for random continuous motion taking place in space.

• By convention we set X_0=0 and start at 0. Saying that the motion is completely random does not mean that X_t and X_s are independent but rather that the motion after time s, that is X_t-X_s, should be idependent of X_s. More generally we will assume the property of independent increments like we did for the Poisson process N_t. We will also assume that the moition does not have any prefered disrection so we must have E[X_t]=0. In addition we will require that the map t \to X_t are continuous. If the paths are not continuous then N_t-t satisfies thses requirements. But requirement of continuity of the paths actually imply that the only possibility is for the increments to be normally distributed.

• Formally a Brownian motion or Wiener process with variance parameter \sigma^2 is a stochastic process X_t such that

  1. X_0=0.
  2. Independent increments: For any n>1 and times s_1\le t_1\le s_2 \le t_2 \le \cdots \le s_n \le t_n the random variables X_{t_1}-X_{s_1}, X_{t_2}-X_{s_2} \cdots X_{t_N}-X_{s_n} are independent.
  3. For any s< t the random variables X_t-X_s has a normal distribution with mena 0 and variance \sigma^2(t-s).
  4. The paths are continuous.

  As mentioned before, 3. actually follows from the other assumptions.

Brownian motion as limit of random walks

Let Y_1, Y_2, \cdots be IID random variable with E[Y_n]=0 and \textrm{ Var}(Y_n)=1. Then a random walk is defined by S_0=0, \quad S_n=Y_1 + \cdots + Y_n\,. We now define a process X^{(n)}_t by rescaling time and the size of the increments to obtain a proper limit X^{(n)}_t = \frac{S_{\lfloor n t \rfloor}}{\sqrt{n}} \quad \textrm{ for }t\ge 0 To understand this scaling note that if, say, t=1 we have X^{(n)}_1=\frac{Y_1+ \cdots + Y_n}{\sqrt{n}} which has mean 0 and variance 1 which is independent of n and we can hope to have a well-defined limit. Using now the central limit theorem we find X^{(n)}_t = \frac{S_{\lfloor n t \rfloor}}{\sqrt{n}} = \frac{S_{\lfloor n t \rfloor}}{\sqrt{\lfloor n t \rfloor}} \times \frac{\sqrt{\lfloor n t \rfloor}}{\sqrt{n}} \to t Z \quad \textrm{ in distribution} which has same distribution as X_t. Similarly X^{(n)}_t-X^{(n)}_s = \frac{S_{\lfloor n t \rfloor} -S_{\lfloor n s \rfloor} }{\sqrt{n}} = \frac{1}{\sqrt{n}} \sum_{j=\lfloor n s \rfloor +1}^{\lfloor n t \rfloor} X_j \to (t-s) Z \quad \textrm{ in distribution} which has the same distribution as X_t-X_s. Stronger form of convergences can be proved which shows that the path of the process are actually continuous in the limit but this is too technical for now.

Properties of Brownian motion

• Probability distributions and the Markov property: By definition X_t is a time-homogeneous process since X_{t+s}-X_s has the same distribution as X_t and the Markov property follows from X_t=X_s+ (X_t- X_s) which shows that the distribution of X_t only depend on X_s. We have then P\{ X_{t+s} \in A | X_s=x\} = P\{ X_t \in A - x \} = \int_{A-x} \frac{1}{\sqrt{2\pi t}} e^{-\frac{y^2}{2t}} dy = \int_{A} \frac{1}{\sqrt{2\pi t}} e^{-\frac{(y-x)^2}{2t}} dy and so X_t is a Markov chain with transition probability densities p_t(x,y)= \frac{1}{\sqrt{2 \pi t}} e^{-\frac{(y-x)^2}{2t}}

• Reflection and Scaling:
  X_t \textrm{ is a Brownian motion } \implies \left\{ \begin{array}{l} Y_t = - X_t \textrm{ is a Brownian motion } \\ Z_t = \sqrt{a} X_{t/a} \textrm{ is a Brownian motion for any } a>0 \\ \end{array} \right. To see this one check that properties 1.-4. are satified in Definition of Brownian motion

Brownian motion in higher dimensions

The Brownian motion in dimension d is defined by X_t = ( X^{(1)}_t, \cdots, X^{(d)}_t) where the X^{(i)}_t are independent one-dimensional Brownian motions.

One deduce from this immediately that

1. X_0=0.
2. Independent increments: For any n>1 and times s_1\le t_1\le s_2 \le t_2 \le \cdots \le s_n \le t_n the random variables X_{t_1}-X_{s_1}, X_{t_2}-X_{s_2} \cdots X_{t_N}-X_{s_n} are independent.
3. For any s< t the random variables X_t-X_s has a normal distribution with mean 0 and covariance (t-s)I.
4. The paths are continuous.

One can conversely construct the Brownian motion from the properties 1. to 4.

The transition probabilities for Brownian motion are p_t(x,y) = \frac{1}{ (2 \pi t)^{d/2}} e^{-\frac{||y-x\|^2}{2t}} and we have the Chapman-Kolmogorov equation p_{t+s}(x,y) = \int_{\mathbf{R}^d} p_t(x,z) p_s(z,y) dz.

Brownian motion and heat equation

If \mu_0=\rho_o(x) dx is the initial distribution of Brownian particles X_o. Then at time t the distribution of X_t is given by \mu_t=\rho_t(x) dx where \rho_t(y) = \int_{\mathbf{R}^d} \rho_0(x) p_{t}(x,y) \, dy Conversely if we consider a function f: \mathbf{R}^d \to \mathbf{R} we have E[ f(X_t) |X_0=x] = \int_{\mathbf{R}^d} p_{t}(x,y) f(y) \, dy where we should pick f such that the expectation of the right is well defined. Note that since p_t(x,y)=p_t(y,x) is symmetric these two equation are actually identical.

We now derive a differential equation for the function f(t,x)\equiv E[ f(X_t) |X_0=x]. We could simply differentiate, under the integral, the semigroup with respect to t, but instead we provide a more interesting probabilistic proof.

Heat equation in domain

Given a domain B with boundary \partial B let us consider the boundary/initial value problem \begin{aligned} & \frac{\partial f}{\partial t}(x,t) = \frac{1}{2}\Delta f (x,t), x \in B \\ & u(t,x)=g(x), x \in \partial B \\ & u(0,x)=f(x), x \in B \\ \end{aligned} We can express the solution in terms of Brownian motion and the hitting time to the boundary \tau= \inf \{t: X_t \in \partial B \} namely u(t,x) = E\left[ f(X_t) 1_{\{\tau >t\}} + g(X_{\tau}) 1_{\{\tau \le t\}}\right]\,. This is derived in a similar way as before. If we take t \to \infty and say B is bounded then the path will eventually hit \partial B and so taking t \to \infty we find the equation \begin{aligned} & \Delta u (x,t)=0, x \in B \\ & u(t,x)=g(x), x \in \partial B \\ \end{aligned} whose solution is E\left[ g(X_{\tau}) 1_{\{\tau \le t\}}\right].

Recurrence and transience of Brownian motion

• In dimension 1 let us consider the interval [0,R] and the function g on the boundary with g(0)=0 and g(R)=1. Then solution the equation u''(x)=0\, \quad \textrm{ with } \quad u(0)=0, u(1)=1 is u(x)=\frac{x}{R} and so u(x)= P\{ X_t \textrm{ hits } R \textrm{ before hitting } 0| X_0=x\} = \frac{x}{R} Not coincidentally this is the same as the gambler’s ruin (with p=\frac{1}{2}). Therefore P\{ X_t \textrm{ hits } 0| X_0=x \} = \lim_{R \to \infty} P\{ X_t \textrm{ hits } 0 \textrm{ before hitting } R| X_o=x\} = \lim_{R \to \infty} \left(1- \frac{x}{R}\right) =1 and so X_t is recurrent in d=1.

Brownian motion with drift

For a vector \mu \in \mathbb{R}^d let us consider the Brownian motion with drift \mu is given by Y_t = X_t + t\mu It is not too difficult to see that the following properties hold

• Y_t has independent increments and Y_t-Y_s (s\le t) has a normal distribution with mean \mu(t-s) and covariance \sigma^2(t-s)I.

• The transition probabilities are p_t(x,y)= \frac{1}{(2\pi \sigma^2 t)^{d/2}} e^{- \frac{\|y-x-t\mu\|^2}{2\sigma^2 t}}.

• The function f(t,x)=E\left[ f(Y_t)\right] satisfies the partial differential equation \frac{\partial f}{\partial t} = \frac{1}{2}\Delta f + \mu \nabla f

References