Tanya Khovanova's Math Blog

I love The Secretary Problem. I first heard about it a long time ago with a different narrative. Then it was a problem about the marriage of a princess:

The king announces that it is time for his only daughter to marry. Shortly thereafter 100 suitors line up in a random order behind the castle walls. Each suitor is invited to the throne room in the presence of the princess and the king. At this point, the princess has to either reject the suitor and send him away, or accept the suitor and marry him. If she doesn’t accept anyone from the first 99, she must marry the last one. The princess is very greedy and wants to marry the richest suitor. The moment she sees a suitor, she can estimate his wealth by his clothes and his gifts. What strategy should she use to maximize the probability of marrying the richest person?

The strategy contains two ideas. The first idea is trivial: if the princess looks at a suitor and he is not better than those she saw before, there is no reason to marry him. The second idea is to skip several suitors at the beginning, no matter how rich they might seem. This allows the princess to get a feel for what kinds of suitors are interested in her. Given that we know the strategy, the interesting part now is to find the stopping point: how many suitors exactly does she have to skip? The answer is ⌊N/e⌋. (You might think that this formula is approximate. Surprisingly, it works for almost all small values. I checked the small values and found a discrepancy only for 11 and 30 suitors.)

The problem is called The Secretary Problem, because in one of the set-ups the employer tries to hire a secretary.

In many situations in real life it is a good idea to sample your options. Whether I’m shopping for an apartment or looking for a job, I always remember this problem, which reminds me not to grab the first deal that comes my way.

Mathematically, I try to find variations of the problem that are closer to real life than the classical version. Here’s one of the ideas I had: you can always delay hiring a secretary until you have interviewed several candidates. You can’t wait too long, as that good secretary you interviewed two weeks ago might have already found a job. And of course the king has a small window of time in which he can run out of the castle and persuade a suitor to come back before he saddles up his horse and rides away.

To make the problem mathematical we should fix the window size as an integer w. When you are interviewing the k-th suitor, you are allowed to go w − 1 suitors back. In other words, the latest you can pick the current suitor is after interviewing w − 1 more people. I call this problem: The Secretary Problem with a Sliding Window.

It is easy to extrapolate the standard strategy to the sliding window problem. There is no reason to pick a suitor who is not the best the princess have seen so far. In addition, if she sees the best person, it is better to wait for the last moment to pick him in case someone better appears. So the strategy should be to skip several people at the beginning and then to pick the best suitor at the last moment he is available.

The difficult part after that is to actually calculate the probabilities and find the stopping point. So I suggested this project to RSI 2015. The project was assigned to Abijith Krishnan under the direction of Dr. Shan-Yuan Ho. Abijith is a brilliant and hard-working student. Not only did he (with the help from his mentor) write a formula for the stopping point and winning probabilities during the short length of RSI, he also resolved the case when the goal is to pick one candidate out of the best two.

If you are interested to see what other RSI students did this year, the abstracts are posted here.

I recently had a home sleep study. I was given a small box which I attached to my chest. I also had to attach a thingy to my finger and put small tubes into my nose. It was relatively easy. Now I have my report:

The total time in bed is 468 minutes. Overall AHI is 37 events per hour. The supine AHI is 58 events per hour. The oxygen saturation baseline is 91%. The hypoxemic burden is 58 minutes. The oxygen saturation nadir is 63%. The heart rate ranges from 76-118 beats per minute.

I didn’t have a clue what all that meant so I hit the Internet. AHI means Apnea–Hypopnea Index, and a normal score is below 5. Anything above 30 indicates severe sleep apnea. Because mine is 37, I now have my diagnosis. My 63% oxygen saturation scared me the most. Wikipedia says 65% or less means impaired mental function. I do not need mental function when I sleep, but Wikipedia also says that loss of consciousness happens at 55%. What would happen if I lose consciousness while I sleep? Can I die? Will I wake up?

Overall the sleep study was a great thing. Now I know the diagnosis and there are ways to treat it. So I am looking forward to my improved energy and health.

But there was something in this report that would bother any mathematician. As you can see apnea gets worse when people sleep on their backs. (Thanks to this study I learned a new English word: supine means lying on the back.) The apparatus that I had to attach to my chest prevented me from sleeping on my stomach, one of my favorite sleep positions.

This report doesn’t say anything about my average AHI when I am not supine. If this average is low, then the solution might be to learn to never sleep on the back. It also means that the oxygen saturation nadir number is not very meaningful. It shows how bad it can be if I am forced to sleep on my back. It doesn’t say much about my standard sleep situation.

When I next see my doctor, I hope she’ll have answers to all my questions.

This story started when my student asked for an explanation for his grade B in linear algebra. He was slightly above average on every exam and the cut-off for an A was the top 50 percent of the class. I wrote a post in which I asked my readers to explain the situation. Here is my explanation.

The picture below contains histogram for a typical first midterm linear algebra exam.

The spike in the lowest range indicates zeros for those who missed the exam.

The mean is 74.7 and the median 81.5. As you can see the median is 7 points higher than the mean. That means that if a student performs around average on all the exams, s/he is in the bottom half of the class.

But this is not the whole story. In addition to the above, MIT allows students to drop the class after the second midterm. Suppose 30 students with lower grades drop the class; then the recalculated median for the first midterm for the students who finish the course goes up to 85. This is a difference of more than 10 points from the original average.

If this was a statistics class, then I could have told the puzzled student that he deserves that B. Instead I told him that he didn’t even have the highest score among those with Bs. Somehow that fact made him feel better.

I love making math questions out of the movies. Here is a Mission Impossible III question.

Tom Cruise is cute. He plays Ethan Hunt in Mission Impossible movies. In Mission Impossible III he needs to steal the Rabbit’s Foot from a secure skyscraper in Shanghai. He arrives in Shanghai and studies the skyscraper looking out his window. He decides to break in through the roof. And the way to get to the roof is to use a rope and swing across from another, even taller, skyscraper. 1:21 minutes into the movie, Ethan Hunt calculates the length of the rope he will need by using the projection of a skyline on his window, as seen on the first picture.

Explain why the projection is not enough to calculate the length of the rope. What other data does he need for that? Ethan Hunt does request extra data. But he makes one mistake. He uses his pencil as a compass to draw the end of the rope curve, as seen on the second picture. Explain what his mistake is.

My son, Alexey Radul, is a programmer. He taught me the importance of laziness in programming.

One of his rules:

Not to write the same line of code in the same program twice.

If you need the same line of code in the same program, that means you should either use a loop or outsource the line to a function. This style of coding saves time; it makes programs shorter and more elegant. Such programs are easier to debug and understand.

I remember how I copied and pasted lines of code before he taught me this rule. Then I needed to change parameters and missed some of the lines during changing. Debugging was such a headache.

Mathematicians are way lazier than programmers. Consider the system of two equations: x+2y=3 and 4x+5y=6. There are no repeating lines here. Only letters x and y appear twice. Mathematicians invented the whole subject of linear algebra and matrices so that they would not need to rewrite variables.

Mathematicians are driven by laziness. Once ancient mathematicians first solved a quadratic equation, they didn’t want to do it again. So they invented a formula that solves all quadratic equations once and for all.

I try to keep up with tradition. I try to make my theorems as general as possible. When I write my papers, I try to make them short and simple. When I think about mathematics I try to get to the stage where the situation is so clear I can think about it without paper and pencil. I often discover new theorems while I am in bed, about to fall asleep. Sometimes I wake up with a good idea. So I do my job while I sleep.

I love my profession. I get paid for being lazy.

I was driving on Mass Pike, when the cars in front of me stopped abruptly. I hit the brakes and was lucky to escape the situation without a scratch.

Actually, it wasn’t just luck. First of all, I always keep a safe distance from the other cars. Second, if I see the brake lights of the car in front of me, I automatically remove my foot from the gas pedal and hold it over the brake pedal until I know what the situation is.

On a highway, if the car in front of me has its brake lights on, usually that means that the driver is adjusting their speed a little bit. So, most of the time I don’t have to do anything. Seeing that the car in front of me has its brake lights on is not a good predictor of what will happen next. Only after I see that the distance between me and the car in front of me is decreasing rapidly, do I know to hit my brakes. That means that brake lights alone are not enough information. Differentiating between insignificant speed adjustments and serious braking requires time and can cost lives.

I have a suggestion. Why not create smart brake lights. The car’s computer system can recognize the difference in the strength with which the brakes are hit and the lights themselves can reflect that. They can be brighter or a different color or pulsing, depending on the strength of the pressure.

The drivers behind will notice these things before they will notice the decrease in the distance. This idea could save lives.

My American friends often ask me for insights into why Grigory Perelman refused the one million dollar Clay prize for his proof of the Poincaré conjecture. They are right to ask me: my life experience was very similar to Perelman’s.

I went to a high school for children gifted in math. I was extremely successful in competitions. I got my gold medal at IMO and went to college without entrance exams. I received my undergraduate and graduate degrees in one of the best math academic centers in Soviet Russia. Perelman traveled a similar path.

Without ever having met Perelman, I can suggest two explanations of why he might reject the money.

First explanation. To have it publicly known that you have suddenly come into money is very dangerous in Russia. Perelman’s life expectancy would have dropped immediately after accepting the million dollars. Russians that have tons of money either hide their wealth or build steel doors way before they make their first million. In addition to being a life hazard, money attracts a lot of bother. He would have been chased by all types of acquaintances asking for help or suggesting marriage proposals.

Second explanation. We grew up in a communist culture where money was scorned and math was idolized. The goal of research was research. Proving the conjecture was the prize itself. In his mind, receiving the award money might diminish the value of what he did. I understand this way of thinking, but I am personally too practical to follow such feelings and would accept the prize.

My first explanation has a flaw. Though valid, it doesn’t explain why he rejected the Fields medal. So I reached for the book abour Perelman, Perfect Rigor: A Genius and the Mathematical Breakthrough of the Century by Masha Gessen. I like Gessen’s explanation of why he rejected the Fields medal:

His objection to the Fields Medal, though never stated as clearly, seemed to have been twofold: first: he no longer considered himself a mathematician and hence could not accept a price intended for the encouragement of midcareer researchers; and second, he wanted no part of ICM, with all the attendant publicity, speeches, ceremony, and king of Spain.

The reasons are specifically related to the medal, so the Clay prize rejection might not be connected to the medal rejection. This argument slightly rehabilitates my first explanation.

I liked the book. It is a tremendous undertaking — writing about a person who doesn’t want to talk to anyone. After reading it, I have one more possible explanation of his refusal of the prize.

Perelman is a loner. One of the closest people to him was his math Olympiad coach. The coaches tend to understand the solutions on the spot, mostly because they already know them. If in his mind Perelman expected all mathematicians to be like his coach, then he might have expected a parade in his honor the day after he solved the conjecture. Instead, he got silence and attempts to steal the prize from him.

Can you imagine doing the century’s best math work without receiving congratulations for many years? The majority of mathematicians waited for the judgment of the experts, as did Perelman. The experts were busy and much slower than Perelman expected. The conjecture was extremely difficult, and it was a high-profile situation — after all, $1 million was attached to its solution. So the experts were very cautious in their pronouncements.

Finally, instead of congratulating Grigory, they said that the proof seemed to be correct and that they had not yet found any mistakes. If like Perelman, I was certain of my proof, I would have found this a painfully under-whelming conclusion.

Perelman expected to feel proud, but instead he probably felt unappreciated and attacked. Instead of the parade he may have hoped for, he had to wait for a long time, only to face disappointment and frustration. This reminds me of an old joke:

A genie is trapped in a lantern at the bottom of the sea. He vows, “I will give one million dollars to the person who frees me.” One thousand years pass. He changes his vow, “I will give any amount of money to the one who frees me.” Another thousand years pass. He ups the ante, “I will give any amount of money and two more wishes to the person who frees me.” Another thousand years pass. He promises, “I will kill the one who frees me.”

Third explanation. Perelman was profoundly disappointed in the math community. Unlike the genie, Perelman didn’t want to kill anyone, but he did want to express his disillusionment. Perhaps that is why he rejected a million dollars.

I recently posted a short article on plagiarism. Did you notice that not a word of it was mine?

I have an idea for a start-up medical insurance company for Massachusetts. My insurance will have an infinite deductible. That means you pay your own bills. The cost of insurance can be very low, say $100 a year, as I do not need to do anything other than to send you a letter confirming that you have medical insurance. People who otherwise will be fined up to $900 for being uninsured will run in droves to buy my insurance.

I have an even better idea. For an extra fee, I will negotiate with doctors so that you will pay the same amount as medical insurance companies pay to them, which is often three times less than you would pay on your own.

Who am I kidding? I am not a business person, I can’t build a company. But I am looking to buy the insurance I just described.

When you name your child there are many considerations to take into account. For example, you should always check that your kids’ initials don’t embarrass them. For example, if the Goldsteins want to name their son Paz, because it means golden in Biblical Hebrew, the middle name shouldn’t be Isaak, or anything starting with I.

Contemporary culture adds another consideration: how easy would it be to find your child on the Internet? I personally find it extremely convenient to have a rare name, because my fans can find my webpage and blog just by googling me. Parents need to decide whether they want their children to be on the first page of the search engine or hidden very far away when someone googles them.

When I named my son Sergei, I knew that there was another mathematician named Sergei Bernstein. But I didn’t think about the Internet. As a result, I confused the world: is my son more than a hundred years old or did Sergei Natanovich Bernstein compete at Putnam?