In this problem, we will consider Buffons Needle, but with a catch. We now drop a needle at random onto a large grid, and example of which is shown below.

The length of the needle is 1, and the space between the grid lines is 1 as well.

Recall from class that a random throw means that the position of the center of the needle and its orientation are independent and uniformly distributed.

• Given that the angle between the needle and the horizontal lines is , what is the probability that the needle does not intersect any grid lines? Justify your answer.
• Continue part (a) to find the probability that the needle, when dropped onto the grid at random (with the angle chosen uniformly at random), intersects a grid line. Justify your answer.

Hint: You may use the fact that sin cos = sin(2) without proof.

• Let X be the number of times the needle intersects a gridline (so, in the example shown above, X = 2). Find E[X]. Justify your answer.

Hint: Can you do this without using your answer from part (b)?

• Combine the previous parts to figure out the probability that X = 1, i.e. the needle will only intersects one gridline. Justify your answer.
• We will fold the needle into an equilateral triangle, where each side is length . What is the expected number of intersections that this triangle will have with the gridlines, when dropped onto the grid? Justify your answer.

2 Variance of the Minimum of Uniform Random Variables

i.i.d.

Let n be a positive integer and let X₁,,X_n Uniform[0,1]. Find varY, where

Y := min{X₁,,X_n}.

Hint: You may need to perform integration by parts.

3 Erasures, Bounds, and Probabilities

Alice is sending 1000 bits to Bob. The probability that a bit gets erased is p, and the erasure of each bit is independent of the others.

Alice is using a scheme that can tolerate up to one-fifth of the bits being erased. That is, as long as Bob receives at least 801 of the 1000 bits correctly, he can decode Alices message.

In other words, Bob becomes unable to decode Alices message only if 200 or more bits are erased. We call this a communication breakdown, and we want the probability of a communication breakdown to be at most 10⁶.

1. Use Markovs inequality to upper bound p such that the probability of a communications breakdown is at most 10⁶.
2. Use Chebyshevs inequality to upper bound p such that the probability of a communications breakdown is at most 10⁶.
3. As the CLT would suggest, approximate the fraction of erasures by a Gaussian random variable (with suitable mean and variance). Use this to find an approximate bound for p such that the probability of a communications breakdown is at most 10⁶.

4 Sampling a Gaussian With Uniform

In this question, we will see one way to generate a normal random variable if we have access to a random number generator that outputs numbers between 0 and 1 uniformly at random.

As a general comment, remember that showing two random variables have the same CDF or PDF is sufficient for showing that they have the same distribution.

• First, let us see how to generate an exponential random variable with a uniform random variable. Let U₁ Uniform(0,1). Prove that lnU₁ Expo(1).
• Let N₁,N₂ N (0,1), where N₁ and N₂ are independent. Prove that N.

Hint: You may use the fact that over a region R, if we convert to polar coordinates (x,y) (r,), then the double integral over the region R will be

ZZ ZZ f(x,y)dxdy = f(rcos,rsin)rdrd.

R R

• Suppose we have two uniform random variables, U₁ and U₂. How would you transform these two random variables into a normal random variable with mean 0 and variance 1?

Hint: What part (b) tells us is that the point (N₁,N₂) will have a distance from the origin that is distributed as the square root of an exponential distribution. Try to useU₁ to sample the radius, and then use U₂ to sample the angle.

5 Markov Chain Terminology

In this question, we will walk you through terms related to Markov chains.

1. (Irreducibility) A Markov chain is irreducible if, starting from any state i, the chain can transition to any other state j, possibly in multiple steps.
2. (Periodicity) d(i) := gcd{n> 0 |Pⁿ(i,i)=P[X_n =i|X₀ =i]> 0}, iX . If d(i)= 1 iX , then the Markov chain is aperiodic; otherwise it is periodic.
3. (Matrix Representation) Define the transition probability matrix P by filling entry (i, j) with probability P(i, j).
4. (Invariance) A distribution is invariant for the transition probability matrix P if it satisfies the following balance equations: = P.

a

1b1a

b

• For what values of a and b is the above Markov chain irreducible? Reducible?
• For a = 1, b = 1, prove that the above Markov chain is periodic.
• For 0 < a < 1, 0 < b < 1, prove that the above Markov chain is aperiodic.
• Construct a transition probability matrix using the above Markov chain.
• Write down the balance equations for this Markov chain and solve them. Assume that the Markov chain is irreducible.

6 Analyze a Markov Chain

Consider the Markov chain X(n) with the state diagram shown below where a,b (0,1).

a b

1 a

0 1 b 1 1 2

• Show that this Markov chain is aperiodic;
• Calculate P[X(1) = 1,X(2) = 0,X(3) = 0,X(4) = 1 | X(0) = 0];
• Calculate the invariant distribution;
• Let T_i = min{n 0 | X(n) = i}, T_i is the number of steps until we transit to state i for the first time. Calculate E[T₂ | X(0) = 1].

7 Boba in a Straw

Imagine that Jonathan is drinking milk tea and he has a very short straw: it has enough room to fit two boba (see figure).

Figure 1: A straw with one boba currently inside. The straw only has enough room to fit two boba.

Here is a formal description of the drinking process: We model the straw as having two components (the top component and the bottom component). At any given time, a component can contain nothing, or one boba. As Jonathan drinks from the straw, the following happens every second:

1. The contents of the top component enter Jonathans mouth.
2. The contents of the bottom component move to the top component.
3. With probability p, a new boba enters the bottom component; otherwise the bottom component is now empty.

Help Jonathan evaluate the consequences of his incessant drinking!

• At the very start, the straw starts off completely empty. What is the expected number of seconds that elapse before the straw is completely filled with boba for the first time? [Write down the equations; you do not have to solve them.]
• Consider a slight variant of the previous part: now the straw is narrower at the bottom than at the top. This affects the drinking speed: if either (i) a new boba is about to enter the bottom component or (ii) a boba from the bottom component is about to move to the top component, then the action takes two seconds. If both (i) and (ii) are about to happen, then the action takes three seconds. Otherwise, the action takes one second. Under these conditions, answer the previous part again. [Write down the equations; you do not have to solve them.]
• Jonathan was annoyed by the straw so he bought a fresh new straw (the straw is no longer narrow at the bottom). What is the long-run average rate of Jonathans calorie consumption? (Each boba is roughly 10 calories.)
• What is the long-run average number of boba which can be found inside the straw? [Maybe you should first think about the long-run distribution of the number of boba.]