Skip to main content

Principle of Symmetry (Quick Note)

Pick n random points on the line (0, 1). This creates n+1 segments on the line. What is the distribution of length of the k-th segment?

Journey:
1. Try solving for the first segment.
2. Argue that the last segment has the same distribution as the first segment, by symmetry.
3. Surprise: the distribution is the same for all segments. Way to see this: instead of line, think of a circle, and argue by symmetry.


The interesting things to note:
Sometimes we can solve for simpler / extremal case, and then extend it to other cases by symmetry argument.


Application
How many cards on average need to be drawn from the deck to get an Ace?

The short answer:
Mark the top of the deck with a Joker card and arrange them in a circle. The 4As + Joker forms 5 segments on the circle. By symmetry, the length of the segments follow the same distribution and have the same average. The averages must add up to 53. So answer is 53/5.

The long answer, if we don't realise the symmetry:
Let F(t) be the probability of having to draw at least t cards from the deck before getting an Ace. Then F(t) = C(53-t, 4) / C(52, 4).

Let f(t) be the probability of having to draw exactly t cards. Then f(t) = F(t) - F(t+1).

Add t*f(t) up and telescoping we will get the answer C(53, 5)/C(52, 4) = 53/5.


Comments

Post a Comment

Popular posts from this blog

641 | 2^32 + 1

Problem: Show that \( 641 | 2^{32} + 1 \). Solution: (From Problem Solving Strategies, Arthur Engel) \( 641 = 625 + 16 = 5^4 + 2^4 \). So \( 641 | 2^{32} + 2^{28} \cdot 5^4 \). Also, \( 641 = 640 + 1 = 2^7 \cdot 5 + 1\). So \( 641 | (2^7 \cdot 5)^4 - 1 = 2^{28}\cdot 5^4 - 1 \). Hence \( 641 | 2^{32} + 2^{28} \cdot 5^4 -(2^{28}\cdot 5^4 - 1) \). QED
Post a Comment
Read more

Derive Poisson Distribution

Let's say we are observing an event that to us seems random. E.g. The number of cars passing through a road. Suppose we learn that on average, there are m cars passing the road within 1 hour. Goal: Can we make a model to suggest what is the probability of seeing exactly r cars passing the road in an hour? Let's represent one hour as a line, and on the line there are marks to represent the time on which a car passes. Let's suppose there are m marks, to represent the average case of seeing m cars on the road in an hour. Let's divide the 1 hour line into n uniform time segments, n large enough such that in one time segment there is at most 1 car. Out of the n time segments, m of them contains a car. Then it is reasonable to say that the probability of a time segment to contain a car is m/n. Let's analyse as n goes to infinity. We can say P(seeing exactly r cars in an hour) =  P(exactly r cars contained in n segments) = \( \binom{n}{r} \left( \frac{m}{n} \right)^r \left...
Post a Comment
Read more

n-th non-square

Problem: Find the n-th non-square number. (Adapted from Problem Solving Strategies, Arthur Engel ) If you have CS background, I invite you to come up with an O(log N) solution. Done? Good. Below I present the O(1) approach. Solution: The n-th non-square number is given by \( F(n) = \left \lfloor n + \sqrt{n} + 1/2  \right \rfloor \). Proof: Let G(n) be the same as F(n) except for the floor function. Investigate \( m \neq F(n) \). There is the largest \( n \) s.t. \( F(n) < m \). Hence \( m+1 \leq F(n+1) \). We conclude that \(G(n) < m \) and \(m+1 \leq G(n+1) \). Rearranging the terms and squaring the inequalities, we get: \( n < (m-n-1/2)^2 \) and \( (m-n-1/2)^2 < n+1 \), or \( n - 1/4 < (m-n)^2 - (m-n) < n + 3/4 \). Since the middle term is an integer, we see that \( (m-n)^2 - (m-n) = n \). Simplifying, we get \(m = (m-n)^2\), showing that m is a square. In other words, F(n) skips all squares. Now, we will show that F(n) is the n-th non...
Post a Comment
Read more