Words of Danny O'Bigbelly My idea of a good time

June 22, 2011

A fair coin

Filed under: Nonsense I've spouted — DannyO @ 5:15 am

After some thought, let us return to the shop to buy some matches.

What strategy should you employ, knowing that the clerk has full knowledge of your strategy?

One strategy is to buy a lot of matches and hope that the clerk hasn’t had time to ruin them all.  This strategy might work in the real world, but it doesn’t work in our world.  The clerk has all the time he needs to ruin any number of matches–even all of them, if he chooses to do so.  You will leave the store, staggering under the burden of all of the matches, and then die at the end of your journey because none of the matches will light.

Another strategy is to buy a bunch of boxes of matches, and then carefully open each box and try the first match from each box.  If the match lights, then you assume that the box was not tampered with, and that the rest of the matches in that box are good.  If you run out of boxes, then you buy more.  This won’t work because the clerk knows that you’re planning to try the first match in each box, and therefore makes that match the only match that lights.  Therefore, having lighted the only working match in each box, you then set off into the wilderness with a box that contains 99 ruined matches, having chosen the one good match, and the die at the end of your journey because none of the remaining matches will light.

You can make things a little harder for the clerk by introducing some randomness–instead of choosing the first match in each box, choose one at random.  The clerk doesn’t know which match you’ll choose, but his strategy doesn’t have to change.  If he puts one working match in the box, then there are still only two possible outcomes for each box: you’ll either choose that match (and it will light and you’ll take that now-useless box), or you’ll throw away that box and try again.  It’s likely that you will have to try many boxes before you draw out a match that works.   The more boxes you try, the more obvious it is that the clerk is trying hard to kill you–and knows your strategy, and in the end you will eventually be fortunate, pick out the one working match, and then march off to your doom.

Every strategy that has this basic form is doomed, no matter how clever.  Consider the following refinement to this procedure: buy a box of matches, select half of the matches at random, and try to light them all.  If they all light, take the remaining matches.  Otherwise, try the whole process again.  The clerk can still attempt to kill you by filling the box with half good and half ruined matches, but the probability that you will randomly select exactly the half that light is astronomically small–the same probability as flipping a fair coin 50 times and having it come up heads every time.  This will happen by blind chance one time in 1125899906842624.  If that isn’t good enough for you–after all, your life is hanging in the balance–buy two boxes, pour out the contents of both into a big heap, and try to light 100.  The probability of success for you (lighting 100 successfully) and success for the clerk (lighting exactly the correct 100) is now one in 1267650600228229401496703205376.  In layman’s terms, this ain’t gonna happen, but if you’re very worried, or there are computers involved, you can always add more boxes of matches until the probability that the clerk will trick you successfully is as close to zero as you like.

This approach ensures that if the clerk is trying to kill you, you’ll probably never leave the store because it is extremely likely that you will catch the clerk every time he gives you a box of matches that would result in your death.  You’re probably not going to die on your expedition, but you’re also probably going to die of old age in the store.

The problem is that we’re giving the clerk as many tries as he needs to get lucky and arrange things in the one way that will send you off to your doom, and since the clerk knows your strategy and therefore knows exactly how to prepare the boxes of matches so that you will either buy another box or leave the store with a box that has no working matches.

Every strategy of this sort–where we give the clerk the opportunity to provide us with only exactly enough matches to pass the test and won’t leave the store until our conditions, which the clerk knows, are satisfied–will fail.  I’m going to make this claim without any proof–in the worst possible example of mathematical rigor, since I’ve only bothered to describe one type of strategy, and there are many.  In this family of strategies, you’ll either buy another box (because you think the box you have is bad), or you’ll leave the store with a box containing nothing but matches that don’t work.  By fine-tuning your strategy, you can make it more “difficult” for the clerk, but this just means that you have to buy a lot more matches before we stumble into the unlikely situation where you accept the box of matches that the clerk offers, and then wander off to die in the wilderness.

The fundamental problem is that we’ve designed a game with only one (eventual) outcome: going on the expedition.  If that’s the only choice, and the clerk controls the matches, then we’re dead.  The clerk doesn’t need intelligence or luck; he only needs patience.

At this point, it would seem like a better idea to simply abandon the expedition and stay home.  In any case it would be quicker.

This insight provides the path to a solution.

Keep in mind that the clerk wants to kill you.  He wants you to go on your expedition, and he will do whatever he can to make you think that you have a working match.  He doesn’t want you to give up and stay home and quietly live out the rest of your life.

In order to suceed, you need a different strategy: one that gets you out of the shop in a reasonable period of time, go on your trip, with a reasonable chance of survival.  Most importantly, however, you must provide the clerk with an attractive opportunity to kill you.  Remember that the clerk can simply ruin every match in the store, if he chooses to do so.  You might be able to detect that he’s done this, but there’s no way to prevent it.  You want to give the clerk an incentive–specifically, the opportunity to kill you–to leave some of the matches in working order, and you want to come up with a test for whether there are any working matches that is unlikely to consume all of them.

Buy some number of boxes of matches–let’s say 20.  After they are safely in your possession (and can’t be modified by the clerk), divide them into two piles by flipping a coin for each box.  There will be approximately ten boxes in each pile; if chance is against you and there are only a small number of boxes in one pile, start again.   Open all of the boxes in the heads pile and try to light matches until you either find one that works, or discover that they are all ruined.  If  some number of the boxes (i.e., 5) in the heads pile contain a working match, take the tails boxes with you on your trip.  Note that there’s no point in taking the remnants of the heads pile–you might have used up all of the good matches; there might have only been one good match in each box.  If any of the boxes in the heads pile do not contain at least one working match, stay home.  Don’t go on the trip.  Once you’ve purchased the 20 boxes, the game is essentially over from the perspective of the clerk; you won’t buy any more boxes, no matter what the outcome is.

In order for the clerk to kill you, he needs to guess correctly which boxes will be in the heads pile (and put at least one good match in five of them) and which boxes will be in the tails pile (and put no working matches in any of them).   This is possible, but unlikely, and if the clerk attempts it then what is far more likely is that at least one of the boxes containing a working match will end up in the tails pile.  Since this is the clerk’s one and only chance to kill you, he will need to prepare enough boxes of matches that contain at least one good match that you’ll be confident that it’s safe to go on your trip (or else he’ll lose his chance to kill you), and he’ll have to be very lucky (or else you’ll end up with at least one of the working matches).

I won’t work through the probabilities that if there are twenty boxes and only five of them contain working matches that all five will end up in the heads pile, but you can do it for yourself and explore how the numbers change if you use larger numbers of boxes, different success criteria, or a biased coin.  You can make the probability as high as you like that if you leave the store thinking that you probably have a working match, that you actually do, and decrease the probability that you won’t stay home if you actually have a good match.  You can’t eliminate the possibility that the clerk will be lucky and you’ll end up dead, but then again the arctic is not without its perils.

If you think about it long enough, I’m sure you’ll find a better solution.

June 20, 2011

Chance favors the prepared mind

Filed under: Nonsense I've spouted — DannyO @ 6:16 pm

One of my professors gave this problem as a homework question a while ago.  By now I would expect that it is in wide circulation, but just in case you haven’t seen it already, please enjoy.

Imagine that you are an arctic explorer.  You are about to leave town to head into the wild, for some irrelevant reason, and when you get to your destination, you will need to light a fire in order to survive.  If you can’t light a fire when you get there, then you will die.  At your destination there is plenty of fuel and a fool-proof furnace that always lights on the first try, so you don’t need to worry about that.  The thing that you need to worry about is getting there with a match to light the furnace.  Unfortunately, you don’t have any matches yet.

In the town there is a store that sells matches.  The clerk of the store is the only other inhabitant of the town.  You have enough money to buy many boxes of matches, and the clerk in the store is happy to sell you as many boxes of matches as you like.  Each box is guaranteed to contain 100 matches.  If you are worried that the clerk will sell you a box filled with nothing, you can open each box and count them before you buy them.  The clerk won’t mind.

However, there is a twist.  For reasons that are beyond the scope of this problem, the clerk wants to kill you, and you are well aware of this fact.  You also know that the clerk has found a way to undetectably remove matches from a matchbox, tamper with them so that they don’t light and put them back into the box.  The only way to tell whether a match has been tampered with is to try it–if it lights, then it was good, but it’s no longer good.  Each match can only be used once, so the only way to find out whether a match is good or bad is to destroy it.  The matches are 100% reliable when they arrive at the store; the only ones that will fail are the matches that the clerk has ruined.

So, the problem really boils down to this: you need to buy matches from the clerk.  If you leave the store with at least one working match, you live.  Otherwise, you’re dead.

Your honest and pacifist beliefs prevent you from killing the clerk, stealing his matches, or trying to influence him in any other way.  The clerk, for similar reasons, can only kill you by selling you boxes of matches that he’s carefully manipulated.  The only interaction you can have is to make sure that each box contains the expected number of matches, buy boxes of matches, and try them.

What’s a good strategy?

This might all seem a little contrived, but hey, it’s a math problem.

Well, actually it’s not only a math problem.  It’s also related to cryptography, and so we’re going to make it a little more difficult.

The clerk knows your strategy.  You can’t keep any secrets from him, even though he can keep secrets from you.  He will know what steps you are going to take before you do.  He can practice and hone his strategy to increase his effectiveness at killing you.

This is exactly what cryptographers have to deal with.  Their adversaries can buy or acquire duplicates of the systems that they want to break and spend as much time as they need studying the system before they make their real attack.  When a burglar picks the lock of your door, it isn’t beginners luck–he’s been practicing opening locks just like yours for months.

And just to make things a little more interesting, let’s throw in a little game theory.  Let’s say that you don’t really need to go on your expedition.  You could skip the whole thing and stay home.  You’ll give up your chance for fortune and glory, but you’ll probably live to a ripe old age and die comfortably, surrounded by loved ones, rather than cursing the name of the clerk while you freeze to death in the middle of nowhere.

What to do?

I’ll let you think about it for a little while, but before I do I’m going to drop a bunch of clues.  You should stop reading now if you would prefer to bash your head against this problem for a while.

There are certain kinds of mathematical problems that nobody knows how to solve–or at least, if anyone knows how to solve them, they aren’t saying so.  This may be because some of the problems have the property that being able to solve these kinds of problems could be enormously valuable to certain people and/or governments.

Despite the temptation, I will avoid describing any of these problems in depth, and will only mention one quickly and without any rigor.

Given a very large number (say, several hundred digits in length) that is the product of two large primes (a few hundred digits in length), there is no known efficient way to discover those two primes.  If you can keep those primes secret, it is extremely unlikely that someone else will be able to figure them out, and since there are a mind-numbing number of such large primes, the probability that someone else will stumble across one is not even worth mentioning.  (they only need to find one, because after they’ve found one, they can find the other by dividing the product by it to find the second.)

This is an example of a particular kind of problem that is very hard to solve, but very easy to verify the solution.  Another example is opening a safe; for any given sequence of numbers, it’s easy to check whether they open the safe, but there’s no way to find the right sequence short of trying many, many sequences.

All of this would be no more than a mathematical curiosity, however, if it wasn’t for a second fact.  Large numbers that are the product of two large primes can be used as the building blocks for mathematical structures that behave in some ways like ordinary numbers and in other ways quite differently.  Most importantly, it is impossible to interpret the results in a meaningful way without knowing the prime factors.

I’m sure that mathematicians are cringing by now, but that’s OK.  They’re probably inured to this sort of casual imprecision from the hoi polloi.

So, if you know the prime factors, you can do calculations that nobody else will be able to understand.  By paths that I will not cover, I will assert that this can be used to create secret codes that are unbreakable by anyone who can’t find the primes, which is, as far as anyone knows, everyone.

This has all been known for a long time, but it had very little practical use until relatively recently, because there was a terrible problem that remained to be solved: finding large primes is as difficult as factoring large numbers.   The only way to prove that a number is prime is by showing that it has no non-trivial factors, and the only way to do that is by trial and error.  For large numbers, that’s a lot of trials and errors.

Primes were so hard to find, and so incredibly valuable–since they could be used to create nearly unbreakable codes–that some of them were considered state secrets.

Fortunately, a way was discovered around this.

Gary Miller discovered (or observed, or whatever) that there are certain functions that can test with absolute certainty whether a number is not a prime.  Instead of the usual “yes” or “no” that we expect from most tests, these functions have the outcomes “I don’t know” or “no”.  If the Miller test answers “no”, then the number is absolutely not a prime.  This doesn’t tell us what its factors are (in the general case) but we know that it’s not a prime.

The Miller test takes a number and computes a function of that number and the candidate number.  If the number fails the test (when the answer is “no”) then it is called a witness to the non-prime nature of the candidate.

That’s not very useful yet–we could construct a test that did the same thing just by saying “I don’t know” nearly all of the time, except when it happened to stumble across a factor, and then it would say “no”.  This would not represent progress.

Miller wasn’t the first to develop such a test; Fermat had one, all the way back at the dawn of number theory, but it wasn’t very good and some composites actually didn’t have any witnesses at all.   Solovay and Strassen had a much better one–more witnesses–but Miller’s was the best because it said “no” much more often as “I don’t know” for most composites.  For an arbitrary large non-prime, approximately three quarters of the numbers less than the non-prime are witnesses.

Unfortunately, there was no telling where the witnesses might be.  They didn’t arrange themselves nicely, and instead were sometimes clumpy.

Rabin, in what in retrospect seems obvious but at the time was a completely new and ground-breaking idea, suggested using sampling to choose witnesses.  We don’t know where the witnesses are, but we know how approximately how many there are, and so we know the probability of selecting one at random.

Here is the Miller-Rabin test: select a potential witness at random, and try Miller’s test.  If the answer is “no”, then it’s a composite, end of story.  If the answer is “I don’t know”, however, then the probability that the number is prime is approximately 0.75.  Repeat; if the second potential witness doesn’t work out, then the probability that the number is prime is approximately 0.9375.  After three iterations, 0.984.  After ten, 0.999999.  After twenty, 0.999999999999.

After a few hundred iterations, if you haven’t found a witness then you can be reasonably certain that the number is prime, or that you are the unluckiest person to ever walk the earth.  If you’re not sure which, just tack on a few hundred more iterations.  Miller’s test is quick and easy to compute, even for ridiculously large numbers.

So, if you want to have your own crypto keys that nobody but you can ever crack, here’s what you do: pick a random number, and test to see whether it’s prime.  If so, keep it; otherwise ditch it and begin again.  Repeat until you have all the primes you need.  There are plenty of primes out there, so you’ll find a couple eventually.

Now you either have a practically unbreakable crypto scheme, or else you’re the unluckiest person imaginable.

Rabin’s insight was that there are certain problems that we can’t solve with complete certainty, but only with very high probability.  We can make that probability as close to 1.0 as we like, but we will never get there.

This way of thinking has made possible practical solutions to problems that would otherwise be unthinkably intractable.  Every once in a while–say perhaps once between now and when the last star in the sky winks out–they will give the wrong answer, but it’s worth that risk.

It’s no coincidence that Rabin was the professor who assigned this problem.

I will let you think about this for a moment or two.

 

Powered by WordPress