free web stats
ACM/EE/IDS 116

ACM/EE/IDS 116 Introduction to Probability Models


Syllabus [pdf]

Lectures
Tue & Thu at 9:00am-10:20am in Kerckhoff 125

Instructor

Office
Annenberg 114
Email
kostia@caltech.edu (please include “116” in the subject line)
Office Hour Thu 1pm-2pm, , or by appointment (please, send an email to schedule)
Head TA

Anirudh Gajula (agajula@caltech.edu)

TAs and OHs


Coure Description

This course introduces students to the fundamental concepts, methods, and models of applied probability and stochastic processes. The course is application oriented and focuses on the development of probabilistic thinking and an intuitive feel for the subject rather than on a more traditional formal approach based on measure theory. The main goal is to equip science and engineering students with necessary probabilistic tools they can apply in future studies and research. Topics covered include sample spaces, probabilities of events, random variables, expectation, variance, correlation, joint and marginal distributions, independence, moment generating functions, law of large numbers, central limit theorem, Monte Carlo method, conditional distributions, conditional expectation and variance, random vectors and matrices, random graphs, Wiener filters, Gaussian vectors, stochastic processes, Poisson process, Brownian motion, stationary processes, correlation function, and power spectral density.


Prerequisites

• Ma 3 or EE 55.
Some familiarity with MATLAB, e.g. ACM 11, is desired.


Textbooks
I will provided a set of comprehensive Lecture Notes.
• S.M. Ross, Introduction to Probability Models
• M. Harchol-Balter, Introduction to Probability for Computing

Course Plan

The following is a detailed tentative outline of the topics to be covered this term.
• Probability models, basics of probabilities: sample spaces, axioms, independence
• Random variables: discrete and continuous, expectation, moments, variance, covariance
• Independent random variables, moment generating functions, Poisson paradigm
• Markov’s and Chebyshev’s inequalities, law of large numbers, central limit theorem, Monte Carlo method
• Conditional probability, conditional expectation, conditional variance
• Law of total expectation, application to the quick-sort algorithm analysis
• Compound random variables, computing probabilities by conditioning
• Classification of Poisson events, the best prize problem, the ballot problem, double conditioning
• Application: probabilistic analysis of random graphs
• Random vectors, covariance matrix, Karhunen–Loève expansion, transformation of random vectors
• Wiener filters, Gaussian vectors, joint probability density function
• Stochastic processes, Markov chains, counting processes, Poisson processes
• Interarrival and waiting times, generating the Poisson process
• Merging and splitting Poisson processes, conditional distribution of the arrival times, order statistics
• Multi-type Poisson process, application to insurance, health care, and traffic engineering
• Brownian motion (Wiener process), hitting times, and maximum variable
• General stochastic processes, the mean and correlation functions, stationary processes
• Gaussian processes, estimation of the correlation function, power spectral density


Practice Problems

Each lecture will be accompanied by two Practice Problems: a somewhat easier, more practical Problem A, and a more difficult, more conceptual Problem B. The main goal of the practice problems is threefold: to help you better understand the material covered in the corresponding lecture, to help you prepare to solve problems in problem sets and exams, and to accommodate the diversity of students’ math backgrounds by providing both easier and more challenging problems. These problems are for self-practice: they will not be graded, and the solutions (posted on Piazza) also illustrate the expected level of rigor for problem sets and exams.


Grading

Your final grade will be based on your total score. Your total score is a weighted average of Problem Sets (60%), Midterm exam (20%), and Final exam (20%). You can increase your total score by up to 5% if you participate actively in Piazza discussions in the Q&A section. Every answer submitted before TAs or instructor answer, which is later endorsed as a “good answer” by TAs or instructor, gets 1% of the total score. There are no fixed thresholds for grades, but if your total score is 90% (80%, 70%, 60%), then you are guaranteed at least “A” (“B”, “C”, “D”). If you are interested in being a TA next year, try to be active on Piazza and help other students by answering their questions.

Problem Sets

60%
Midterm
20%
Final
20%

Problem Sets

There will be six Problem Sets. Problems (and solutions) will be posted on Piazza. For assignment and due dates see “Important Dates” below. Late submissions will not be accepted for any reason, but the Problem Set with the lowest score will be dropped and not counted toward your total score. Submitting wrong files or files in a wrong format is considered as a late submission. Extensions may be granted for academic, personal, or medical reasons. For extensions, please email the Head TA.


Exams
There will be two exams: Midterm (based on Lectures 1-8) and Final (based on Lectures 9-17). The Head TA will offer a review session before each exam. Both exams are take-home, self-timed, and closed-book, but you can use one sheet (double-sided) of your own notes. You can use your electronic devices only for typing and for basic arithmetic operations.

Ethical Use of AI
You can use AI tools (e.g., ChatGPT) to support your learning in this course, but only in ethical and responsible ways. For example, it is fine to use AI to generate a practice exam based on the topics covered in the course. However, using AI to directly solve your problem sets or exams, to give you hints, or check your solutions for correctness is not allowed, as it undermines your learning and violates Caltech's Honor Code. When in doubt, ask yourself: would it be acceptable for a tutor to do this for you? If not, then it is also not appropriate to ask an AI to do it. Most importantly, keep in mind that you are here to train your own neural network, not the artificial one.

Collaboration Policy
Here is a detailed collaboration policy. In general, collaboration is encouraged everywhere except for the exams. Let’s help each other and learn together! If you get stuck with a homework problem, I encourage you to discuss it with other students (offline or online on Piazza). But remember that you will have to prepare and submit your solution by yourself. No collaboration is allowed on the exams.

Important Dates
 
Available

Problem Set 1
1pm Tue, Oct 07
9pm Tue, Oct 14
Problem Set 2
1pm Tue, Oct 14
9pm Tue, Oct 21
Problem Set 3
1pm Tue, Oct 21
9pm Tue, Oct 28
Head TA Review
9am Tue, Oct 28
Midterm Exam
1pm Tue, Oct 28
9pm Tue, Nov 04
Problem Set 4
1pm Tue, Nov 04
9pm Tue, Nov 11
Problem Set 5
1pm Tue, Nov 11
9pm Tue, Nov 18
Problem Set 6
1pm Tue, Nov 18
9pm Tue, Nov 25
Head TA Review
9am Thu, Dec 04
Final Exam
1pm Thu, Dec 04
9pm Thu, Dec 11

Websites

Course Website (this page)
Piazza Page
Lecture notes, practice problems, problem sets, exams, solutions, announcements, and class discussions will be managed via Piazza, which is designed such that you can get a quick help from your classmates, TA(s), and instructor. Instead of emailing questions to the teaching staff, I encourage you to post your questions on Piazza because a) you will get the answers faster and b) your classmates may also benefit from seeing the answers to your questions.
• Problem sets and exams will be graded via Gradescope.
To submit your solution via Gradescope, your need to create a single PDF (not images) that contains the whole solution, and then upload it to Gradescope. Here is a useful link: How can I submit my homework as a PDF?

— If you a registered student, you will be enrolled on Gradescope by the end of the 1st week of classes, and you will receive a notification from Gradescope about your enrollment (please make sure that the email that you use on Gradescope is your official Caltech email).
— If you are a registered student, but have not been enrolled on Gradescope by the end of the 1st week of classes, please email the Head TA as soon as possible and ask to enroll you to Gradescope. Your absence on Gradescope means that, according to my records, you are not registered for the course.
— If you want just to audit the course, it is fine, you will have access to Piazza and all course materials there (please email me and I will enroll you on Piazza), but you will not have access to Gradescope and your submissions will not be graded. If you audit the course this year, you should not register for the course in the future.


Suggested Study Process
To get the most out of ACM 116, here is my suggested study process:
Have Enough Sleep: Good sleep is an important prerequisite for learning.
Attend Lectures: Focus on understanding the big picture of what is going on.
Review Lecture Notes: Ideally on the same day they are released, make sure everything is clear.
Ask and Answer Questions: If something is not clear, ask on Piazza, and help your classmates by answering their questions.
Summarize in Your Own Notes: After each lecture, very briefly summarize my notes, extract the essence.
Work on Practice Problems: Attempt to solve the practice problems and review my solutions.
Attend Office Hours: Interact with the instructor, TAs, and other students.
Start Early: Begin each problems set on the day it is released (or as soon as possible after that).
Finish Early: Aim to complete each problem set and exam at least one day before the deadline.
Stuck? Ask for Help: If you get stuck on a problem, ask for hints on Piazza (unless it is an exam problem ;-))

Keep in Mind
My goal is to help you understand and learn the material. Understanding is a creative process that takes time and effort. If you do not understand something, please ask me. If you are struggling to balance the workload, talk to me. If you have any concerns, let me know. Keep in mind that I am here to help.

Honor Code
You must conform to the Honor Code:
“No member of the Caltech community shall take unfair advantage of any other member of the Caltech community.”

Tasks for Week 1:

a) Install MATLAB from Caltech IMSS.
b) Self-study: Introduction to MATLAB [m] and simulation using MATLAB [pdf]