Tanya Khovanova's Math Blog

This is a version of the standard charades game that my son, Sergei Bernstein, invented.

Unlike in regular charades, the person who acts out the phrase doesn’t know what the phrase is and has to guess it. The viewers on the other hand, know the phrase but they are not allowed to talk.

So the actor is blindfolded and the viewers are not just watching; they are actively moving the actor and his/her body parts around to communicate the phrase. For example, if the actor is on the right track, since the viewers can’t say, “Yes, good!”, they might communicate it by nodding the actor’s head.

Sounds like fun, especially for people who enjoy touching and being touched.

Once again I am one of the organizers of the Women and Math Program at the Institute for Advanced Study in Princeton, May 16-27, 2011. It will be devoted to an exciting modern subject: Sparsity and Computation.

In case you are wondering about the meaning of the picture on the program’s poster (which I reproduce below), let us explain.

The left image is the original picture of Fuld Hall, the main building on the IAS campus. The middle image is a corrupted version, in which you barely see anything. The right image is a striking example of how much of the image can be reconstructed from the corrupted image using clever algorithms.

Female undergraduates, graduates and postdocs are welcome to apply to the program. You will learn exactly how the corrupted image was recovered and much more. The application deadline is February 20, 2011.

Eugene Brevdo generated the pictures for our poster and agreed to write a piece for my blog explaining how it works. I am glad that he draws parallels to food, as the IAS cafeteria is one of the best around.

by Eugene Brevdo

The three images you are looking at are composed of pixels. Each pixel is represented by three integers corresponding to red, green, and blue. The values of each integer range between 0 and 255.

The image of Fuld hall has been corrupted: some pixels have been replaced with all 0s, and are therefore black; this means the pixel was not “observed”. In this corrupted version, 85% of the pixel values were not observed. Other pixels have been modified to various degrees by stationary Gaussian noise (i.e. independent random noise). For the 15% observed pixel values, the PSNR is 6.5 db. As you can see, this is a badly corrupted image!

The really interesting image is the one on the right. It is a “denoised” and “inpainted” version of the center image. That means the pixels that were missing were filled in and the observed pixel integer values were re-estimated. The algorithm that performed this task, with the longwinded name “Nonparametric Bayesian Dictionary Learning,” had no prior knowledge about what “images should look like”. In that sense, it’s similar to popular wavelet-based denoising techniques: it does not need a prior database of images to correct a new one. It “learns” what parts of the image should look like from the original image, and fills them in.

Here’s a rough sketch of how it works. The idea is to use a new technique in probability theory — the idea that a a patch, e.g. a contiguous subset of pixels, of an image is composed of a sparse set of basic texture atoms (from the “Dictionary”). Unfortunately for us, the number of atoms and the atoms themselves are unknowns and need to be estimated (the “Nonparametric Learning” part). In a way, the main idea here is very similar to Wavelet-based estimation, because while Wavelets form a fixed dictionary, a patch from most natural images is composed of only a few Wavelet atoms; and Wavelet denoising is based on this idea.

We make two assumptions that allow us to simplify and solve this problem, which is unwieldy-sounding and vague when the texture atoms have to be estimated. First, there may be many atoms, but a single patch is a combination of only a sparse subset of them. Second, because each atom appears in part in many patches, even if we observe some noisily, once we know which atoms appear in which patches, we can invert and average together all of the patches associated with an atom to estimate it.

To explain and programmatically implement the full algorithm that solves this problem, probability theorists like to explain things in terms of going to a buffet. Here’s a very rough idea. There’s a buffet with a (possibly infinite) number of dishes. Each dish represents a texture atom. An image patch will come up to the buffet and, starting from the first dish, begins to flip a biased coin. If the coin lands on heads, the patch takes a random amount of food from the dish in front of it (the atom-patch weight), and then walks to the next dish. If the coin lands on tails, the patch skips that dish and instead just walks to the next. There it flips its coin with a different bias and repeats the process. The coins are biased so the patch only eats a few dishes (there are so many!). When all is said and done, however, the patch has eaten a random amount from a few dishes. Rephrased: the image patch is made from a weighted linear combination of basic atoms.

At the end of the day, all the patches eat their own home-cooked dessert that didn’t come from the buffet (noise), and some pass out from eating too much (missing pixels).

If we know how much of each dish (texture atom) each of the patches ate and the biases of the coins, we can estimate the dishes themselves — because we can see the noisy patches. Vice versa, if we know what the dishes (textures) are, and what the patches look like, we can estimate the biases of the coins and how much of a dish each patch ate.

At first we take completely random guesses about what the dishes look like and what the coins are, as well as how much each patch ate. But soon we start alternating guesses between what the dishes are, the coin biases, and the amounts that each patch ate. And each time we only update our estimate of one of these unknowns, on the assumption that our previous estimates for the others is the truth. This is called Gibbs sampling. By iterating our estimates, we can build up a pretty good estimate of all of the unknowns: the texture atoms, coin biases, and the atom-patch weights.

The image on the right is our best final guess, after iterating this game, as to what the patches look like after eating their dishes, but before eating dessert and/or passing out.

I’ve heard many fun problems in which blindfolded parachutists are dropped somewhere and they need to meet up once they’re on the ground. They can’t shout or purposefully leave traces behind. They will recognize each other as soon as they bump into each other. Their goal is to get to the same assembly point. They can design their strategy in advance.

Here is the first problem in a series that gets increasingly difficult:

Two parachutists are dropped at different locations on a straight line at the same time. Both have an excellent sense of direction and a good geographical memory, so both know where they are at any moment with respect to their starting point on the line. What’s their strategy?

The strategy is that the first person stands still and the second one goes forward and back repeatedly, increasing the distance of each leg until they collide.

In the next variation, both are required to execute the same program, that is, if one stands still, then both stand still. To compensate for this increased difficulty, they are allowed to leave their parachutes anywhere. And both of them will recognize the other’s parachute if they bump into it.

In the third variation, the set-up is similar to the previous problem, but they are not allowed to change the direction of their movement. To their advantage, they know which way East is.

I recently heard a 2-D version from my son Sergei in which the parachutists are ghosts. That means that when they bump into each other they go through each other without even recognizing the fact that they met:

Several blindfolded men are sleeping at different locations on a plane. Each wakes up, not necessarily at the same time. At the moment of waking up, each of them receives the locations of all the others in relation to himself at that moment. They are not allowed to interact, nor will they receive any further information as time passes. They need to get together in one place. How can they do that, if they are allowed to decide on their strategy in advance?

They do not know where North is. So they can’t go to the person at the most Northern point. Also they do not know how locations correspond to people, so they can’t all go to where, say, Peter is. Let us consider the case of two men. Suppose they decide to go to the middle of the segment of two locations they receive when they awake. But they get different locations because they wake up at different times. Suppose the first person wakes up and goes to the middle. The fact that he walks while the other is sleeping, means that he changes the middle. So when the second person wakes up, his calculated middle is different from the one calculated by the first person. Consequently, they will never manage to meet. Hence, the solution should be different.

Actually Sergei gave me a more difficult problem:

Not only do they need to meet, but they need to stay together for a predefined finite time period.

Here is as bonus problem.

If there are three parachutists, it is possible to end up in a meeting place and stay there indefinitely. For four people it is often possible too.

Darth Maul killed Qui-Gon Jinn. Obi-Wan Kenobi killed Darth Maul. Palpatine killed Mace Windu. Darth Vader killed Obi-Wan Kenobi and Palpatine. I am mentally drawing the kill graph of Star Wars, where people are vertices and kills are edges. The graph is not very interesting. In movies where no one gets resurrected, the kill graph is a forest.

I’m interested in studying social networks in the movies and how they differ from social networks in real life. As we saw, the kill graph is not very exciting mathematically.

Now let’s try the acquaintance graph, where edges mark two people who know each other. Unfortunately, in the movies there are often many nameless people and we learn very little about their acquaintances. On the other hand, all the “nameful” people usually know each other, thus their acquaintance graph is a complete graph. The richest acquaintance graphs would be for epic movies like Star Wars, in which the events span two generations and many planets. As a result, there are characters who never meet each other. For example, Leia, Luke and Han from the original trilogy never meet people who died in the prequel, such as Anakin’s mother and Count Dooku.

But I think that the most intriguing type of filmic social network is the fight graph, where edges represent characters who fight each other. Usually such graphs are bipartite, reflecting the division between bad guys and good guys. When an epic film is more complex and has traitors, the fight graph is no longer bipartite. Consider Darth Vader who fought and killed a lot of good guys including Obi-Wan Kenobi as well as many bad guys including Count Dooku and the Emperor.

I would like to immortalize Darth Vader in mathematics. He did restore the balance to the Force. If there is a graph which is not bipartite and can become bipartite by removing one highly connected node, I would like to name such a node Darth Vader.

Dear Nita Palmira,

I do not recall your name and I’m not sure where you got my email address from, but I really appreciate you contacting me. I am excited by your Two-Procedures-For-The-Price-Of-One offer. I am really looking forward to my enlarged penis and my DDD breasts.

Meanwhile, I can give you a unique group discount on IQ tests. I can test the IQ of all your company employees for the price of one test. Moreover, you do not need to waste even a minute. Actually, no one even needs to answer any questions. You can send me your $500 check to the address below and I will promptly send you the IQ report, the accuracy of which I can guarantee.

Sincerely yours.

I am coaching my AMSA students for math competitions. Recently, I gave them the following problem from the 1964 MAML:

The difference of the squares of two odd numbers is always divisible by:
A) 3, B) 5, C) 6, D) 7, E) 8?

The fastest way to solve this problem is to check an example. If we choose 1 and 3 as two odd numbers, we see that the difference of their squares is 8, so the answer must be E. Unfortunately this solution doesn’t provide any useful insight; it is just a trivial calculation.

If we remove the choices, the problem immediately becomes more interesting. We can again plug in numbers 1 and 3 to see that the answer must be a factor of 8. But to really solve the problem, we need to do some reasoning. Suppose 2k + 1 is an odd integer. Its square can be written in the form 4n(n+1) + 1, from which you can see that every odd square has remainder 1 when divided by 8. A solution like this is a more profitable investment of your time. You understand what is going on. You master a method for solving many problems of this type. As a bonus, if students remember the conclusion, they can solve the competition problem above instantaneously.

This is why when I am teaching I often remove multiple choices from problems. To solve them, rough estimates and plugging numbers are not enough. To solve the problems the students really need to understand them. Frankly, some of the problems remain boring even if we remove the multiple choices, like this one from the 2009 AMC 10.

One can holds 12 ounces of soda. What is the minimum number of cans needed to provide a gallon (128 ounces) of soda?

It’s a shame that many math competitions do not reward deep analysis and big-picture understanding. They emphasize speed and accuracy. In such cases, plugging in numbers and rough estimates are useful skills, as I pointed out in my essay Solving Problems with Choices.

In addition, smart guessing can boost the score, but I already wrote about that, too, in How to Boost Your Guessing Accuracy During Tests and To Guess or Not to Guess?, as well as Metasolving AMC 8.

As the AMC 10 fast approaches, I am bracing myself for the necessity to include multiple choices once again, thereby training my students in mindless arithmetic.

Many people ask me when is a good time to teach kids math. In my experience, it can never be too early. You just need to keep some order. Multiplication should be taught after addition, and negative numbers after subtraction. Kids should remember multiplication by heart at the age of seven. They can understand negative numbers as early as four.

In the picture I am explaining Platonic solids to four-month-old Eli, the son of my friends. His homework is to chew on a dodecahedron.

Suppose Romeo is encouraged by love and attention. If Juliet likes him, his feelings for Juliet grow and flourish. If she doesn’t like him, he loses his interest in her.

Juliet, on the other hand, is the opposite. If Romeo doesn’t like her, she needs to win him over and her attraction for him grows. If he likes her, she feels that her task is accomplished and she loses her interest in him. Juliet likes the challenge more than the relationship.

Steven Strogatz used differential equations to model the dynamics of the relationship between Romeo and Juliet. This is a new and fascinating area of applied mathematical research; you can read more about the roller-coaster relationship between Romeo and Juliet in Steven Strogatz’s Nonlinear Dynamics and Chaos: With Applications to Physics, Biology, Chemistry, and Engineering.

Mathematicians like symmetry: in math literature they switch the roles between Romeo and Juliet randomly. So in some papers they give Romeo the role of preferring a challenge over love and in some papers they give that role to Juliet.

When I teach this subject of love, Alexander Pushkin’s famous quote always pops into my mind. The quote comes from the first lines of Chapter Four of Eugene Onegin, and in Russian it is:

Чем меньше женщину мы любим,
Тем легче нравимся мы ей…

I didn’t like the English translations that I found, so I asked my son Alexey to provide a more literal translation:

The less we love a woman, the more she likes us in return…

I blame Pushkin for my tendency to always pick Juliet as the character who thrives on the challenge, even though men are often assumed to be the chasers. I’d like to ask my readers to comment on these roles: Do you think both genders play these roles equally? If not, then who is more prone to be into the chase?

Let’s return to mathematical models. In the original model, the reactions of Romeo and Juliet are a linear function of feelings towards them. I would like to suggest two other roles, in which people react to the absolute value of feelings towards them. They do not care if it is love or hate: they care about intensity.

First, there is the person, like my friend Connie, who feeds on the emotions of other people. She’s turned on by guys who love her as well as by guys who hate her. If they’re indifferent, she’s turned off.

Second, there is the opposite type, like my colleagues George, Joseph, David and many others. They hate emotion and prefer not to be involved. They lose all interest in people who feel strongly about them and they like people who are distant. I know the name for this role: it’s a mathematician!

My friend Olga Amosova worked as a molecular biologist at Princeton University. Last time I visited her, we talked about her research.

She told me that she and her group designed a repair for a DNA mutation that is highly localized. “What’s the point,” I asked her, “of repairing DNA mutation in one cell?”

I was amazed to learn that not only is there a practical use to her research, but that there is something urgent that I myself must do.

There are many diseases that are caused by localized (so called “point”) mutations. The most famous one is Sickle-cell disease. In Sickle-cell disease, defective hemoglobin causes erythrocytes to adopt a sickle shape that makes it difficult to pass through blood vessels. It is a very painful and debilitating disease. However, it turns out that the results of the research of Olga and her group could make the lives of people with such mutations much easier.

Stem cells have two amazing abilities. They grow fast and they can be turned into any type of cells in the human body. If the mutation is repaired in just one stem-cell, it can be selected and turned into a blood progenitor cell. These progenitor cells produce erythrocytes that actually transport oxygen. If these repaired cells are added to the patient’s blood, they would produce good hemoglobin for half a year. This would improve the patient’s quality of life tremendously.

So what do the rest of us learn from Olga’s research? That we must save all left-over stem-cells that are produced in childbirth, like the umbilical cord and the placenta. It’s not only Sickle-cell, but many other diseases that could benefit from using stem-cells. Research is moving so fast that these frozen stem-cells might become relevant in surprising ways — not only for the child, but also for relatives of the child — like you yourself!

So what’s the urgent thing I must do? My son recently got married, so I must finish this post and send it to my son in case they get pregnant.

Mikhail Zhvanetsky is the most prolific and famous Russian humorist. Here are my own translations of some of his best lines.

• Better a small dollar than a big thank you.
• Better dinner without an appetite than an appetite without dinner.
• Don’t drive faster than your guardian angel can fly.
• I drive too fast to worry about cholesterol.
• Best alibi — be a victim.
• A pedestrian is always right. While he is alive.
• Any car will last you a life-time. If you are hasty enough.
• Better a belly from beer than a hump from hard work.
• A bald patch is a glade trampled by thoughts.
• It is difficult to crawl with your head proudly held high.
• It’s a shame when other people have your dreams come true!
• The lottery is the most accurate measure of the number of optimists.
• A courteous man will not criticize a woman who carries a railroad tie awkwardly.
• The highest degree of embarrassment? Exchanged glances in a keyhole.
• Everything goes well, but past me.
• Let them laugh at you, rather than cry.
• While you measure seven times, others will already make a cut.
• It is not enough to find your place in life, you have to be there first.
• If a person knows what he wants, then he either knows too much or wants too little.
• And then he took a knife and shot himself dead.
• Thinking is too difficult, so most people judge.
• The more I look in the mirror, the more I believe in Darwin.
• Of two evils, I choose the one I haven’t tried before.
• Do not run from a sniper, you’ll die tired.
• You came — thanks; you left — many thanks.
• All great men are long dead, and I am feeling so-so.
• Never exaggerate the stupidity of your enemies and the loyalty of your friends.
• To save a drowning man, it is not enough to lend a hand; it is necessary for him to offer his hand in return.
• What a pity that you are leaving at long last.
• An idea came into his head and now it is desperately trying to find his brain.
• I am infinitely respectful of the terrible choices of my people.
• Some have both hemispheres protected by a skull, others by pants.
• For illusions of grandeur one doesn’t need grandeur; illusions are quite enough.
• Good always wins over evil. Hence, the winner is always good.
• Only on your birthday do you discover how many useless things there are in the world.
• You can recognize a decent man by how difficult it is for him to be nasty.
• Everything in this world is relative. For example, the length of one minute depends on which side of the bathroom door you’re on.
• In the form I filled in before the surgery there was this question: Whom should we call in case of an emergency? I wrote: A more qualified surgeon.