### Recent Announcements

**June 8:**Please log on to GradeBook and verify your scores for Homework 3, Homework 4, regraded midterms, and the in-class exercises. Contact Jacob if you spot something wrong or have any questions.**June 6:**A practice exam has been posted on Piazza. Solutions will be posted after Friday's sections.**June 5:**In preparation for the final exam, Jacob will hold extra office hours Monday 11am-1pm, and Prof. Vaughan will hold extra office hours Monday 3-4pm.**June 4:**All course evaluations for the CS department have moved online this quarter. You should have received a link to fill out the evaluation form for this course. Please take a moment to complete this survey. Constructive suggestions for improvement or comments on what we're doing right are most useful. Feedback must be received by the end of this week.

### Course Overview

This course is designed to help students develop the mathematical
reasoning skills necessary to solve problems that involve
*uncertainty*. The foundational problem solving skills you will
learn in this class are crucial for many exciting areas of computer
science that inherently involve uncertainty, including artificial
intelligence and machine learning, data mining, financial modeling,
natural language processing, bioinformatics, web search, algorithm
design, cryptography, system design, network analysis, and more.
These skills will also help you analyze the uncertainty in your
day-to-day life.

The first half of the course will cover the basics of probability, including sample spaces and probability, conditional probability, discrete and continuous random variables, expectation, mean and variance, and the Law of Large Numbers, with some applications to information theory. The second half of the course will focus on inference and Markov chains.

STAT 100A is required for this course. Although we will review all of the basics of probability in class, we will go through some of this material very quickly. If you are not familiar with basic concepts like random variables and expectation, the first half of the course will be more challenging and require extra effort from you.

### Meeting Times

**Lectures:**
Mondays & Wednesdays, 2:00-3:50pm,
Boelter 2444

**Discussion Sections:**

Fridays, 2:00-3:50pm, Boelter 2444 (Section 1A)

Fridays, 4:00-5:50pm, Boelter 5436 (Section 1B)

Regular attendance at both lectures and sections is **required**. There will be frequent in-class exercises that count for 15% of your grade. Please attend the section for which you are enrolled.

### Staff and Office Hours

**Instructor:** Prof. Jenn Wortman Vaughan (jenn at cs)

Office Hours: Thursdays 11am-noon and by appointment, 4532H Boelter Hall

**TA:** Jacob Mathew (jacobgmathew at gmail)

Office Hours: Tuesdays 11am-1pm, 2432 Boelter Hall

**Graders:** Ding Zhao (zhaoding at ucla)
and Jake Stothard (stothardj at gmail)

### Breakdown of Grades

Grades will be based on the following components:

**Homework Assignments (25%):**There will be 5 homework assignments spread out over the quarter.**No late homeworks will be accepted.**Most problems will be of the pencil-and-paper variety, though there will be 2 or 3 C++ programming components too. For each assignment, a subset of the problems will be graded in detail; you may or may not know in advance which problems will be graded. Your solutions will be graded on both**correctness and clarity**. If you cannot solve a problem completely, you will get more partial credit if you identify the gaps in your argument than you will if you try to cover them up.**In-class Exercises (15%):**There will be frequent pencil-and-paper exercises given in both lecture and discussion sections. Sometimes you will be asked to complete these exercises in groups, sometimes on your own. These exercises will be graded based on effort. It's ok to get the wrong answer, but you need to show that you tried. Missed exercises cannot be made up, but your lowest exercise grade will be dropped.**Midterm (30%):**An in-class midterm will be given on Wednesday, May 2. The midterm will be closed-book, but one page of double-sided**hand-written**notes is allowed. Calculators and cell phones may not be used during the exam.**Final Exam (30%):**A cumulative final exam will be held Tuesday, June 12, 11:30am-2:30pm. The same rules apply as for the midterm.

### Schedule & Readings

The required textbook for this course is Introduction to
Probability (2nd Edition) by Dimitri P. Bertsekas and John
N. Tsitsiklis. We will cover Chapters 1-3, parts of Chapters 4 and 5,
and parts of Chapters 7-9. Assigned readings will be posted here
throughout the quarter. To get the most out of class, you should
complete the required reading **before** each lecture.

Slides will also be posted here after each lecture for your convenience, but reading the slides is not a good substitute for coming to class. In particular, the slides generally do not contain the details of the proofs and examples that we will go over in class.

This schedule is tentative and may shift a little as we get deeper into the material.

**Monday, April 2**(slides)

Course logistics. Sample spaces and events. The axioms of probability.

Reading: B&T pages 1-17

Handouts: course overview and logistics, academic honesty policy**Wednesday, April 4**(slides)

Conditional probability. The total probability theorem. Bayes' rule.

Reading: B&T pages 18-34**Friday, April 6**

*Discussion:*Solving problems using the sequential approach and the divide-and-conquer approach.**Monday, April 9**(slides)

Independence and conditional independence.

Reading: B&T pages 34-43**Wednesday, April 11**(slides)

Counting problems. Permutations and combinations. Binomial probabilities.

Reading: B&T pages 44-52, skipping the section on partitions

See also: this discussion of the Waffle House problem and this investigation into burger options**Friday, April 13**

*Discussion:*Applications of Bayes' rule and independence. Solving problems using the counting approach.**Monday, April 16**(slides)

Discrete random variables. Probability mass functions. Expectation.

Reading: B&T pages 72-83

**Wednesday, April 18**(slides)

Functions of random variables. Variance. Joint PMFs. Conditional PMFs.

Reading: B&T pages 83-103 (UPDATED!)**Friday, April 20**

*Discussion:*Decision making using expectation. Examples of joint and conditional PMFs.**Monday, April 23**(slides)

Conditional expectation. The Total Expectation Theorem. Independence of random variables.

Reading: B&T pages 104-118**Wednesday, April 25**(slides)

Correlation and covariance. Information and entropy.

Reading: B&T 217-222

Optional reading: Chapter 5 of Information Theory, Inference, and Learning Algorithms by David MacKay**Friday, April 27**

*Discussion: Midterm review.*(Back on!)**Monday, April 30**(slides)

Application of probability theory to data compression using Huffman coding.

Optional reading: Chapter 5 of Information Theory, Inference, and Learning Algorithms by David MacKay, especially 5.5 and 5.6**Wednesday, May 2**

**Midterm exam!!****Friday, May 4**

*Discussion: More applications to information theory.***Monday, May 7**(slides)

Continuous random variables. PDFs and CDFs.

Reading: B&T pages 140-158 (though we won't go into as much detail on normal random variables)**Wednesday, May 9**(slides)

Joint PDFs. Conditional PDFs. Application to analyzing a search on a linked list.

Reading: B&T pages 159-183**Friday, May 11**

*Discussion:*Parellels between discrete and continuous random variables.**Monday, May 14**(slides)

Bounds on probabilities. The Law of Large Numbers and the Central Limit Theorem.

Reading: B&T pages 264-270 (CORRECTED)**Wednesday, May 16**(slides)

Inference. Maximum likelihood and MAP.

Optional reading: Students curious about these topics may wish to look through Chapters 8 and 9 of B&T, though we won't follow the presentation in the book**Friday, May 18**

*Discussion:*Examples of applying maximum likelihood and MAP.**Monday, May 21**(slides)

Naive Bayes classifiers.

Reading: Pages 1-6 (not 2.4) of Tom Mitchell's chapter on Generative and Discriminative Classifiers**Wednesday, May 23**(slides)

Discrete time Markov chains. n-step transitions. Characterizations of states.

Reading: B&T pages 340-351**Friday, May 25**

*Discussion:*Translating descriptions of settings into Markov Chains.**Monday, May 28**

**No class, Memorial Day****Wednesday, May 30**(slides)

Long term behavior of Markov chains. Balance equations. Google's PageRank algorithm.

Reading: B&T pages 352-358

Optional reading: How Google Finds Your Needle in the Web's Haystack, though it is not necessary to understand the details of the power method and the final method of approximating I**Friday, June 1**

*Discussion:*Applying the balance equations.**Monday, June 4**(slides)

Absorption probabilities in Markov chains. The gambler's ruin.

Reading: B&T pages 362-369 (UPDATED)**Wednesday, June 6**(slides)

Time to absorption.

Reading: B&T pages 362-369**Friday, June 8**

*Discussion:*Review for final exam.**Tuesday, June 12**

**Final exam, 11:30-2:30pm!!**

### Homework Assignments

Homework assignments will be posted here throughout the quarter.

- Homework 1: Due Monday, April 16
- Homework 2: Due Monday, April 30
- Homework 3: Due Friday, May 18
- Homework 4: Due Wednesday, May 30
- Homework 5: Due Friday, June 8

### Piazza Discussion Board

We will be using Piazza for class discussion. Rather than emailing questions to the teaching staff, you are encouraged to post your questions on Piazza. Find our class page here.

Good uses of Piazza include:

- Asking for clarifications about material that was covered in class or in the reading.
- Sharing useful references that you've found with other students (as long as they do not contain homework solutions).
- Looking for other students with whom to discuss assignments or study for exams.
- Answering questions posted by other students to solidify your own understanding of the material.
- Discussing the course material and probability theory in general.

The course Academic Honesty Policy must be followed on Piazza and at all times. Do not post or request homework solutions! And please be polite.

### Academic Honesty Policy

Collaboration on the homework assignments is encouraged! Discussing the problems with others can help you learn. Students are free to discuss the homework problems with anyone in the class under the following conditions:

- Each student must write down his or her solutions independently, and must understand the solutions he or she writes down. Talking over solutions is fine, but reading or copying another student's answers is not acceptable!
- Each student must write a list of all of his or her collaborators at the top of each assignment. This list should include anyone with whom the assignment was discussed.

These policies are described in the Academic Honesty Policy that must be signed by every student in the class. The Dean of Students also has a a guide to Academic Integrity.