Thursday, January 21, 2016


This is the second year in a row that I've seen an article decrying our collective cyber stupidity because of the awful passwords we use to protect ourselves. And this is the second year in a row that I've rolled my eyes very hard at the article because of its mathematical ignorance. This is the first year I've decided to blog about it, though.

The article linked to above lists the most popular passwords found in databases of stolen passwords. At the top of the list are groaners such as "password", "123456", and “qwerty”. How could those be the most popular, when everyone knows China is hacking its way into our country and we're using passwords to protect our finances, identities, and porn habits? How could everyone be so stupid?

Well, the truth is, very few people have to be stupid for those passwords to be the most popular. In fact, there's an easy to imagine scenario in which no one is so cyber-challenged. Let's see how.

The most popular password is the one that gets used more than any other individual password. This doesn't mean it's used by a majority of people, obviously, just as Donald Trump isn't supported by a majority of Republicans. Additionally, when we're ranking password popularity, we're doing so by login rather than by person, because that's how the data comes to us. So password popularity is measured as logins/password.

And what's being railed against in the above article is that the passwords with the highest login/password are bad ones. But what makes a password bad? Ease of guessing--those that take the least time to crack are the least secure.

This quality is quantified in a password's information entropy, which is a measure of the number of bits needed to specify the password. In other contexts, a piece of data's information entropy tells you how much that data can be compressed. The higher the entropy, the more bits needed to specify the data, the fewer bits you can get rid of and still preserve it.

When I think entropy, I think physics. Most people probably do, too, knowing it has something to do with thermodynamics and disorder. You probably know the second law of thermodynamics, which is usually stated as something like, "The entropy (disorder) of a system tends to increase."

The "tends to" there indicates that this is a probabilistic law. That is, if you have a box with octillions of gas molecules all bouncing around at different speeds and directions, it's hard to say exactly what they're going to do, but you can say what they're likely to do. And it turns out that a box of gas is more likely to go to a high entropy state than a low one. The reason is that there are many more high entropy states than low ones available.

This is where the connection to disorder comes in. The canonical example is probably an egg. An intact egg is a very ordered thing. It has a specific shape, and you can't change the shape of the egg without changing the fact that it's an intact egg. Thus order means low entropy, because there are only a small number of ways for an egg to be an egg.

Scrambled eggs, on the other hand, are disordered and high entropy. The high entropy results from the fact that you can rearrange your egg particles (eggs are made of egg particles, right?) in many, many different ways but still end up with the same basic breakfast: scrambled eggs.

How does this connect back to information and passwords? Because as the entropy of a system increases, it takes longer and longer to accurately describe the system in detail. With low entropy, high order systems, there might be one law of nature telling you why the system is shaped the way it is, which means it's easy to specify it in detail. But with a high entropy system, there are many microstates that are approximately the same, so you need to be more and more detailed if you want to specify a particular one. "No, the one with particle 1,036,782,561 going this way, not that way."

So high entropy data doesn't compress as easily because there are many high entropy systems, which means it takes a lot of bits to differentiate between two chunks of data. And this is also why high entropy passwords are more secure: because if you're randomly guessing a password, it takes you much, much longer to get through all the available high entropy passwords than it does the low entropy passwords.

But that's also why the least secure passwords will always be the most popular ones. Compared to the secure passwords, there just aren't that many bad passwords out there, because bad passwords are low entropy. The login/password for bad passwords is going to be high essentially by definition. Here's a toy model to demonstrate.

Mathematically, the entropy of a system (s) is proportional to the log of the number of microstates (n) that correspond to a single macrostate. Computer people like to do things in binary, so they use a log base of two: S = log2(n). Now let’s take some real data and see what we find. Using this website, I have found the entropy of each of the 25 most popular passwords. Their average entropy is 20.12. Using my password manager, I've found the average entropy of 10 randomly generated strong passwords (I got lazy, but the variation in entropy was low): 80.84.

So the average good password is ~4 times as strong as the average bad password. If we assume there are only 25 bad passwords (there are many more, but more makes the point even stronger), and that the population of logins (p) uses either good passwords or bad passwords, we can write an expression comparing password popularity (logins/password). For our model, let’s see what it would take for good passwords to be just as popular as bad passwords:

pbad/nbad = pgood/ngood

How do the number of good passwords compare to the number of bad ones? Well, from the log formula up there, if we multiply the strength of a bad password by 4, we get 4S = 4log2(n). From the rules of logs, we can take that 4 on the outside of the log and bring it in: 4S = log2(n4). So if you have n bad passwords, then you have n4 good passwords.

pbad/nbad = pgood/nbad4

Solving for the ratio of logins using bad passwords to good, we get:

pbad/pgood = 1/nbad3

Now let’s plug in nbad = 25.

pbad/pgood = 1/15625 = 0.000064

This means that as long as more than 0.0064% of all logins use bad passwords, they will be the most popular. Stating the converse, 99.9935% of all logins can use strong passwords, and the bad ones will still be more common.

Of course, in the real world, there are more than 25 bad passwords (and waaaay more than 254 good passwords), and people aren't divided up into binary good and bad password users. But I think this demonstrates that very few people need actually be stupid for the above article to be true.

And as I said, it's possible that no one is stupid because this is based on logins rather than users. All it takes is that more than 0.0064% of the time you need to pick a username and password for a site, it's a site for rating cat videos and you rightly don't care about security.

Tuesday, January 19, 2016

Quantifying Weirdness

Quantum mechanics is weird; there's no doubt about that. It’s got wave-particle duality, the uncertainty principle, and spooky action at a distance. Other fields have weird results, too, but although we might comment on the peculiarity of a particular finding, we do not indict other fields as a whole. With quantum mechanics in particular, though, it seems like its idiosyncrasies leave people with the feeling that it is either too weird to be right or too weird to be understood.

Well, today I'd like to help dispel those attitudes, particularly the first one—or at the very least put a number on just how weird quantum mechanics is. To do so, I'm going to be regurgitating material I learned in my philosophy of physics course.

In order to quantify the weirdness of quantum mechanics, we'll be exploring the phenomenon of quantum entanglement. Hopefully, we'll be able to unravel some of its mysteries and not get caught in a web of confusion.

I'm sorry, I promise there will be no more entanglement puns.

Entanglement first gained widespread awareness in physics after a 1935 paper by Einstein, Podolsky, and Rosen, henceforth known as the EPR paper. Einstein was unhappy with how that paper turned out, but he articulated his thoughts more clearly to his colleagues (especially Schrodinger) in private. Additionally, the thought experiment proposed then was more complicated than it had to be. The upshot is I'll be talking about this from a slightly more modern perspective; but historically, the EPR paper is one of the jumping off points for discussing quantum funny business.

So here's entanglement. In quantum mechanics, particles like electrons are described by a wave function which tells you the probability of finding the electron in a particular state. One such state is spin which, because of weird quantum mechanical reasons, can be either up or down. So the wave function could say there's a 50% chance the spin is up and a 50% chance it's down, for example.

You won't know what the spin is until you measure it. When you do so, the language is that the wave function “collapses,” so now it's just in one state, either up or down, instead of a superposition of both.

If two electrons are hanging out, normally you have two wave functions to keep track of. But if two electrons get created together in a particular process, then they will be described by a single wave function. Once that happens, barring interference from the outside world, it is not possible to decompose that wave function into two separate ones.

Where before your wave function for a single electron said there was a 50/50 chance of spin-up or spin-down, now it might say something like there is a 50% chance that electron A is spin-up and electron B is spin-down, and a 50% chance that electron A is spin-down and electron B is spin-up. So if electron A is in your lab, and electron B is down the road at the chemist, and you measure electron A to be spin-up, then you know the wave function has collapsed to "A up, B down." This means you also know, without having measured it, that electron B is now spin-down. If you do later measure it, you will always find it to be spin-down if A was up.

Here's where things get weird. Again, as long as you prevent your electrons from being interfered with, they remain entangled until you measure the spin of one of them, no matter how far apart the electrons get. So if electron A is in your lab, and you send electron B to Alpha Centauri, when you measure the spin of electron A, you instantly know, across a distance that would take light 4 years to travel, what the spin of electron B is.

This is weird.

Here's another scenario. This one is totally going to blow your mind. Imagine you are playing a game with a street magician. He's got two hands and one coin. While your back is turned, he puts the coin in one of his hands and then asks you to guess where the coin is. There's a 50/50 chance for either hand. You say left hand. He opens, and reveals that there is no coin there.

Now here's the wacky part. Assuming the magician exhibits no trickery and that the coin is in one of his hands, you now know, as if by magic, that the coin is in his right hand. Even if the magician performs some real magic and sends his right hand to Alpha Centauri after hiding the coin, you know instantly, across a distance that would take light 4 years to travel, that the coin is in his right hand. Information has traveled faster than light—a clear violation of Einstein's special relativity!

Okay, no matter how hard I try, I can't make that second scenario sound as weird as the first one. But why not? Because you're saying, “Silly Ori Vandewalle (if that even is your real name), nothing spooky is going on here. The coin's location is a result of the magician's actions before the hands are separated. Revealing the hand doesn't decide the fate of the coin. Duh.”

This is essentially the argument that Einstien made in the EPR paper. If two electrons are entangled, and one of them is sent to Alpha Centauri, and measuring the spin of one tells you the spin of the other, then the only reasonable conclusion you can draw is that the spins were determined beforehand.

The name of the EPR paper is, "Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?" Following Betteridge's law, Einstein posited the answer was no. That's because quantum mechanics can only tell you the probability of the electron's spin being up. But just as with the magician's coin, Einstein argued, this probability represents nothing more than our ignorance, not any actual indeterminacy on the part of the coin or the electron.

So is the weirdness gone?

Well, let's see if we can't make this spooky action even more mundane. Another way to think of this result is that the two electrons are correlated. If two objects are correlated, they have a common cause. A caused B, or B caused A, or C caused both A and B. So we are suggesting that some common cause configured both spins beforehand but didn't bother to tell the wave function this.

In the 60s, physicist John Stewart Bell developed a theorem that must be true about any three binary properties of a single system. This theorem tells us something important about common causes. There are a few assumptions that go into the theorem, the most relevant of which is that, once you measure property A, that measurement can't affect properties B and C before you measure them.

Let's go through Bell's theorem with cookies so that I can distract you from the fact that we're doing math.

By Kimberly Vardeman from Lubbock, TX, USA (Perfect Chocolate Chip Cookies) [CC BY 2.0], via Wikimedia Commons
Say you've baked a batch of cookies, and the cookies can be large or not large (L, ~L), have walnuts or no walnuts (W, ~W), and have chocolate chips or no chocolate chips (C, ~C). Now say you want to know how many large, non-walnut cookies you have. We'll call that N(L, ~W). This number is the sum of all large, non-walnut, chocolate chip cookies N(L, ~W, C) and all large, non-walnut, non-chocolate chip cookies N(L, ~W, ~C). This must be true, because whether or not a cookie has chocolate chips does not affect its size or walnut content.

Similarly, the number of cookies with walnuts but no chocolate chips is N(L, W, ~C) + N(~L, W, ~C) because size doesn't matter. And finally, the number of large, non-chocolate chip cookies is N(L, W, ~C) + N(L, ~W, ~C) because walnuts don't matter.

Now let's add together the number of large, non-walnut cookies and the number of walnut cookies with no chocolate chips. That quantity is:

N(L, ~W, C) + N(L, ~W, ~C) + N(L, W, ~C) + N(~L, W, ~C)

If you notice, the second and third terms are also the terms for the number of large, non-chocolate chip cookies. That means our sum is always at least as great as the number of large, non-chocolate chip cookies.

Now let's make a slight shift and talk instead about probabilities. If you randomly reach out for a cookie, the probability that you get a particular one is directly proportional to the number of that cookie there is to take. This means we can reword Bell's cookie theorem thusly:

The probability of choosing a large, non-walnut cookie or a walnut, non-chocolate chip cookie is always greater than or equal to the probability of choosing a large, non-chocolate chip cookie.

This theorem is true regardless of how many of each cookie there actually is, because at no point in demonstrating this did we use numbers. It's also true no matter what kinds of properties we're talking about, so long as they are binary properties, because we could just as easily say L stands for lemon cookies or even something non-cookie-related.

But what's more, this theorem tells us about correlations. You see, if I give instructions to a thousand people to bake exactly the number of cookies I say and have each person randomly select and eat one cookie, we'll find that Bell's cookie theorem holds true. The probabilities will be maintained across all kitchens, because the cookie batches are correlated--spooky baking at a distance. The correlation is a result of the common cause known as me giving out instructions.

Now let's switch gears and talk about sunglasses—or as I prefer to call them, quantum shields. Polarized sunglasses only admit light that oscillates in a particular direction (up and down or left and right, for example). If you have horizontally polarized sunglasses, then only light waving from left to right (from the frame of the frames) will get through. But light coming from the sun is equally likely to be waving in any direction, so if you think about it, polarized sunglasses should only let a tiny, infinitesimal amount of light through—only light that is exactly horizontal and nothing at any other angle. Yet this isn't what happens. Polarized sunglasses will absorb roughly half the incident light and let the rest pass. Why is that?

Well, let's talk about the quanta of light, photons. A single photon doesn't have a direction it's waving, but it does have a polarization that is based on its spin. When a photon passes through sunglasses, the photon's spin is measured by the polarizing filter. Before the measurement, it's in a superposition of horizontal and vertical spin based on the angle of its spin (the direction it's waving).

When it's measured, that superposition collapses so that its spin is either horizontal or vertical. If it ends up being horizontal, it passes through. Otherwise, it's absorbed. The closer the angle of its spin is to horizontal, the higher the probability that it collapses to a horizontal spin. In this way, light from any polarization (except exactly vertical) can pass through, but the odds of it doing so go down the further away from horizontal you get, and anything that does pass through will subsequently be measured as horizontal. So sunglasses are quantum shields.

"Oakley half wire" by Jpogi at Licensed under Public Domain via Commons
This probability of getting a particular spin works for electrons, too, such as the two entangled ones in our EPR thought experiment. Instead of a polarizing filter, we use magnets to measure an electron’s spin. Before we talked about a 50/50 chance of an electron being up or down, but these odds can be adjusted by rotating our magnets in exactly the same way that light waves rotated away from horizontal have different odds of passing through sunglasses.

But this adds a new wrinkle to our thought experiment. Before, getting a spin-up on Earth meant the Alpha Centauri electron would be spin-down 100% of the time. If we rotate the Earth magnet by some angle θ, then that perfect correlation stops being 100%. It turns out that the odds of one being spin-up and the other spin-down are equal to cos2(θ/2), where θ is the angle between the two magnets.

We can carry out this experiment many times, creating entangled electrons and sending them to Alpha Centauri. A third of the time, we can measure with one magnet oriented at 0 degrees and the other at θ degrees clockwise, a third with one θ degrees and the other φ degrees, and a third with one 0 degrees and the other φ degrees. In this way, we are measuring three different binary properties of the system. Bell's theorem applies.

An entangled pair can be spin-up at 0 degrees and spin-down at θ degrees, spin-up at θ degrees and spin-down at φ degrees, or spin-up at 0 degrees and spin-down at φ degrees.

Bell's theorem tells us, then, that P(θ) + P(φ-θ) >= P(φ). Using the cosine formula up there, this comes out to cos2(θ/2) + cos2([φ- θ]/2) >= cos2(φ). Okay. Looks fine.

Except this isn't always true, depending on the angles you pick. Sometimes, the left-hand side will be less than the right-hand side. If you subtract the right from the left, then whenever Bell’s inequality is violated, the expression will be negative. You can see when that happens in this graph.

I am a Matlab Master.
So what does it mean for Bell’s inequality to be violated? Well, in the case of our cookies, the correlation was upheld because I sent out a common set of instructions to all the bakers. This is the common cause of the correlation. We saw that this common cause would lead to adherence to Bell's inequality for any set of three, binary properties of a system. This means that a common cause cannot be the origin of the correlation between entangled electrons. They aren’t deciding their configuration beforehand.

What Bell's theorem does permit is a non-local connection—the electrons instantly updating each other on their spin, or electrons that are governed by interactions across all of space. The other usual possible explanation for EPR and Bell is that electrons don't have any intrinsic reality, that realism itself is a foolish idea. No one likes either of these possibilities.

There are alternative ways of deriving, formulating, and generalizing Bell's theorem. When you do so via the CHSH inequality, you find that classical correlations can be no higher than 2. But quantum correlations violate this limit and can be as high as 2√2. And yet we can imagine other correlations, such as the Popescu-Rohrlich box, that are even higher than 2√2—correlations that you cannot reach even with entangled, non-local/non-real electrons.

So quantum mechanics is weird. But it's only weirder than regular spooky action at a distance by a factor of √2, or ~41%. Although √2 is irrational, so maybe quantum mechanics is unreasonably weird.

Thursday, January 7, 2016

Red vs. Blue

Sorry, but this post is not about the Halo-based web series. It's also not about quantum physics, like I suggested last time, except insofar as everything in the physical world is about quantum physics. Instead, this post is about my Hanukkah gift this year, a page-a-day calendar based on the show Are You Smarter Than a 5th Grader? Apparently my parents weren't sure I'd been learning anything this past semester and wanted a way to test me. Well, let's take a look at the Jan 4 entry.

Don't sue me, Fox, I guess?
First, let me be an astronomical pedant. Except for weird objects, stars are classified as either dwarfs or giants. Our sun is a yellow dwarf, and it's not clear that we should classify it as regular. There are many more small stars than big stars in the universe, with the consequence being that most stars are red dwarfs. That makes the sun more massive than most stars. On the other hand, stars can get a lot bigger than ours, both in terms of mass and size. So from that perspective, our sun is very small compared to what can exist. Does that make it a regular star? That question gets a shrug from me. But it's certainly not true that the sun is representative of stars in general.

Now, on to the question itself. The answer is that blue giants are the hottest. I suspect this is supposed to be something of a trick question. In everyday life we associate blue with cold and red with hot, but the exact opposite relation is true for hot, dense objects; red is relatively cool, blue hot. Why this discrepancy exists has to do with what color is really all about.

In general, there are three sources for the colors of objects: thermal radiation, reflection/absorption, and atomic spectra. That first one is the reason why blue stars are the hottest. Or rather, it's why the hottest stars are blue. Anything with a temperature emits a spectrum of radiation based on that temperature.

By Darth Kule (Own work) [Public domain], via Wikimedia Commons
This Planck spectrum has a peak wavelength inversely proportional to temperature, so the hotter an object is, the shorter its peak wavelength. Blue is a shorter (more energetic) wavelength of light than red is, so hot objects emit more blue light than red light.

For humans and most other room-temperature objects, the peak wavelength is in the infrared, which our eyes are not sensitive to. Everyday objects do emit some visible light, but as you can see from the Planck spectrum, the intensity drops off very quickly to the left of the peak, so our thermal emissions are essentially invisible to us.

Where we are most likely to encounter visible thermal radiation, not counting the sun, is the stovetop. Heat a piece of metal up to a few hundred degrees and it will start to glow red. Since it is difficult for us to achieve higher temperatures in everyday situations, this is probably where our sense of what hot looks like comes from. Compared to the most massive stars, a heating element is downright chilly, but it's much hotter than we are, so red = hot. Other Earthly examples include hot coals and lava (and some of the color of fire, with the rest coming from emission lines).

As far as why we associate blue with cold, the most likely explanation is that water and ice are blue-tinted. Another possibility is that blue is simply the opposite of red in our brain, but for the purpose of making this blog post longer, let's go with the first explanation.

The ocean is not blue because the sky is (nor is the sky blue because the ocean is). The ocean is blue because water preferentially absorbs red light and reflects blue light. The reason water in a cup is clear is because water transmits almost all light that touches it, but the light it does not transmit is either absorbed or reflected. So with small quantities of water, there is not enough reflection to notice. For an ocean, it's unavoidable.

Reflection and absorption account for nearly all the color we ordinarily see. The details of why objects reflect or absorb particular wavelengths turn out to be pretty complicated and not reducible to a clever function or graph. However, there are some relatively simple examples that demonstrate the importance of wavelength when it comes to the behavior of light.

The most obvious example is the blue sky. The sky is blue due to a process known as Rayleigh scattering. Rayleigh scattering occurs when the wavelength of light is significantly bigger than the particles that light is striking. In that case, the light is either transmitted or scattered, and the probability of scattering is inversely proportional to the 4th power of the wavelength. This means light at the blue end of the spectrum can be scattered up to 9 times as much as light at the red end (700 nm/400 nm)4.

When light is scattered, it bounces off the particle it strikes in a random direction. Eventually, this light will scatter such that it gets to your eye, but by then it's not likely to look as if it was coming from the source. So when we look at the sky, we see the sun no matter what direction we look. The difference is that the red and yellow light of the sun comes directly to us while the blue light bounces around a bit first.

When particle size gets much bigger, as happens for the complex molecules that make up people, shirts, and paint, the size and shape of the molecule plays a much more important and complicated role in which wavelengths get absorbed, transmitted, or scattered.

The final source of color is atomic spectra, which we observe as either emission or absorption lines. Each element on the periodic table is composed of electrons in orbit of a nucleus. The orbits an electron is allowed to have are prescribed by the number of protons, neutrons, and electrons present and the rules of quantum mechanics.

To occupy a particular orbit, an electron must possess a particular energy. If that electron moves from a high energy orbit to a low energy orbit, conservation of energy says it must release energy equal to the difference in energy levels between the two orbits to account for the transition. This energy is released in the form of a photon--light. The wavelength of that photon, and consequently the color, is inversely proportional to its energy. So big jumps produce energetic, blue photons, whereas small jumps produce red photons. (Gamma ray photons and radio wave photons and any other kind of photon are also possible depending on the energy levels involved.)

This process works in reverse, too. If light with enough energy to effect a jump hits an electron, then the electron absorbs the light and goes from a low energy to a high energy orbit.

Because these transitions only occur at specific wavelengths, we see these as emission and absorption lines rather than the spread out thermal spectra that hot objects produce. On Earth, the most common example of an emission line is a neon sign. An electric current passes through a gas, such as neon, exciting the electrons in the gas. When the electrons come down from their excited energy levels, they emit photons of a particular wavelength, giving off their characteristic orange-red glow.

There's not a great example of absorption lines on Earth that I'm aware of, but a particularly stunning example is the sun. While the sun has a nearly perfect blackbody spectrum, if you spread out its light with a spectrograph, you will notice gaps of color. These gaps are absorption lines and represent all the elements in the sun's outer photosphere (as well as some in our atmosphere, depending on where you take the light from), which is colder than the rest of the sun and absorbs light that passes through on its way to us.

Source: Nigel Sharp, National Optical Astronomical Observatories/National Solar Observatory at Kitt Peak/Association of Universities for Research in Astronomy, and the National Science Foundation. Copyright Association of Universities for Research in Astronomy Inc. (AURA), all rights reserved.
I feel it would be disingenuous of me to finish up here without noting that all of these sources of color are more connected than my discrete categorization would lead you to believe. Ultimately, light is emitted whenever an electric charge is shaken up. This is happening with thermal radiation in a messy, smeared out way and atomic spectra in a precise, limited way. And when light is absorbed or reflected by a surface, the ultimate reason is that quantum mechanical electronic energy levels are being messed around with, just like in atomic spectra. The difference is the former is much harder to calculate via quantum mechanics, so instead we label it with a simple refractive index that varies based on wavelength and is derived from observation.

Anywho, that's all for now. And I didn't even touch on how the physics of color interacts with the biology of sight, which is also a fascinating subject. Next time, quantum physics. Unless I detour into my calendar once again.