20-d DMC: Expected waiting time to K successes using linearity and sums.

Описание: Foundations of Computer Science, Rensselaer Fall 2020.

Professor Malik Magdon-Ismail continues discussing the expected value with the all important expected value of a sum and linearity of expected value plus a brief discussion of the expected value of a product. We apply linearity to the expected value of dice, the Binomial and waiting time problems, including coupon collecting. We then show how to use the law of total expectation in the build-up method to computing expectations. We end with sums of indicator random variables and their application to two problems. We show that if children throw hats in the air and receive hats randomly, the expected number of kids to get their hat back is 1. We then give an interesting application to record breaking and show that the number of times the record is broken (for example a new all time high temperature) grows logarithmicaly in the number of trials (the Harmonic numbers make an appearance).

This is the twentieth lecture in a "theory" course focusing on discrete math and the foundations of computing: what can we compute and what can't we compute.

Level of the course: Sophomore Computer Science or related major.

Material is from Chapter 20 of "Discrete Mathematics and Computing", dmc-book.com.