Loading...

​​Discussion 13A

​​Iterated Expectation

​​​​$E[X \mid Y]$​ is a conditional expectation. 

​​​​$E[X \mid Y] = \sum_x x \Pr(X=x \mid Y)$​

​​It is a function of ​​$Y$​: for any particular value of ​​$Y=y$​, what do we expect ​​$X$​ to be? So ​​$E[X \mid Y] = g(Y)$​.

​​The expectation of this function ​​$E_Y[g(Y)] = E_Y[ E[ X \mid Y ] ] = E[X]$​.

​​

​​This is also known as the law of total expectation because ​​$E_Y [g(Y)] = \sum_y g(y) \Pr(Y=y) = \sum_y E[X \mid Y=y] \Pr(Y=y)$​.

​​Taking it a couple steps further,

​​​​$\sum_y E[X \mid Y=y] \Pr(Y=y)$​

​​​​$= \sum_y \Big(\sum_x x \Pr(X=x \mid Y=y) \Big) \Pr(Y=y)$​

​​​​$= \sum_{x,y} x \Pr(X=x \mid Y=y) \Pr(Y=y)$​

​​​​$= \sum_{x,y} x \Pr(X=x, Y=y)$​

​​​​$= \sum_{x} x \sum_y \Pr(X=x, Y=y)$​

​​​​$= \sum_x x \Pr(X=x)$​

​​​​$=E[X]$​

​​Markov Chains

​​Premise: represent a sequence of random variables ​​$X_1, X_2, \cdots, X_n$​ as a directed graph, where each node represents a value that the random variables can take on, and holds a probability distribution to describe transitions to the next node

​​

​​​​$\mathcal{X}$​: state space. set of possible values of ​​$X_i$​

​​​​$P$​: state transition matrix. entry ​​$P_{i,j}$​ at row ​​$i$​ and column ​​$j$​ is ​​$P_{i,j} = \Pr(X_{n+1} = j \mid X_n = i)$​

​​​​$\pi_0$​: initial distribution. ​​$\pi_0(i) = \Pr(X_0 = i)$​. in general ​​$\pi_n$​ is the distribution of ​​$X_n$​

​​

​​The sum of each row of ​​$P$​ is ​​$1$​. Because of the convention of defining ​​$P_{i,j}$​ as above, the distributions ​​$\pi_i$​ are row vectors and the ​​$\pi_{n+1} = \pi_n P$​ is a transposed version of the usual matrix-vector multiplication.

​​

​​A stationary distribution ​​$\pi$​ is a distribution on ​​$\mathcal{X}$​ such that ​​$\pi = \pi P$​. It is a vector associated with an eigenvalue of ​​$1$​.

​​Absorption Probabilities

​​See problem

​​Hitting Times

​​See problem

​​