Math 4653: Elementary Probability
Fall 2013: Professor Andrew Odlyzko
Classes: TTh 4:40 - 6:35, Vincent 206
Office Vincent Hall 511
- phone 612-625-5413
- email: odlyzko@umn.edu (preferred and most reliable method)
Office hours: MW 3:00 - 6:00, and by appointment. However, always check this web page
before coming over, as on some days the hours may be restricted.
Textbook: "Elementary Probability for Applications" by Rick Durrett, available
in the bookstore. Chapters 1-4 and 6 will be covered in detail, 5 and 7 sketchily.
There is just one edition of this book, so used copies will do fine.
(Some of the more recent printings have a few typos corrected, but this is not
a major change.)
Warning: Quite a few of the 'answers to odd problems' in the back of the
book (pp. 239-240) are wrong!
Additional material:
You might also find useful two textbooks that are available freely (and legally) online,
C. Grinstead and J. L. Snell "Introduction to Probability",
Grinstead-Snell book and
K. Baclawski and G.-C. Rota, "An Introduction to Probability and Random Processes",
Baclawski-Rota book.
Both are more advanced than the textbook for this course, but might be helpful.
A calculator is advisable. Computer systems such as Mathematica, Matlab, and Maple (or some systems
available on the Web, like Wolfram Alpha) might be helpful, but are
not essential and are not required. Some are
available in Math computer labs, and also (for CSE undergrads) for free downloads at
CSE Labs.
Exams: No final, three 100-minute in-class mid-terms on Thu Oct 3, Thu Nov 7, and Tue Dec 10.
Weekly homework assignments (usually), due (usually) on Thursdays, first one due Sept. 12.
Will be posted by the preceding Friday, and will (usually) cover material through the preceding Thursday.
Always due at the beginning of a class, late homeworks will not be accepted.
If you can't make it to class, you can leave your homework in
my mailbox in Vincent 107, or email it to me (in either typeset or scanned form).
You may work with others on homework
problems, but you have to write up your solution yourself, in your own words, to show you
understand the solution.
Special challenge problems: There will be occasional challenge problems for extra credit.
These you can only work on by yourself.
Exams will be open book; you may bring books, notes, and calculators, but no smart
phones, iPads, or other communication devices can be used, and you have to do all the work
yourself.
Grades: homework will count for 30%, the three exams for 20%, 25%, and 25%, respectively.
Expected effort: This is a 4-credit course, so you are expected to devote 12 hours
per week, on average (including lectures).
Scholastic Conduct: Cheating or other misconduct will not be tolerated. The standard University
policies will be followed.
General remarks:
This course develops the basic ideas of probability theory: random variables, distributions, expectations,
variances, conditional probabilities, Bayes' formula, Markov chains, and limit theorems. Discrete
probability dominates, and emphasis is on working with concrete problems that arise in applications.
Homework assignments and other notes:
-
Material to be covered the weeks of Sep 2 and 9: Chapter 1.
-
Due Thu Sep 12:
-
Textbook exercises (Chapter 1, pp. 26-31): 4, 20, 26, 38 (10 pts each),
8, 10, 32, 36 (15 pts each).
-
Material to be covered the weeks of Sep 16 and 23: Chapter 2.
-
Due Thu Sep 19:
-
Textbook exercises (Chapter 1): 16, 34, 42, 44 (10 pts each), 46, 48 (15 pts each), 52 (10 pts), 56 (20 pts).
-
Due Thu Sep 26:
-
Textbook exercises (Chapter 2): 6, 10, 18 (where a correction needs to be made to some
printings of the book, the problem is to place 8 rooks), 22, 24, 32, 38, 40, and 50 (10 pts each).
-
Problem A1: (10 pts) You have found a broken slot machine. Each time you pull a handle, you
get a penny with probability 0.99, and you get a dollar with probability 0.01.
What is the expected number of pulls on the handle until you have in your hands a dollar
or more?
-
Thu Oct 3:
-
In class mid-term. 100 minutes, not the full 115 minutes of the lectures,
-
Material to be covered on exam: Chapters 1 and 2.
-
Open book; you may bring books, notes, and calculators, but no smart
phones, iPads, or other communication devices can be used, and you have to do all the work
yourself. Blue books will be available, but you do not have to use them.
-
No homework due this week. For practice on material that was not covered on homeworks, but
may be on the mid-term, work out
textbook exercises 56, 62, 68, 72, 74, 78, 82, 84, 86, and 88 from Chapter 2.
Don't hand them in, they will not be graded. Solutions will be presented Tue Oct 1 in class.
-
Material to be covered in class on Tue Oct 1: review of chapters 1 and 2, solutions
to exercises.
-
Week of Oct 7: Start Chapter 3.
-
Due Thu Oct 10:
-
Textbook exercises 18, 24, and 54 from Chapter 1, 10 pts each.
Also 16, 44, 60, and 80 from Chapter 2, 15 pts each.
-
Problem A2: (10 pts) Alice has just finished law school, and is taking the bar exam.
Her chances of passing it on the k-th try are 1 - 1/k; i.e., she
is bound to fail on the first try, but does that for practice,
she succeeds with probability 50% on the second try, etc.
What is the expected number of times Alice will take the test
before she passes? (Part of the grade will depend on how simple
the answer you get is.)
-
Extra credit problem (25 pts): Textbook exercise 86 from Chapter 2.
You can only work on this by yourself, no
collaborations are allowed. 50 pts
if you find an elegant solution!
-
Solution to extra credit problem: file http://www.dtc.umn.edu/~odlyzko/Math4653/solch2prob86.pdf
-
Material to be covered in the week of Oct 14: rest of Chapter 3.
-
Due Thu Oct 17:
-
Textbook exercises 4, 6, 10, 14, 20, 22, 32, 33 from Chapter 3 (10 pts each).
-
Problem A3 (20 pts): Consider a "language" based on the 3 letters a, b, and c, with
probabilities 0.4, 0.35, and 0.25, respectively. In a random string of length 10,
what is the probability there is exactly one appearance of the substring (i.e.,
a run of consecutive letters, not a subsequence) aabxcac, where x can
be either b or c? The same question, but with length 15.
-
Material to be covered the week of Oct 21: start on Chapter 4.
-
Due Thu Oct 24:
-
Textbook exercises 36, 37, 40, 42, 48, 50, 52, 58, 64 and 66 from Chapter 3 (10 pts each).
-
Material to be covered the week of Oct 28: rest of Chapter 4.
-
Key formulas for absorbing Markov chains in matrix notation: file http://www.dtc.umn.edu/~odlyzko/Math4653/markov20111108.pdf
-
Due Thu Oct 31:
-
Textbook exercises 2, 4, 8, 12 (10 pts each), and 14, 16, 18, 24 (15 pts each) from Chapter 4.
-
Material to be covered in class on Tue Nov 5: Review of chapters 3 and 4, and exercises
assigned in preparation for the mid-term.
-
Thu Nov 7:
-
2nd in-class mid-term, 100 minutes. Material to be covered on exam: chapters 3 and 4.
-
Open book; you may bring books, notes, and calculators, but no smart
phones, iPads, or other communication devices can be used, and you have to do all the work
yourself. Blue books will be available, but you do not have to use them.
-
No homework due this week. For practice on material that was not covered on homeworks, work out
exercises (from Chapter 4) 30, 34, 36, 38, 40, 42, 44, and 46.
-
Also solve: Problem A4: Bob is in jail and has $3. He can get out on bail if he can get $8.
A guard agrees to make a series of bets with him. If Bob bets A dollars, he wins A with
probability 0.4 and loses A with probability 0.6. Find the probability Bob gets to $8 before
losing all his money if (a) he bets $1 each time, and (b) he bets, each time, as much as
possible, but not more than necessary to bring his fortune to $8.
-
Material to be covered the week of Nov 11: Chapter 5.
-
Due Thu Nov 14:
-
Textbook exercises (from Chapter 4): 38, 44, 46 (15 pts each), and 40 (10 pts).
-
Problem A4 (15 pts): Bob is in jail and has $3. He can get out on bail if he can get $8.
A guard agrees to make a series of bets with him. If Bob bets A dollars, he wins A with
probability 0.4 and loses A with probability 0.6. Find the probability Bob gets to $8 before
losing all his money if (a) he bets $1 each time, and (b) he bets, each time, as much as
possible, but not more than necessary to bring his fortune to $8.
-
Problem A5 (15 pts): Consider the following model of the spread of a disease. There are N people in the
population. Some are sick and the rest healthy.
(a) When a sick person meets a healthy one, the healthy one becomes sick with
probability p.
(b) All encounters are between pairs of persons, and all possible encounters in pairs
are equally likely.
(c) Exactly one encounter takes place per unit time.
(d) During each unit of time, each sick person recovers with probability q by
the end of that interval (but may still infect a healthy person during that interval),
independently of the length of time spent sick, or whether a sick person is encountered.
Let X_n be the number of sick persons at time n. Write down the formulas for the
transition matrix for this Markov chain and justify them.
-
Problem A6 (15 pts): Suppose you are playing in a casino, with an initial stake of k dollars, 1 <= k <= 19.
If you get down to zero, you are kicked out, and if you get to $20, you go home.
At each turn, you either win a dollar or lose a dollar, with the probability of
winning equal to 1 - m/20 if you have m dollars at that moment. Determine the probability of
leaving the casino with $20 in your pocket for each k, without using the matrix
algebra machinery of Markov chains.
-
Material to be covered the week of Nov 18: Chapter 6.
-
Due Thu Nov 21:
-
Textbook exercises 2 (10 pts), 4, 8, 10, 12, 14, and 16 (15 pts).
-
Extra credit problem (25 pts): Consider the Monty Hall problem (Example 3.8 in the book),
but with a twist. By collecting statistics, you discover that the random number generator
used to select the door behind which the car is placed is faulty, so that it is placed
behind door 1 with probability alpha, behind door 2 with probability beta, and behind
door 3 with probability gamma, where alpha > beta > gamma. Hence if you went on the
show, and had to choose a door, door 1 would be the obvious choice. But suppose
that you know that after you choose a door, Monty Hall will give you a choice.
He will open a door that has a goat behind it (and if both of the doors that you
have not selected have goats behind them, he will choose one at random), and offer
you a chance to switch from your choice to the other door that is still unopened.
What door should be your first choice?
-
Due Thu Dec 5 (some depend on techniques to be discussed in class on Tue Dec 3:
-
Textbook exercises (all from Chapter 6): 4, 6, 12, 14, 16, 18, 22, 26, 38, and 44 (10 pts each).
-
Extra credit problem (20 pts): Show that if X and Y are random variables, each of which takes
on only two values, then E(XY) = E(X) E(Y) implies that X and Y are independent.
-
Thu Dec 5: Last regular class. Class evaluation forms will be handed
out to be completed after the (shortened) lecture.
-
Tue Dec 10: 3rd midterm.
-
Same rules as on other exams: open book, ..., 100 minutes.
- Material to be covered on midterm: Chapters 5 (very lightly, only to the extent we covered it in class, so
basically sections 5.1 and 5.2, but you should look over the others at least briefly) and 6.
Up [
Return to home page
]