# CS494/594 Prob/Markov Chains in CS, Spring 2008

• Instructor: Dr. Michael Thomason
• Lectures: Afternoon WF (check time and location in CS Office)
• Office hours: 10-11 MWF CL316 (Often around at other times, but not guaranteed available.)

## Description

Yes, there really was a person called Markov...

Many applications in computer science deal with processes that evolve in time or space. If the evolution is probabilistic, these are stochastic or random processes. Many systems have inherent randomness due to natural variability, noise, or other factors; and even deterministic systems are often studied via probability models due to their size or because the inputs to which they respond are described by probabilities.

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.

## Topics

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 and Grading

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

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.