CARR, ETHAN, WILCOX, ASHLEY, DU, YISHUAI, Law of Large Numbers LEE, MICHAEL, KIM, KUMBEE, HEALY, SHANE, Elementary Combinatorics DAVID, MARIA, YU, CHENG, NOVOZHENYA, MARIA, Birthday problem FAWSON, JUSTIN, SAUCEDO, DANIEL, WANG, SHAOBO, Central limit theorem BRIGGS, NATHAN, STANLEY, BRANTON, HENRY, TY, Percolation CHILCOTE, DAVID, KIM, BONGKYUM, RASMUSSEN, MISTY, Monty Hall MCDONOUGH, JERAMIE, PARROTT, JONATHAN, MOORE, GRAYSON, Branching processes SWINDELLS, RYAN, BUTLER, NICHOLAS, WEBB, LIJUN, LIU, JIAQI, central limit theorem Neville, Scott, WILLIS, TRISTAN, DONG, RUNZHI, Infinities Yue Gao, LEIRO, JULIAN, BLACKLEY, BRANDON, Entropy of passwords
Mar 11 Send me a list of three topics in order of preference by Fri Mar 11. Groups will be assigned by then.
Mar 30 Latex class after quiz.
May 4 Due at the end of exam week. See below for submission details.
Monty Hall Problem Prove the monty hall problem by running a simulation. I suggest showing this by simulating several runs of the Monty hall show with different strategies and see what strategy does best.
Entropy of passwords. How do you make a strong password? Write a program that accepts a password of length $n$ containing only letters of the alphabet. Then write an algorithm to crack a password of length $n$. How does the running time change as you increase $n$. Run it for $n=1,2,3,4,5$.
Elementary combinatorics Write a program to take a list of students of length $n$ (a list of integers $1,\ldots,n$ or a list of names), and randomly divide them into groups of $k$. The program must print out all the groups of size $k$. Consider scenarios like if $k$ does not divide $n$ and so on. I wrote a simple program like this to divide you guys into groups. How fast is your algorithm? How random is it?
Birthday problem Suppose you have $n$ kids in a classroom, find the probability that any two of them have the same birthday. Plot this as a function of $n$. Assume that birthdays are uniformly distributed over the days of the year.
Now, find the actual distribution of birthdays of the US population from a reasonable source of data. What does the distribution look like? Can you explain it? Recalculate the probability that any two people have the same birthday as a function of $n$, the number of people in the room.
Weak law of large numbers Write down a proof of the weak law of large numbers. Suppose $X$ is a random variable, with mean $\mu$ and variance $\sigma$. Let $S_n = \sum_{i=1}^n X_i$, where $X_i$ are iid copies of $X$. Prove that for any $\e > 0$,
Central limit theorem (One of the most significant and foundational results in probability) Give me one proof of the central limit theorem. Suppose $X$ is a random variable, with mean $\mu$ and variance $\sigma$. Let $S_n = \sum_{i=1}^n X_i$, where $X_i$ are iid copies of $X$. Prove that for any $\e > 0$,
You may take this in any direction you want. You can do interesting applications of the central limit theorem, different methods of proof, comment on the universality of the normal distribution and so on.
Infinities. (Interesting, exploratory) How many different types of infinity are there? Research, for example, the difference between countable infinity and uncountable infinity and prove the Cantor diagonal argument for me.
Measurability. (Interesting but a little advanced) There is a theorem in math called the Banach-Tarski paradox. It says the following:
The Banach–Tarski paradox is a theorem in set-theoretic geometry, which states the following: Given a solid ball in 3‑dimensional space, there exists a decomposition of the ball into a finite number of disjoint subsets, which can then be put back together in a different way to yield two identical copies of the original ball. Indeed, the reassembly process involves only moving the pieces around and rotating them, without changing their shape. However, the pieces themselves are not “solids” in the usual sense, but infinite scatterings of points. The reconstruction can work with as few as five pieces.
This is because, loosely speaking the pieces or sets we break the solid balls into must be nonmeasurable. That is, they cannot have a notion of volume associated with them.
So explain what measurability means in probability theory, state a theorem or two, and tell me what probability has to do with the Banach-Tarski paradox.
Branching process and criticality. (Interesting) A branching process models the ancestory tree of an animal in a very simplistic way. It may be defined as follows see Chapter 0 of David Williams, Probability with Martingales
Let’s start with the first member of a race of animals, and call her Eve (as is conventional in the literature). If Eve has no children, then her race dies out. In fact, in any generation, everyone might have no children and the race might die out.
You have a collection of random variables that represent the number of children you’re going to have. They’re all independent and identically distributed. Call a member of this collection $X$. Assume
That is, the probability that you have no children is non-zero. Under what conditions on the distribution on $X$ does the race die out, and under what conditions does it survive?
You’re allowed to come up with your own, but run it by me first.