1. Homepage
2. Homework
3. CSCI 2244 Randomness and Computation Fall 2023 - PS3: Binomial Coefficients, Random Variables and The Paradox of an Urn at Noon
This question has been solved

# CSCI 2244 Randomness and Computation Fall 2023 - PS3: Binomial Coefficients, Random Variables and The Paradox of an Urn at Noon

Boston CollegeCSCI 2244Randomness and ComputationBinomial CoefficientsRandom VariablesThe Paradox of an Urn at NoonPython

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)

2244777514300 = 2244214419441730. 777 514 300 100 100 200 214 263

Fn = P nk, here Fn is the n-th (shifted) Fibonacci number. (Hint: Recall we proved in k0 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 2k-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

1. (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 2k before noon.)

2. (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 2k minute before noon.)

3. (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.

## Get in Touch with Our Experts QQ WeChat Whatsapp
Boston College代写,CSCI 2244代写,Randomness and Computation代写,Binomial Coefficients代写,Random Variables代写,The Paradox of an Urn at Noon代写,Python代写,Boston College代编,CSCI 2244代编,Randomness and Computation代编,Binomial Coefficients代编,Random Variables代编,The Paradox of an Urn at Noon代编,Python代编,Boston College代考,CSCI 2244代考,Randomness and Computation代考,Binomial Coefficients代考,Random Variables代考,The Paradox of an Urn at Noon代考,Python代考,Boston Collegehelp,CSCI 2244help,Randomness and Computationhelp,Binomial Coefficientshelp,Random Variableshelp,The Paradox of an Urn at Noonhelp,Pythonhelp,Boston College作业代写,CSCI 2244作业代写,Randomness and Computation作业代写,Binomial Coefficients作业代写,Random Variables作业代写,The Paradox of an Urn at Noon作业代写,Python作业代写,Boston College编程代写,CSCI 2244编程代写,Randomness and Computation编程代写,Binomial Coefficients编程代写,Random Variables编程代写,The Paradox of an Urn at Noon编程代写,Python编程代写,Boston Collegeprogramming help,CSCI 2244programming help,Randomness and Computationprogramming help,Binomial Coefficientsprogramming help,Random Variablesprogramming help,The Paradox of an Urn at Noonprogramming help,Pythonprogramming help,Boston Collegeassignment help,CSCI 2244assignment help,Randomness and Computationassignment help,Binomial Coefficientsassignment help,Random Variablesassignment help,The Paradox of an Urn at Noonassignment help,Pythonassignment help,Boston Collegesolution,CSCI 2244solution,Randomness and Computationsolution,Binomial Coefficientssolution,Random Variablessolution,The Paradox of an Urn at Noonsolution,Pythonsolution,