Course title: Probability,
SIEO 3658
Lecturer:
Prof. E. G. Coffman, Jr.
Office hours: By
appointment all days (including weekends)
Office: 813 Schapiro
(CEPSR) Bldg.
Phone: (212) 854-2152
Email: [email protected]
URL: http://www.ee.columbia.edu/~egc
Home address: 855
West End Ave (at 102nd St.)
Apt. 4C; Buzz to gain entry. Ph:
212-316-9038
TA:
Jian Tan
Room 801,
Schapiro (CEPSR)
Phone:
212-854-2498
Email:
[email protected]
Office
hours: Friday 1:00 - 3:00pm
Room: 633 S.
W. Mudd Building
Time: Tu, Th 11:00 - 12:15pm
Text: Introduction to Probability by Bertsekas and Tsitsiklis
Athena
Scientific, publishers 2002 (Athena Scientific)
Current errata can be found in book_errata
Lecture Notes (work in progress): The notes for
the course can be found in
lecturenotes.pdf They will
be updated on approximately a weekly
basis, and
they can be brought with you into exams.
Calendar
information (holidays, last day to add a class, last day
to exercise pass/fail option, etc., etc. )
Course structure:
There will be weekly homework assignments, 2 midterm
exams, and a final exam;
these will count for 20%, 25%, 25%, and 30%,
respectively.
Homework
problems are all taken from additional_problems
unless
stated otherwise. Solutions will be supplied by the
TA
and can be found within 48 hours
of the time they should have
been submitted in homework solutions.
Ethics: You may discuss homework solutions among yourselves
or with others. But
do not look at what another student
hands in for a homework
assignment. (Until after it's
returned of course.)
The first midterm is
scheduled for Oct 6, 2005
The solutions can be found in midterm1solutions.pdf
The second midterm is scheduled for Nov 10, 2005
Midterms
are closed book and last for the full class period.
You can have the instructor-supplied
notes with you during
exams.
Make-up Exam Policy:
You can always avoid taking a regularly
scheduled test, and take
a make-up exam. However, do be cognizant
of the fact that the make-up exam
must be guaranteed to be no easier than the regularly
scheduled exam (to be
fair to the majority who adhere to the schedule);
I can only guarantee this by
devising a make-up exam that is definitely harder
than the regular exam; I
make every effort to minimize the added
difficulty of the make-up exam.
For grading purposes, the make-up exam grades
are combined with the
others, just as if everyone took the same exam.
Week 1 (Sept.
6,8)
Reading: Sections 1.1 to 1.4
Homework assignment:
Problems 3,6,10,14,17.
Turn in homework at the beginning of class on Sept. 13. (Problems
19,25,35,
as given here originally are shifted to week 2.)
1. Background fundamentals
on sets, which will be covered
in a relatively quick review as needed.
Glossary: empty set, universal
set, subset, set definitions, partitions, blocks,
countability, power set, disjointness, n-tuples,
operations: union,
intersection, complement, Venn diagrams, set algebra,
DeMorgan's
laws.
2. Fundamental definitions of probability with
intuitive notions and examples,
some contrived, some from everyday life.
Glossary: probability space/model, experiments, outcomes,
events, probability
laws (nonnegativity,
additivity, normalization)
3. Discrete models and the uniform law, sequences (chains) as
outcomes
4. Continuous models and the uniform law
5. Properties of probability laws.
6. Modeling (granularity, abstraction, generality
of probability laws, ...)
7. Conditional probability: definition, probability
subspace, multiplication
rule, applications
8. Independence, conditional independence
9. Theorem of total probability, and Bayes rule
Week 2 (Sept
13,15)
Reading: The remainder of Chapter 1.
Homework assignment: Problems 19,23,25,26,30,35. Turn
in
solutions at the beginning of class on Sept. 20.
Continuation of Week 1
1. Independence, conditional independence
2. Bernoulli trials, counting successes
and failures
3. Counting: combinations, permutations,
binomial theorem, binomial
coefficients, factorials,
Stirling's formula.
4. Problem session, Chapter 1 (this
may extend into week 3).
Week 3 (Sept
20,22)
Continuation of Chapter 1 material, if needed.
Reading: Sections 2.1 to 2.4
Homework assignment: Problems 2,4,5, and 8 to be turned in at
the beginning
of class on Sept 27..
1. Discrete random variables as functions
from the sample space to
the real numbers.
2. Probability mass functions.
3. Expectations
4. Specific pmf's and expectations covered for
the uniform, geometric, binomial, and
Poisson probability laws.
Week 4 (Sept 27,29)
Continuation and review of Chapter 2 material
Reading: Notes sent by email and remainder of Chapter 2.
Homework assignment: Problems in Chapter 2: 7, 15, and 17
to hand in Oct. 4.
1. Higher moments (variance and standard deviation)
2. Conditional pmf's and moments (I will work
probs 14 and
16 of additional problems in class)
3. Independence
4. Problems
Week 5 (Oct
4,6)
No Homework this week. Midterm on
Thursday Oct 6.
Problem session on Oct. 4th.
1. We begin the study of the basic definitions of continuous
random variables,
focusing on comparisons with discrete random variables.
Common
rv's studied in depth are those with uniform, exponential,
or normal
distributions.
2. The same concepts are covered as in previous chapters:
multidimensional rv's, conditional probabilities,
moments,
derived distributions (common functions such as X/Y,
Y-X,
max(X,Y).
Week 6 (Oct 11,13)
Homework: Problem
1 (mean and variance are 2.33 and 9.8831, resp.)
2 (mean and variance are 5/2 and 3/4)
3 (mean and variance are 3a/2 and 3a^2/4)
5 (1 over lambda
times the natural log of 2)
10 (1/2 both parts)
13 (1/4)
Please show all calculations/derivations/explanations.
Due Oct. 18th.
1. We begin the study of the basic definitions of continuous
random variables,
focusing on comparisons with discrete random variables.
Common
rv's studied in depth are those with uniform, exponential,
and normal
distributions.
Week 7 (Oct
18,20)
Homework: Problems 9(a), 14, 17,
19
2,8,10(a) and (b), 16. Due Oct. 25.
Reading for next week. Chapter 4 up to p. 227.
Continuation of Chap. 3: derived distributions, monotonic functions
of a random variable, mixed distributions, distributions with discrete
and continuous components. Continuations of moment generating
functions.
Week 8 (Oct
25,27)
Homework due Nov. 1: Problems 4-14, 4-21, 4-23, 4-26
Reading: Chapter 4 continued up to p. 240,
Chapter 5 on the Bernoulli and Poisson processes.
Chapter 4: Sums of rv's, convolutions, more
on conditional distributions.
Law of iterated expectations, Law of total variance, Randomized
sums of i.i.d.
random variables. Covariance and correlation.
Commencement of Chapter 5. The Bernoulli process:
Two definitions 1) interarrival times are iid geometric
rv's, 2) sequences
of iid Bernoulli rv's. Splitting and merging (properly
defined) preserve
the properties of Bernoulli processes.
The Poisson process as sequences of iid exponential rv's, as a point
process where the number of points in any given interval
is Poisson
distributed and independent of the number of points in any
other disjoint
interval.
Week 9 (Nov 1,3)
Continuation of Bernoulli and Poisson processes.
Course recapitulation, problems, and remedial work as needed.
Focus of the next week's exam will be on Sections
3.1 through 3.6 and 4.1 through 4.5 (although it is impossible
to avoid the
fundamental concepts of Chapters 1 and 2).
Review of material for midterm #2 at a separate time and place.
Week 10 (Nov
10)
Midterm 2, Thursday Nov. 10
Week 11 (Nov 15,17)
The Laws of large numbers and the central limit theorem
(CLT). We will
not dwell on the niceties of convergence (leaving the general notion to
our
intuition) but we will be intent on learning how to use the
CLT.
Start of Chapter 5. The Bernoulli process:
Two definitions 1) interarrival times are iid geometric
rv's, 2) sequences
of iid Bernoulli rv's. Splitting and merging (properly
defined) preserve
the properties of Bernoulli processes.
Week 12 (Nov
22)
Continuation of Chapter 5; problems
Week 13 (Nov
29)
Finite Markov chains. Definition by state
diagrams and by one-step transition matrices.
n-step transition probabilities - powers of the transition
matrix
state classification: transient states, recurrent classes,
absorption
states, periodicities, reducibility
stationary distributions, balance equations, conditions
for solutions
Week 14 ( Dec 1, Dec 8)
Continuation of Markov Chains and course wrap-up.