CSCI 2244 Randomness and Computation Fall 2023 - PS3: Binomial Coefficients, Random Variables and The Paradox of an Urn at Noon
CSCI 2244.02 Fall 2023
Problem Set 3
General Instructions. The purpose for having these problem sets is to enhance your mathematics and
programming skills when it comes to the probability theory. These problems may be quite challenging,
so discussions with classmates are encouraged. However, I strongly suggest you spend at least half an
hour thinking on the problems individually before discussing. Although discussions (and consulting to
ChatGPT and WolframAlpha) are allowed, you need to write the solution using your own words by
yourself. Please acknowledge any person or references that you discuss with or consult from.
1 Binomial Coefficients (4 points)
Prove the following expressions using combinatorial reasoning (e.g. bijections). You would get only 1 point if you simply expand it into horrific equations.
2
(a) (b)
2244777514300 = 2244214419441730. 777 514 300 100 100 200 214 263
Fn = P n−k, here Fn is the n-th (shifted) Fibonacci number. (Hint: Recall we proved in k≥0 k
class that Fn is the size of the event where a coin is tossed n times but no two consecutive results are both HEAD.)
Random Variables (4 points)
Consider a random experiment where we keep tossing a fair coin until you see the third HEAD. Denote an outcome of this random experiment by a sequence (a1, a2, a3, . . .), where ai ∈ {HEAD, TAIL}. For any k ∈ {1, 2, 3}, define the random variable Xk to be the index i such that ai is the k-th HEAD in the sequence (if such an index does not exist, then Xk = ∞.)
(a) (1 point) Let t ∈ N be a positive integer. Find (and explain) the probability P (X3 = t). (b) (1 point) Let t ∈ N be a positive integer. Find (and prove) the probability P (X3 ≥ t). (c) (2 points) Find (and prove) the probability P(2X1 ≥ X2).
3 The Paradox of an Urn at Noon (The PUN, 4 points)
It’s actually called Ross-Littlewood Paradox or the balls and vase problem.
You have an empty urn and infinitely many balls. Balls are labelled by positive integers 1, 2, . . .. It’s
almost noon, and you are so boring before lunch. Thus, you would like to throw some balls into the urn and take a random ball out of the urn. In particular, for each integer k ≥ 0, you do the following at exactly the 2−k-th minute before noon:
• You throw exactly 2 balls (labelled by 2k + 1 and 2k + 2) into the urn.
• You then grab exactly one ball uniformly at random from the urn, and throw it away.
1
CSCI 2244.02 Fall 2023 PS3 Instructor: Shang-En Huang
-
(a) (2 points) Show that at any moment prior to noon, the urn is non-empty. In particular, the number of balls in the urn actually increases to infinite as the time approaches noon. (Hint: for each integer k ≥ 0, find the number of balls that stay in the urn at time 2−k before noon.)
-
(b) (2 points) Show that for any particular ball labelled with t ∈ N, the probability that this ball will be thrown away by noon is 1. (Hint: for any integer k ≥ ⌊(t − 1)/2⌋, find out the probability that ball t stays in the urn at 2−k minute before noon.)
-
(c) (0 points) Both part (a) and part (b) are mathematically well-defined. However, they send you different messages about whether the urn is empty at noon. What do you think?
Weekly Quiz 3 (4 points)
Please complete weekly quiz 3 on Canvas.
Programming Assignment 3: Balls and Urns (4 points)
Please complete PA3.ipynb and submit it to Canvas.
2
