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.