Facebook Birthday Problem: Part 2

Recently, I devised the following problem:

Suppose that you have n friends, and you always say “Happy Birthday” to each friend on his/her birthday. On how many days of the year will you not say “Happy Birthday” to one of your friends?

Until somebody tells me otherwise, I’m calling this the Facebook birthday problem in honor of Facebook’s daily alerts to say “Happy Birthday” to friends.

Here’s how I solved this problem. Let I_k be an indicator random variable for “no friend has a birthday on day k, where k = 366 stands for February 29 and k = 1, \dots, 365 stand for the “usual” 365 days of the year. Therefore, the quantity N, representing the number of days of the year on which no friend has a birthday, can be written as

N = I_1 + \dots + I_{365} + I_{366}

Let’s start with any of the “usual” days. In any four-year span, there are 4 \times 365 + 1 = 1461 days, of which only one is February 29. Assuming the birthday’s are evenly distributed (which actually doesn’t happen in real life), the chance that someone’s birthday is not on day k is

\displaystyle 1 - \frac{4}{1461} = \displaystyle \frac{1457}{1461}.

Therefore, the chance that all n friends don’t have a birthday on day k is

\displaystyle \left( \frac{1457}{1461} \right)^n.

Since the expected value of an indicator random variable is the probability of the event, we see that

E(I_k) = \displaystyle \left( \frac{1457}{1461} \right)^n

for k = 1, \dots, 365. Similarly, the expected value for the indicator for February 29 is

E(I_{366}) = \displaystyle \left( \frac{1460}{1461} \right)^n.

Since E(X+Y) = E(X) + E(Y) even if X and Y are dependent, we therefore conclude that

E(N) = E(I_1) + \dots + E(I_{365}) + E(I_{366}) = 365 \displaystyle \left( \frac{1457}{1461} \right)^n + \left( \frac{1460}{1461} \right)^n.

This function is represented by the red dots on the graph below.

In tomorrow’s post, I’ll calculate of the standard deviation of N.

Facebook Birthday Problem: Part 1

The “birthday problem” is one of the classic problems in elementary probability because of its counter-intuitive solution. From Wikipedia:

In probability theory, the birthday problem or birthday paradox concerns the probability that, in a set of n randomly chosen people, some pair of them will have the same birthday. By the pigeonhole principle, the probability reaches 100% when the number of people reaches 367 (since there are only 366 possible birthdays, including February 29). However, 99.9% probability is reached with just 70 people, and 50% probability with 23 people. These conclusions are based on the assumption that each day of the year (except February 29) is equally probable for a birthday.

Recently, I devised the following different birthday problem:

Suppose that you have n friends, and you always say “Happy Birthday” to each friend on his/her birthday. On how many days of the year will you not say “Happy Birthday” to one of your friends?

Until somebody tells me otherwise, I’m calling this the Facebook birthday problem in honor of Facebook’s daily alerts to say “Happy Birthday” to friends.

In this series, I will solve this problem. While this may ruin the suspense, here’s a graph of the solution for 100 \le n \le 1000 along with error bars indicating two standard deviations.

Before deriving this solution, I’ll start with a thought bubble if you’d like to take some time to think about how to do this.

Movie Magic: The Mathematics behind Hollywood’s Visual Effects

From the Mathematical Association of America’s Distinguished Lecture Series:

Applying Science to Speed Training

I enjoyed this surprising (well, surprising to me) application of exponential functions: training sprinters and other runners.

Field Guide to Math on the National Mall

For anyone visiting my old stomping grounds of Washington, D.C., this summer, the Mathematical Association of America has compiled its Field Guide to Math on the National Mall. For example:

Washington, D.C., was planned around a large right triangle, with the White House at the triangle’s northern vertex and the U.S. Capitol at its eastern vertex, linked by Pennsylvania Avenue (as the hypotenuse). A 1793 survey established the location of the triangle’s 90° vertex, and Thomas Jefferson, when he was Secretary of State, had a wooden post installed to mark the spot. This post was replaced in 1804 by a more substantial marker, which came to be known as the Jefferson Pier.

UCLA mathematicians bring ocean to life for Disney’s ‘Moana’

From the UCLA news service:

UCLA mathematicians bring ocean to life for Disney’s ‘Moana’

From the second paragraph:

“In general, the animators and artists at the studios want as little to do with mathematics and physics as possible, but the demands for realism in animated movies are so high,” [UCLA mathematician Joseph] Teran said. “Things are going to look fake if you don’t at least start with the correct physics and mathematics for many materials, such as water and snow. If the physics and mathematics are not simulated accurately, it will be very glaring that something is wrong with the animation of the material.”

I recommend the whole article.

My Favorite One-Liners: Part 96

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them.

When assigning homework or a take-home project, my students may ask what the rules are for collaborating with their peers. As a general rule, I want my students to talk to each other and to collaborate on homework, even if that opens the possibility that some student may directly copy their answers from somebody else. (I figure that if any student abuses collaboration, they will get appropriately punished when they take in-class exams.) So, when students ask about rules for collaborating, I tell them:

To quote the great philosopher, “You go talk to your friends, talk to my friends, talk to me.”

My Favorite One-Liners: Part 92

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them.

This is one of my favorite quote from Alice in Wonderland that I’ll use whenever discussing the difference between the ring axioms (integers are closed under addition, subtraction, and multiplication, but not division) and the field axioms (closed under division except for division by zero):

‘I only took the regular course [in school,’ said the Mock Turtle.]

‘What was that?’ inquired Alice.

‘Reeling and Writhing, of course, to begin with,’ the Mock Turtle replied; ‘and then the different branches of Arithmetic — Ambition, Distraction, Uglification, and Derision.’

Predicate Logic and Popular Culture (Part 123): Willie Nelson

Let M(t) be the proposition “You were on my mind at time t.” Translate the logical statement

\forall t < 0 (M(t)).

Naturally, this matches the classic song by Willie Nelson (though Elvis did record it before him).

green line

Context: This semester, I taught discrete mathematics for the first time. Part of the discrete mathematics course includes an introduction to predicate and propositional logic for our math majors. As you can probably guess from their names, students tend to think these concepts are dry and uninteresting even though they’re very important for their development as math majors.

In an effort to making these topics more appealing, I spent a few days mining the depths of popular culture in a (likely futile) attempt to make these ideas more interesting to my students. In this series, I’d like to share what I found. Naturally, the sources that I found have varying levels of complexity, which is appropriate for students who are first learning prepositional and predicate logic.

When I actually presented these in class, I either presented the logical statement and had my class guess the statement in actual English, or I gave my students the famous quote and them translate it into predicate logic. However, for the purposes of this series, I’ll just present the statement in predicate logic first.

Predicate Logic and Popular Culture (Part 122): Queen

Let p be the proposition “I cross a million rivers,” let q be the proposition “I rode a million miles,” and let r be the proposition “I still am where I started.” Translate the logical statement

(p \land q) \Rightarrow r.

This matches a line from this classic by Queen.

green line

Context: This semester, I taught discrete mathematics for the first time. Part of the discrete mathematics course includes an introduction to predicate and propositional logic for our math majors. As you can probably guess from their names, students tend to think these concepts are dry and uninteresting even though they’re very important for their development as math majors.

In an effort to making these topics more appealing, I spent a few days mining the depths of popular culture in a (likely futile) attempt to make these ideas more interesting to my students. In this series, I’d like to share what I found. Naturally, the sources that I found have varying levels of complexity, which is appropriate for students who are first learning prepositional and predicate logic.

When I actually presented these in class, I either presented the logical statement and had my class guess the statement in actual English, or I gave my students the famous quote and them translate it into predicate logic. However, for the purposes of this series, I’ll just present the statement in predicate logic first.