Today’s Class

1. Recurrences
2. Random Walks

Recurrences

Definition. A recurrence is linear if it is of the form

 $$f(n) = a_1 f(n-1) + a_n f(n-2) + \cdots + a_d f(n-d) = \sum_{i=1}^d a_i f(n-i)$$ 

Definition. The order of a linear recurrence defined in the above equation is $d$.

Random Walks

Law of Total Probability (single event):

 $$P(A) = P(A\;|\;E) P(E) + P(A\;|\;\bar{E}) P(\bar{E})$$ 

Next Class

1. Reflection