The minimal effort explanation of quantum computing

Quantum computing is really complicated, right? Far more complicated than conventional computing, surely. But, wait. Do I even understand how my laptop works? Probably not. I don’t even understand how a doorknob works. I mean, I can use a doorknob. But don’t ask me to design one, or even draw a picture of the inner mechanism.

We have this illusion (it has the technical name in the illusion of explanatory depth) that we understand things we know how to use. We don’t. Think about it. Do you know how a toilet works? A freezer? A goddamn doorknob? If you think you do, try to explain it. Try to explain how you would build it. Use pictures if you like. Change your mind about understanding it yet?

We don’t use quantum computers so we don’t have the illusion we understand how they work. This has two side effects: (1) we think conventional computing is generally well-understood or needs no explanation, and (2) we accept the idea that quantum computing is hard to explain. This, in turn, causes us to try way too hard at explaining it.

Perhaps by now you are thinking maybe I don’t know how my own computer works. Don’t worry, I googled it for you. This was the first hit.

Imagine if a computer were a person. Suppose you have a friend who’s really good at math. She is so good that everyone she knows posts their math problems to her. Each morning, she goes to her letterbox and finds a pile of new math problems waiting for her attention. She piles them up on her desk until she gets around to looking at them. Each afternoon, she takes a letter off the top of the pile, studies the problem, works out the solution, and scribbles the answer on the back. She puts this in an envelope addressed to the person who sent her the original problem and sticks it in her out tray, ready to post. Then she moves to the next letter in the pile. You can see that your friend is working just like a computer. Her letterbox is her input; the pile on her desk is her memory; her brain is the processor that works out the solutions to the problems; and the out tray on her desk is her output.

That’s all. That’s the basic first layer understanding of how this device you use everyday works. Now google “how does a quantum computer work” and you are met right out of the gate with an explanation of theoretical computer science, Moore’s law, the physical limits of simulation, and so on. And we haven’t even gotten to the quantum part yet. There we find qubits and parallel universes, spooky action at a distance, exponential growth, and, wow, holy shit, no wonder people are confused.

What is going on here? Why do we try so hard to explain every detail of quantum physics as if it is the only path to understanding quantum computation? I don’t know the answer to that question. Maybe we should ask a sociologist. But let me try something else. Let’s answer the question how does a quantum computer work at the same level as the answer above to how does a computer work. Here we go.

How does a quantum computer work?

Imagine if a quantum computer were a person. Suppose you have a friend who’s really good at developing film. She is so good that everyone she knows posts their undeveloped photos to her. Each morning, she goes to her letterbox and finds a pile of new film waiting for her attention. She piles them up on her desk until she gets around to looking at them. Each afternoon, she takes a photo off the top of the pile, enters a dark room where she works at her perfected craft of film development. She returns with the developed photo and puts this in an envelope addressed to the person who sent her the original film and sticks it in her out tray, ready to post. Then she moves to the next photo in the pile. You can’t watch your friend developing the photos because the light would spoil the process. Your friend is working just like a quantum computer. Her letterbox is her input; the pile on her desk is her classical memory; while the film is with her in the dark room it is her quantum memory; her brain and hands are the quantum processor that develops the film; and the out tray on her desk is her output.

David Wolfe doesn’t want you to share these answers debunking quantum avocados

Everyone knows you need to microwave your avocados to release their quantum memory effects.

Recently, I joined Byrne and Wade on Scigasm Podcast to talk about misconceptions of quantum physics. Apparently, people are wrong about quantum physics on the internet! Now, since the vast majority of people don’t listen to Scigasm Podcast [burn emoji], I thought I’d expand a bit on dispelling some of the mysticism surrounding the quantum.

Would it be fair to say quantum physics is a new field in the applied sciences, though it has been around for a while in the theoretical world?

No. That couldn’t be further from the truth. There are two ways to answer this question.

The super pedantic way: all is quantum. And so all technology is based on quantum physics. Electricity is the flow of electrons. Electrons are fundamental quantum particles. However, you could rightfully say that knowledge of quantum physics was not necessary to develop the technology.

In reality, though, all the technology around us today would not exist without understanding quantum physics. Obvious examples are lasers, MRI and atomic clocks. Then there are technologies such as GPS, for example, that rely on the precision timing afforded by atomic clocks. Probably most importantly is the develop of the modern transistor, which required the understanding of semiconductors. Transistors exist, and are necessary, for the probably of electronic devices surrounding you right now.

However, all of that is based on an understanding of bulk quantum properties—lots of quantum systems behaving the same way. You could say this is quantum technology 1.0.

Today, we are developing quantum technology 2.0. This is built on the ability to control individual quantum systems and get them to interact with each other. Different properties emerge with this capability.

Does the human brain operate using properties of the quantum world?

There are two things this could mean. One is legit and other is not. There is a real field of study called quantum biology. This is basically material physics, where the material is biological. People want to know if we need more than classical physics to explain, say, energy transfer in ever more microscopic biochemical interactions.

The other thing is called quantum consciousness, or something equally grandiose. Now, some well-known physicists have written about this. I’ll note that this is usually long after tenure. These are mostly metaphysical musings, at best.

In either case, and this is true for anything scientific, it all depends on what you mean by properties of the quantum world. Of course, everything is quantum—we are all made of fundamental particles. So one has to be clear what is meant by the “true” quantum effects.

Then… there are the crackpots. There the flawed logic is as follows: consciousness is mysterious, quantum is mysterious, therefore consciousness is quantum. This is like saying: dogs have four legs, this chair has four legs, therefore this chair is a dog. It’s a logical fallacy.

Quantum healing is the idea that quantum phenomena are responsible for our health. Can we blame quantum mechanics for cancer? Or can we heal cancer with the power of thought alone?

Sure, you can blame physics for cancer. The universe wants to kill us after all. I mean, on the whole, it is pretty inhospitable to life. We are fighting it back. I guess scientists are like jujitsu masters—we use the universe against itself for our benefit.

But, there is a sense in which diseases are cured by thought. It is the collective thoughts and intentional actions of scientists which cure disease. The thoughts of an individual alone are useless without a community.

Is it true that subatomic particles such as electrons can be in multiple places at once?

If you think of the particles has tiny billiard balls, then no, almost by definition. A thing, that is defined by its singular location, cannot be two places at once. That’s like asking if you can make a square circle. The question doesn’t even make sense.

Metaphors and analogies always have their limitations. It is useful to think this way about particles sometimes. For example, think of a laser. You likely are not going too far astray if you think of the light in a laser as a huge number of little balls flying straight at the speed of light. I mean that is how we draw it for students. But a physicist could quickly drum up a situation under which that picture would lead to wrong conclusions even microscopically.

Does quantum mechanics only apply to the subatomic?

Not quite. If you believe that quantum mechanics applies to fundamental particles and that fundamental particles make up you and me, then quantum mechanics also applies to you and me.

This is mostly true, but building a description of each of my particles and the way they interact using the rules of quantum mechanics would be impossible. Besides, Newtonian mechanics works perfectly fine for large objects and is much simpler. So we don’t use quantum mechanics to describe large objects.

Not yet, anyway. The idea of quantum engineering is to carefully design and build a large arrangement of atoms that behaves in fundamentally new ways. There is nothing in the rules of quantum mechanics that forbids it, just like there was nothing in the rules of Newtonian mechanics that forbade going to the moon. It’s just a hard problem that will take a lot of hard work.

Do quantum computers really assess every possible outcome at once?

No. If it could, it would be able to solve every possible problem instantaneously. In fact, we have found only a few classes of problems that we think a quantum computer could speed up. These are problems that have a mathematical structure that looks similar to quantum mechanics. So, we exploit that similarity to come up with easier solutions. There is nothing magical going on.

Can we use entanglement to send information at speeds faster than the speed of light?

No. Using entanglement to send information faster than light is like a perpetual motion machine. Each proposal looks detailed and intricate. But some non-physical thing is always hidden under the rug.

Could I use tachyons to become The Flash? And if so, where do I get tachyons?

This is described in my books. Go buy them.

Why are there so many symbols in math?

“Mathematics is the language of the universe.” — every science popularizer ever

I am a mathematician. In fact, I have a PhD in mathematics. But, I am terrible at arithmetic. Confused? I certainly would have been if a self-proclaimed mathematician told me that 15 years ago.

The answer to this riddle is simple: math is not numbers. Whenever a glimpse of my research is seen by nearly anyone but another mathematician, they ask where the numbers are. It’s just a bunch of gibberish symbols, they say.

IMG_20171212_090428
The whiteboard in my office on 12 December 2017.

Well, they are right. Without speaking the language, it is just gibberish. But why—why all these symbols?

The symbols are necessary because communicating the ideas requires it. A simple analogy is common human language.

Mandarin Chinese, for example, has many more like-sounding syllables than English. This has led to a great number of visual puns, which have become a large part of Chinese culture. For example, the phrase 福到了(“fortune has arrived”) sounds the same as 福倒了(“fortune is upside down”). Often you will see the character 福 (“fortune”, fú, which you pronounce as ‘foo’ with an ascending pitch) upside down. While, like most puns, this has no literal meaning, it denotes fortune has arrived.

Fudao
Fudao, CC BY-SA 3.0, https://en.wikipedia.org/w/index.php?curid=30725479

Not laughing? OK, well, not even English jokes are funny when they have to be explained, but you get the idea. This pun just doesn’t translate to English. (Amusingly, there is also no simple common word for pun in Chinese.)

The point here is that upside down 福, with its intended emotional response, is not something you can even convey in English. The same is true in mathematics. Ideas can be explained in long-winded and confusing English sentences, but it is much easier if symbols are used.

And, there really is a sense in which the symbols are necessary. Much like the example of 福, most mathematicians use symbols in a way that is just impossible to translate to English, or any other language, without losing most of the meaning.

Here is a small example. In the picture above you will see p(x|θ). First, why θ? (theta, the eighth letter of the Greek alphabet, by the way). That’s just convention—mathematicians love Greek letters. So, you could replace all the θ’s by another symbol and the meaning wouldn’t change. It’s like the difference between writing Chinese using characters or pinyin: 拼音 = pīnyīn.

You might think that it is weird to mix symbols, such as Roman and Greek, but it now very common in many languages, particularly in online conversations. For example, Chinese write 三Q to mean “thank you”, because 三 is 3 and, in English, 3Q sounds like ‘thank you”. In English, and probably all languages now, emojis are mixed with the usual characters to great effect. You could easily write, “Have a nice day. By the way, my mood is happy and I am trying to convey warmth while saying this.” But, “Have a nice day :)” is much easier, and actually better at conveying the message.

OK, so we are cool with Greek letters now, how about  p(x|θ)? That turns out to be easy to translate—it means “the probability of x given θ.” Unfortunately, much like any statement, context is everything. In this case, not even a mathematician could tell you exactly what p(x|θ) means since they have not been told what x or θ means. It like saying “Bob went to place to get thing that she asked for.” An English speaker recognises this as a grammatically correct sentence, but who is “she”, what is the “thing”, and what is the “place”? No one can know without context.

What the English speaker knows is that (probably) a man, named Bob, went to store to purchase something for a woman, whose name we don’t know. The amazing thing is that many more sentences could follow this and an English speaker could easily understand without the context. Have you ever read or listened to a story in which the characters are never named or described? You probably filled in your own context to make the story understandable for you. Maybe that invented context is fluid and changes as you hear more of the story.

The important point is that such actions are not taught. They come from experience—from being immersed in the language and a culture built from it. The same is true in mathematics. A mathematician with experience in probability theory could follow most of what is written on that whiteboard, or at least get the gist of it, without knowing the context. This isn’t something innate or magical—it’s just experience.

Quantum Physics for Babies

This talk was given at the University of Sydney School of Physics Colloquium 19 June 2017.

It’s​ great to be back here. That feels a bit awkward to say since it’s only been 6 months since I left and I’m only 10 minutes away. But King and Broadway might as well be the Pacific Ocean for academics. I’m Chris Ferrie. I’m just down the road at the Centre for Quantum Software and Information. It’s an awesome new Centre. We’re on Twitter. You should check us out.

Now, though the title of the talk doesn’t make it obvious, I am a serious, well… maybe not serious, but I am an academic. But I also have a hobby… tennis. No, I write children’s books. Yes, it is a real book. And, yes, I wrote it and self published it several years ago when I was a postdoc. Why, and how, and for what purpose, well… that is the purpose of this talk.

measure-1509707_1920Measure twice, cut once. So the old proverb goes. It certainly it makes sense if you only have enough material to build a thing. However, and I see this all too often in otherwise very smart people, too much measuring leads to over optimisation and inaction, not enough cutting. Whereas, I like cut several times, toss things out, try new cutting instruments, and so on. I almost never measure. Ultimately, this is the story of Quantum Physics for Babies. I just did it. It wasn’t carefully planned, nor was there a spark or ah-ha moment which spawned the idea. I started, I failed, I started again.

And, for better or worse, the book became popular. Journalists starting asking me, “why did you write this book?” and, more seriously, “why teach quantum physics to babies, why is that important?”

brain-2062057_1920So, I started to rationalize. Why did I write this book? And, is it important? In particular, is it important for all children, not just my own? (because it is always important to find a way to discuss your passion with your own kids.) I think the answer to “is it important?” is yes. In this talk I’ll walk you through the various levels of rationalisation I’ve went through. Each has an element of truth to it, both for myself personally and what the experts on the topic of early childhood education espouse.

But let me start at the same place I start most things, with a joke. Someone that has known me for only a short time probably wouldn’t be too surprised that I was voted “class clown” in high school. Humor plays a crucial part of almost every aspect of my life. I laugh with my partner, I laugh with my children, I laugh with my friends, and I laugh with other scientists. (Einstein didn’t think it was very funny—but, then again, he never liked quantum physics.) Happiness is the difference between your reality and your expectations. Humor often defies expectation and happiness ensues. So, hopefully you didn’t come to this talk with too many expectations and you’ll leave a little happier then when you came in. At least there’s cake.

There is no denying that I saw the irony as good for a laugh the first time the title popped into my head. Of course, the level of humour I’m talking about is not at all for the advertised audience. I’ve never seen a child laugh at the title of the book. Adults, on the other hand, love the juxtaposition of quantum physics with “for babies”. So I knew that at least a few people would buy it as a gag gift for a nerdy friend having a baby. What I didn’t expect was this nerdy friend getting a copy.

I’ve joked with various people about making other goofy “for babies” books. Why not “contract law for babies” or “geopolitical policy for babies”? Though, the only person in the world that needs to read such a book is too busy tweeting insults at women. But quantum physics—yeah—people seem to agree that is worth being more than a joke, and hopefully I knew something about it.

In the end, I put real thought and effort into the content. The goal became clear enough: how to fill a baby book out with short sentences, no jargon and a coherent description of quantum physics. It was a challenge and there is still probably room for improvement. But I’ve already had people say, “we all had a good laugh, then I started to read it and there was real quantum physics inside.” Many adults even claimed they learned something. But were the children learning?

The unanimous advice for new parents is to read to your newborn. Most say it doesn’t even matter what it is, just read. But, let’s play a little game here. Suppose a parent does read to their child and has no time to add a new book to the rotation. Then, Quantum Physics for Babies needs to replace a book. What book should it be? First, I don’t think it should replace fiction. Fiction and fairy tales serve many purposes and, besides, variety is the spice of life. So we are left with nonfiction, which for baby books is limited solely to only a few types of reference material.

Quantum Physics for Babies - Sydney Uni 19 June 2017 (1)A huge fraction of any newborn’s library will begin with the word “first”: “First Words”, “First book of numbers”, “First alphabet book”, and so on. One quickly gets the impression that these are essential reference books for the early learner. But beyond the obvious things—letters, numbers, shapes, three letter words—are a myriad of books about animals, and mostly farm animals.

Now, learning is tricky concept to define even for adults. There are numerous models of early childhood cognitive development, and so it is hard to say conclusively what is being “learned” and at what level, but something is clearly happening since every 3 year in the world knows what sound a cow makes. Do you? I think I do. But I have never heard one myself. Maybe there was a time when that was important, or at least relevant, but I don’t think that time is today.

Quantum Physics for Babies - Sydney Uni 19 June 2017 (2)Here is another example. Do you know what these birds are? My children seem to know and can identify the difference between a penguin and a puffin. Why? Why are there more books about puffins than there are puffins and no books about transistors when you are probably sitting on a billion of them right now. In your phone lives a few billion transistors making up, by the standards of only decade ago anyway, a supercomputer. A child today will probably spend their entire life closer to computer than they will an animal of comparable size. I’m not suggesting than all books on animals be replaced by physics for babies books, but we could maybe replace a few.

I won’t claim my children understand quantum physics, but they certainly understand it at the same level they understand anything else gotten from a book. They will tell you that everything in the world is made of atoms and atoms are made of neutrons, protons and electrons and electrons have energy. I think that is about the same level of understanding as being able to identify a puffin, or should I say Fratercula corniculata for the baby ornithologists in the crowd.

So it seems then that Quantum Physics for Babies is here to stay. But we’re all scientists here and we love nothing more than free cake and to categorize things. So where does Quantum Physics fit? In what aisle of the bookshop does it sit on the shelf? Well, it turns out that it has been shoehorned into the new educational buzzword de jour: STEM.

Quantum Physics for Babies - Sydney Uni 19 June 2017 (3).png

STEM (Science Technology Engineer and Mathematics) started out as an initiative to focus on its namesake topics with the goal of training a workforce ready for the careers that were assumed new technologies would create. Interestingly, the first press mention of the acronym seems to go back to 2008 when The Bill and Melinda Gates Foundation donated $12 million dollars to the Ohio STEM Learning Network, which is still going strong today. Most never looked back. [By the way, much backlash ensued over leaving out the Arts, for example. So you might see STEAM or even STREAM (Reading) out there.]

Now governments all over the world currently have numerous initiatives at all levels of the curriculum to enhance what they called STEM-based learning. This is vaguely and variably defined and can mean anything from simply having access to more technology in the classroom to the design and building of simple machines to solve practical problems. But the motivation and directives that follow are often based on decade-old studies suggesting rises in STEM-related jobs. One recent state-level education​ department cited a study with data collected prior to the release of the first iPhone (that was only 10 years ago, by the way). The often cited report of the Chief Scientist of Australia contained recommendations citing data accumulated from 1964-2005. Policy is good, but it cannot keep up with the pace of technology.

Disruption! The fear today—fueled by startups, makers, and ever younger entrepreneurs—is that we just have no idea what jobs will look like in the future. And so STEM, at least for the trailblazers, is now a movement with the audacious goal of graduating creators and innovators. We no longer want graduates who simply have more and integrated technical skills.

What does this look like? Let me give you an example. Here is Taj Parabi, now 17, CEO of his own business which ships DIY tablets. His company, fiftysix, also visits schools and puts on extracurricular workshops for students on technology and… entrepreneuring! That’s right. Your children are competing with 8-year-olds trained to be CEOs of their own companies!

On a topic near and dear to my own heart, a now veteran effort from the Institute for Quantum Computing is the Quantum Cryptography School for Young Students (QCSYS)Quantum Physics for Babies - Sydney Uni 19 June 2017 (4), which invites international high-school students for a week of intensive training on quantum technology. Indeed, many of these students eventually become PhD students in Quantum Information Theory. Other efforts include school incursions and the new QUANTUM: The Exhibition which is an all-ages, hands-on exploratory exhibit.

Quantum Physics for Babies - Sydney Uni 19 June 2017 (5)On the other side of the border (remember: the wall is on the souther border), IBM has recently released the “Quantum Experience”, an app that lets you program a quantum computer, a real quantum computer. You create an algorithm and then jump in the queue for it to run on real device housed in IBM’s labs. Here they are video conferencing with a school in South Africa and hosting local students.

So that is the tiniest snapshot of STEM education today. Is Quantum Physics for Babies on par with these efforts? Are the children learning the skills necessary to be quantum engineering start-up entrepreneurs? Of course not. Quantum Physics for Babies, at least as far as reading to actual babies is concerned, is about the parents.

20 years from now, your child might be sitting in an interview for the job of Quantum Communication Analyst or Quantum Software Engineer. How long will it be before such topics feature in the report of the Chief Scientist on the curriculum? How long before it is mainstream in public schools? I’m not holding my breath.

The problem today is that it’s impossible to keep up. Pilot studies, kids maker studios, programming toys and apps, … These are all beautiful, but the growth of STEM education has now outpaced even the technology. The curriculum cannot keep up, and so the onus of STEM education, however you want to define it, is largely on the parents.

Again, the efforts of STEM education researchers are impressive, but a parent cannot assume that their child will happen to be in the school that benefits from these one-off pilot studies or incursions. The education system in most developed countries has been too long taken for granted and is now depleted from underfunding. No doubt there are many great principals and great teachers out there. Two days from now, I’m going to go speak with a dozen principals and teachers about STEM education. But there are almost 1500 primary schools in Sydney alone (over 3000 in New South Wales). There is much that needs to be done at the larger scale—but even if I said that was being done, it is little comfort for parents today.

So—in the end—this is what I both want and expect from the book: the elimination of doubt and fear. I want quantum physics, indeed all physics and math and science, to be normal for a child to take interest in. When your child asks about going to Canada for a summer school on quantum cryptography, that should be seen as normal request. When she asks to help her set up an account for a quantum cloud computing service, you should be like, no worries I already have one.

Today, when 1 in 3 Americans would rather clean a toilet then do a math problem, when a search for “quantum physics” brings up Deepak Chopra instead of Stephen Hawking, and when the facts pointing to climate change are seen as equally compelling as a celebrity’s argument for a flat earth, we need all the help we can get. And we need to start that conversation as early as possible.

Quantum Physics for Babies was just the beginning…IMG_20170606_175007

What does it mean to excel at math?

“In mathematics you don’t understand things. You just get used to them.” ― John von Neumann

John von Neumann made important scientific discoveries in physics, computer science, statistics, economics, and mathematics itself. He was, by all accounts, a genius. Yet, here he is saying he “just got used” to mathematics. While this was probably a tongue-in-cheek reply to a friend, there is some truth to it. Mathematics is a language and anyone can eventually learn to speak it.

Indeed,balls_to_sphere mathematics is the language by which scientists of all fields communicate—from philosophy to physics. And by mathematics, I don’t mean numbers. Scientists communicate ideas through mental pictures which are often represented by symbols invented just for that purpose. Here is an example: think about a ball. Maybe it is a baseball, or a basketball, or—if you are in Europe—a socc…err… football. Maybe it is the Earth or the Sun. Now try to get rid of the details: the stitching, the colors, the size. What is left? A sphere. You just performed the process of abstraction. A sphere is an idea, a mental image that you can’t touch—it doesn’t exist!

sphere_to_ballWhy is this important, anyway? Well, if I can prove things about spheres, then that ought to apply to any ball in the real world. So, formulas for area and volume, for example, equally apply to baseballs, basketballs, soccer balls, and any other ball. Mathematics is a very powerful way of answering infinitely many questions at once!

Now, it is said that to become an expert at anything, you need 10,000 hours of practice. While not a hard-and-fast rule, it seems to work out in terms of acquiring modern language—10,000 hours probably works out to mid-to-late teens for an adept student. Usually, we don’t start practicing real mathematics until well after we have mastered our first language, in late high-school or college. Why not start those 10,000 hours now with your children?

Sounds great, but where do you start? The bad news is that there are no simple rules. The good news is that it doesn’t really matter where you start. With your children, you could practice numeracy, practice puzzles and games, read books, watch science videos, try to code, draw pictures, or just sit in a quiet room and think. As you do these things, encourage generalization and abstraction. Ask questions and let your child ask questions. The correct answers are not important—it is the process that counts.

I was asked recently to share some tips for parents who want their kids to excel at math and do well in the classroom later on. The trouble is, doing well in the classroom—that is, doing well on standardized tests—doesn’t necessarily correlate with understanding the language of mathematics. If you want to do well on standardized tests, then just practice standardized tests. However, if you want your kids to have the powerful tools of abstraction​ at their disposal and possibly also do well on tests, then teach them the language of mathematics.

The power of simulation: birthday paradox

The birthday paradox goes… in a room of 23 people there is a 50-50 chance that two of them share a birthday.

OK, so the first step in introducing a paradox is to explain why it is a paradox in the first place. One might think that for each person, there is 1/365 chance of another person having the same birthday as them. Indeed, I can think of only one other person I’ve met that has the same birthday as meand he is my twin brother! Since I’ve met far more than 23 people, how can this be true?

This reasoning is flawed for several reasons, the first of which is that the question wasn’t asking about if there was another person in the room with a specific birthdayany pair of people (or more!) can share a birthday to increase the chances of the statement being true.

The complete answer gets heavy into the math, but I want to show you how to convince yourself it is true by simulating the experiment. Simulation is programming a computer or model to act as if the real thing was happening. Usually, you set this up so that the cost of simulation is much less than doing the actual thing. For example, putting a model airplane wing in a wind tunnel is a simulation. I’ve simulate the birthday paradox in a computer programming language called Python and this post is available in notebook-style here. Indeed, this is much easier than being in a room with 23 people.

Below I will not present the code (again, that’s over here), but I  will describe how the simulation works and present the results.

The simulation

Call the number of people we need to ask before we get a repeated birthday n. This is what is called a random variable because its value is not known and may change due to conditions we have no control over (like who happens to be in the room).

Now we simulate an experiment realising a value for n as follows.

  1. Pick a random person and ask their birthday.
  2. Check to see if someone else has given you that answer.
  3. Repeat step 1 and 2 until a birthday is said twice.
  4. Count the number of people that were asked and call that n.

Getting to step 4 constitutes a single experiment. The number that comes out may be n = 2 or n = 100. It all depends on who is in the room. So we repeat all the steps many many times and look at how the numbers fall. The more times we repeat, the more data we obtain and the better our understanding of what’s happening.

Here is what it looks like when we run the experiment one million times.

exponemil
Simulating the birthday paradox. On the horizontal axis is n, the number of people we needed to ask before a repeated birthday was found. We did the experiment one million times and tallied the results.

So what do all those numbers mean? Well, let’s look at how many times n = 2 occurred, for example. In these one million trials, the result 2 occurred 2679 times, which is relatively 0.2679%. Note that this is close to 1/365 ≈ 0.274%, which is expected since the probability that the second person has the same as the first is exactly 1/365. So each number of occurrences divided by one million is approximately the probability that we would see that number in a single experiment.

We can then plot the same data considering the vertical axis the probability of needing to see n people before a repeated birthday.

prob
Same as the previous plot but now each bar is interpreted as a probability.

Adding up the value of each of these bars sums to 100%. This is because one of the values must occur when we do an experiment. OK, so now we can just add up these probabilities starting at n = 2 and increasing until we get to 50%. Visually, it is the number which splits the coloured area above into two equal parts. That number will be the number of people we need to meet to have a 50-50 shot at getting a repeated birthday. Can you guess what it will be?

Drum roll… 23! Tada! The birthday paradox simulated and solved by simulation!

But, wait! There’s more.

What about those leap year babies? In fact, isn’t the assumption that birthdays are equally distributed wrong? If we actually tried this experiment out in real life, would we get 23 or some other number?

Happily, we can test this hypothesis with real data! At least for US births, you can find the data over at fivethirteight’s github page. Here is what the actual distribution looks like.

dist_birth.png
Distribution of births in US from 1994-2014, by day of year.

Perhaps by eye it doesn’t look too uniform. You can clearly see 25 Dec and 31 Dec have massive dips. Much has been written about this and many beautiful visualizations are out there. But, our question is whether this has an effect on the birthday paradox. Perhaps the fact that not many people are born on 25 Dec means it is easy to find a shared birthday on the remaining days, for example. Let’s test this hypothesis by simulating the experiment with the real distribution of birthdays.

To do this, we perform the same 4 steps as above, but randomly sampling answers from the actual distribution of birthdays. The result of another one million experiments is plotted below.

truehist.png
Simulating the birthday paradox on the true distribution of births. On the horizontal axis is n, the number of people we needed to ask before a repeated birthday was found. We perform the experiment one million times and tallied the results.

And the answer is the same! The birthday paradox persists with the actual distribution of birthdays.

Nerd sniping

The above discussion is very good evidence that the birthday paradox is robust to the actual distribution of births. However, it does not constitute a mathematical proof. An experiment can only provide evidence. So I will end this with a technical question for those mathematical curiosos out there. (What I am about to do is also called Nerd Sniping.)

Here is the broad problem: quantify the above observation. I think there is more than one question here. For example, it should be possible to bound the 50-50 threshold as a function of the deviation from a uniform distribution.

(Cover image credit: Ed g2s, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=303792)