# Introduction

Website: Here Canvas: Here Homework Release: Here on Friday (When the homework goes out, you already have all the material you need to do it that day.) Regrade request on Gradescope before 2 days of grade release. Gradescope: Here Homework is due every Friday at 1 pm. No extensions. No late minutes. Box: Here for HW solution at 1pm every Friday for the first two weeks, later will be picked up in recitation. Lectures: TUESDAY and THURSDAY 11:50 a.m. - 1:10 p.m. EST in Wean 7500. Zoom (Lectures and handouts will be uploaded to Canvas under the "Files" tab, print handout before class) Zoom Password: chocolate Recitation: (C) FRIDAY 2:30 p.m. - 3:20 p.m. EST in GHC 6115 with Alec Zoom TA OH: Alec Sun alecsun@andrew OFF HRS: Monday 3:30 p.m. - 5:00 p.m. EST Zoom

Social Hours: 8-9 p.m. on Tuesdays on Zoom Calendar:

• It is important to find a small group of students with whom you can check your answers.

• Discussing problems with others helps you learn better. If you collaborate with others, try to get "hints" rather than "answers." You should write up your actual homework on your own.

• If you use an outside source (web site, book, person, etc.), you must cite that source.

• At the top of your homework sheet, you must list all the people with whom you discussed any problem. (Even if you were the one doing the helping, you should list the other person.)

Weekly homework -- worth 35% combined. Midterm 1 -- worth 20%. Midterm 2 -- worth 20%. Final -- worth 20%. Occasional Quizzes -- worth 5%. Class Participation -- attend classes. If you participate heavily we reserve the right to move up your grade at our discretion.

A = 90 - 100% ; B = 80 - 89% ; C = 70 - 79% ; D = 60 - 69%

## Syllabus

[Tues Jan 18] Probability on events (Chpt 3 PnC book) [Thurs Jan 20] Discrete Random Variables, Joint Probs, Conditional Probability (Chpt 4 PnC book) [Tues Jan 25] Expectation, Linearity of Expectation, Conditional Exectation, Expectation via Conditioning (Chpt 5 PnC book). [Thurs Jan 27] Variance, Higher Moments (Chpt 6.1 - 6.5 PnC book). [Tues Feb 1] Sum of Random Number r.v., Stochastic Dominance (Chpt 6.6, 6.7 PnC book). [Thurs Feb 3] z-Transforms (Chpt 7 PnC book). [Tues Feb 8] Continuous Distributions (Chpt 8 PnC book). [Thurs Feb 10] Finishing Continuous + start Normal Distribution (Chpt 9 PnC book). [Tues Feb 15] Normal Distribution (Chpt 10 PnC book). [Thurs Feb 17] Pareto Distribution (Chpt 11 PnC book). [Tues Feb 22] Laplace Transforms + Simulation (Chpt 12 PnC book + Chpt 13.1) [Thurs Feb 24] MIDTERM I [Tues Mar 1] Tail Bounds (Chpt 14 PnC book). [Thurs Mar 3] Applications of Tail Bounds (Finish Chpt 14 + Chpt 15 PnC book). [Tues Mar 15] Balls and Bins + Start Las Vegas (Finish Chpt 15 + 17.1 PnC book). [Thurs Mar 17] Las Vegas Randomized Algs -- Quicksort and k-Select (Chpt 17 PnC book) [Tues Mar 22] Monte Carlo Randomized Algs -- Matrix Mult Checking, Multinomial Mult Checking (Chpt 18 PnC book) [Thurs Mar 24] More Monte Carlo -- Primality Testing (Chpt 19 PnC book) [Tues Mar 29] Discrete-time Markov Chains (Chpt 20 PnC book) [Thurs Mar 31] MIDTERM II [Tues Apr 5] Discrete-time Markov Chains (Chpt 21 PnC book) [Thurs Apr 7] Spring Carnival -- No class [Tues Apr 12] Discrete-time Markov Chains (Chpt 21 PnC book) [Thurs Apr 14] Infinite-state DTMCs (Chpt 22 PnC book cont) [Tues Apr 19] A bit of Queueing Theory (Chpt 23 PnC book) [Thurs Apr 21] Exponential & Poisson Process (Chpt 24 PnC book) [Tues Apr 26] Exponential & Poisson Process + Discussion (Chpt 24 PnC book) [Thurs Apr 28 Continuous-time Markov Chains (Chpt 25 PnC book) [Won't get here] Inspection paradox, PASTA (Chpt 26 PnC book) [Won't get here ...] M/G/1 (Chpt 26 PnC book)

Learning Outcome:

• Analyze probabilities and expectations using tools such as conditioning, independence, linearity of expectations.

• Compute expectation and variance of common discrete and continuous random variables.

• Apply z-transforms and Laplace transforms to derive higher moments of random variables.

• Prove elementary theorems on probability.

• Analyze tail probabilities via Markov, Chebyshev, and Chernoff bound concentration inequalities.

• Design randomized algorithms and analyze their efficiency.

• Model problems using discrete-time and continuous-time Markov chains.

• Derive limiting probabilities of Markov chains.

• Construct and analyze models for performance analysis of queueing networks.

• Understand the application of probability to problems in machine learning, theoretical computer science, networking, cloud computing, and operations research.

Table of Content