Yes, there really was a person called Markov...
This course begins with basic probability, then concentrates on finite-state Markov chains (MCs), a restricted kind of stochastic process with numerous applications in CS. We will use an outline of probability, numerous handouts, and a set of lecture notes on MCs. There have been changes in these notes over the years and changes still occur as material is added, etc. Be sure to get the current version.
Axioms of probability; properties arising from axioms; random variables; expectation and variance
Probability vs statistics; large number laws
Markov property; Discrete-parameter MCs; classification of states; absorbing chains; recurrent chains
Continuous-parameter MCs; basic equations and properties
Illustrations and applications in CS as time permits, including Hidden Markov Models (HMMs) and Prediction Suffix Trees (PSTs)
Prereq is CS 311 and permission of instructor. This course is for CS majors. Simple computations with matrices are widely used, and there are a few references to calculas. We will be looking at fundamental properties and deriving some basic equations. You will have to learn to run MATLAB at an introductory level (MATLAB is available on CS linux and solaris systems). You will write a little MATLAB code, mainly for I/O and plotting; will use the MATLAB statistical toolkit; and will use some MATLAB script provided to you for computations with MCs.
If you already have a good mathematical background in probability, do not take this course. It repeats too much material to be useful, and you should instead find a second course in stochastic processes or some other topic.
There will be two take-home exams for 100 pts each. Exams will be spaced about evenly through the semester. There will be from 4 to 6 graded homeworks of about 25 points each. Students interested in this course must contact the instructor. Graduate credit will require additional and/or alternate assignments compared to undergrad credit, and this will include some different questions on exams.
Students who have a disability that requires accomodation should make an appointment with the Office of Disability Services (974-6087) to discuss specific needs; also schedule an appointment with the Administrative Services Assistant, College of Arts and Sciences (974-4161) during her/his office hours.
Homework to be turned in for grading will be clearly indicated and will be handed out in class. You must work alone on graded homework, but all other homework is for your practice and discussion.
These are examples of handouts and homework about Markov chains: NetLoad, Hw6, Hw9, Hw11.