Postscript version of this file

STAT 380 Lecture 7

Reading for Today's Lecture: Chapter 4 sections 1-3.

Goals of Today's Lecture:

• Define Markov Chain.

• Introduce transition matrix

• Derive Chapman Kolmogorov equations.

Today's notes

Summary of Probability Review

We have reviewed the following definitions:

• Probability Space (or Sample Space): $\Omega =$ set of possible outcomes, $\omega$.

• Events, subsets of $\Omega$.

• Probability: P function defined for events, values in [0,1] satisfying:

  1.

  $P(\emptyset)=0$ and $P(\Omega)=1$.

  2.

  Countable additivity: $A_1,A_2,\cdots$ pairwise disjoint ($j\neq k$ $A_j\cap A_k=\emptyset$)
  

  $$P(\cup_{i=1}^\infty A_i) = \sum_{i=1}^\infty P(A_i)$$

  
  

• Joint, marginal, cond'l prob mass functions: X,Ydiscrete:

  • Joint pmf
    
    p_X,Y(x,y) = P(X=x,Y=y).
    
    

  • Marginal pmf
    
    $$p_X(x) = P(X=x) = \sum_y p_{X,Y}(x,y)$$
    
    

  • Conditional pmf
    
    p_Y|X(y|x) =p_X,Y(x,y)/p_X(x).
    
    

• Joint, marginal, conditional densities: X,Y continuous:

  • Joint density f_X,Y(x,y); probabilities are double integrals

  • Marginal density
    
    $$f_X(x) = \int f_{X,Y}(x,y) dy$$
    
    

  • Conditional density
    
    f_Y|X(y|x) =f_X,Y(x,y)/f_X(x).
    
    

• Expected value:
  
  $${\rm E}(g(X)) = \sum g(x) p_X(x)$$
  
  
  or
  
  $${\rm E}(g(X)) = \int g(x) f_X(x) dx$$
  
  

• Conditional expectation
  
  $${\rm E}(g(Y)\vert X=x) = \sum g(y) p_{Y\vert X}(y\vert x)$$
  
  
  or
  
  $${\rm E}(g(X)\vert X=x) = \int g(y) f_{Y\vert X}(y\vert x) dy$$
  
  

• ${\rm E}(g(Y)\vert X)$ is previous with x replaced by X after getting formula.

Tactics:

• Convert English expressions to set notation:

  • ``Or'' means union (remember inclusive or).

  • ``And'' means intersection.

  • ``not'' means complement.

• Compute prob something happens as 1-prob it doesn't.

• Break up event into disjoint pieces and add up probabilities.

• Find independent events and write event as intersection.

• Find A, B for which P(A|B) is known.

• Use Bayes rule: if $B_1,\ldots,B_p$ is a partition then
  
  $$P(B_1\vert A) = \frac{P(A\vert B_1)P(B_1)}{\sum P(A\vert B_j)P(B_j)}$$
  
  

• Use first step analysis. (See family names example, craps game, alternating dice tossing on asst 1.)

Tactics for expected values:

• Use linearity:
  
  $${\rm E}(\sum a_j X_j) = \sum a_j {\rm E}(X_j)$$
  
  

• Condition on another variable and use
  
  $${\rm E}\left[{\rm E}(Y\vert X)\right] = {\rm E}(Y)$$
  
  

• Use first step analysis. (Special case of previous.)

Markov Chains

The last names example has the following structure: if, at generation n there are m individuals then the number of sons in the next generation has the distribution of the sum of m independent copies of the random variable X which is the number of sons I have. This distribution does not depend on n, only on the value m of Z_n. We call Z_n a Markov Chain.

Ingredients of a Markov Chain:

• A state space S. S will be finite or countable in this course.

• A sequence $X_0,X_1,\ldots$ of random variables whose values are all in S.

• A matrix ${\bf P}$ with entries P_i,j for $i,j\in S$. The matrix is required to be stochastic which means
  
  $$\sum_j P_{ij} = 1$$
  
  
  for all i.

The stochastic process $X_0,X_1,\ldots$ is called a Markov chain if

$$P\left(X_{k+1} =i_{k+1}\vert X_k=i_k,\ldots,X_0=i_0\right) = {\bf P}_{i_k,i_{+1}}$$

for all $i_0,i_1,\ldots,i_k$ and all k.

The matrix ${\bf P}$ is called a transition matrix.

Example: If X in the last names example has a Poisson$(\lambda)$ distribution then given Z_n=k, Z_n+1 is like the sum of k independent Poisson$(\lambda)$ random variables which has a Poisson($k\lambda$) distribution. So

$${\bf P}= \left[\begin{array}{llll} 1 & 0 & 0 & \cdots \\ e^{... ...ts \\ \vdots & \vdots & \vdots & \ddots \end{array}\right]$$

Example: Weather: each day is dry (D) or wet (W).

X_n is weather on day n.

Suppose dry days tend to be followed by dry days, say 3 times in 5 and wet days by wet 4 times in 5.

Markov assumption: yesterday's weather irrelevant to prediction of tomorrow's given today's.

Transition Matrix:

$${\bf P}= \left[\begin{array}{cc} \frac{3}{5} & \frac{2}{5} \\ \frac{1}{5} & \frac{4}{5} \end{array} \right]$$

Now suppose it is wet today. P(wet in 2 days) ?
$$\begin{align*}P(X_2=W\vert X_0=W) & = P(X_2=W,X_1=D \vert X_0=W) \\ & \qquad +... ...,W} P_{W,W} \\ & = \frac{1}{5}\frac{2}{5} + \frac{4}{5}\frac{3}{5} \end{align*}$$
Notice that all the entries in the last line are items in ${\bf P}$.

Look at the matrix product ${\bf P}{\bf P}$:

$$\left[\begin{array}{ll} \frac{3}{5} & \frac{2}{5} \\ \frac{1... ... \frac{2}{5} \\ \frac{1}{5} & \frac{4}{5} \end{array} \right]$$

Notice that the probability P(X₂=W|X₀=W) is exactly the formula for the W,W entry in ${\bf P}{\bf P}$.