Skip to content

Archive

Tag: math

There’s one thing I’ve done a lot of while working at a platform for EDU iPhone/iPad apps and that’s playing educational apps. I’ve played dozens, if not hundreds of games designed to teach children ABCs or basic arithmetic. I’ve flipped through an equally formidable number of storybook apps, including some recreations of my childhood favorites. A lot of the apps have really been disappointing, but a few gems have stood out.

One of my favorites is a math app called Space Math. After it won the SmarTots Quest for the Best educational app contest, I had a chance to help the designer, Reese, add some more features to its newest version. In thing that I found interesting was the contrast between him and many of the other app developers I’ve worked with. While many others were either large companies converting various properties from browser-based flash programs to iOS or business people hiring outsourcers to make a variety of apps, Reese was a one-man hobbyist shop. More interestingly, his full-time job is teaching math to high school students and his app was driven partially by his experiences with some his students arriving to high school with weak foundations in more elementary math. As a former teacher who was drawn to build things to help my students, I find it very easy to empathize with him!

Here is the first version of the screencast I made to help promote his work:

Wayne sprung this question on me yesterday. I swear he should have been a CS major.

The Hundred Hatted Prisoners

There are a hundred prisoners in a dungeon, sentenced to be executed the next morning. Fortunately for them, the king of the land is eccentric and offers them a chance to survive. He tells them he’ll line them up, one in front of the other, with the most guilty in the back and the least guilty in the front. They’ll be bound, so it will be impossible for them to see those behind them, but they’ll be facing down a gentle slope and will be able to see all the prisoners in front of them clearly.

Next, the king will place a hat on the head of each prisoner. Some hats will be blue and some will be red, but the exact number of each is secret. The prisoner in the very back will be able to see which color of hats the other ninety-nine prisoners are wearing. The second prisoner will be able to see the hats of the ninety-eight prisoners in front, but not his own or the one on the prisoner in the back. It will continue like this, up to the prisoner at the very front of the line, who cannot see any of the hats.

Finally, the king will walk up the line, starting from the back, going to the front, asking each prisoner what color his own hat is. Anyone who answers incorrectly will be executed immediately, via silent odorless methods undetectable to those who haven’t yet been asked what color their hats are.

The prisoners may talk with each other tonight and collude to create a strategy for the next day. Once they are lined up for execution, though, they will not be allowed to speak, except to answer the king when he asks, “What color is your hat?” Even then, they may only utter a single word, “red” or “blue”.

If the prisoners work together with the right strategy, how many need to risk their lives?

This logic puzzle doesn’t really have a “sucker answer” like the coin-tossing one did, but the answer is a smaller number than one might first think. It’s a smaller one than I first thought.

The votes from Friday’s Simple Probability Puzzle are in. Here was the question:

Imagine there’s a completely random event with two outcomes, say flipping a coin. Each flip has an equal probability of landing heads or tails. Now imagine that we’re interested in seeing how long it takes to get a certain sequence of outcomes.
Pattern 1

Tails, Heads, Tails
Pattern 2

Tails, Heads, Heads

Now, suppose we flip a coin until Pattern 1 is reached, note how many coin flips it took, and then we repeat the process many times and average how many flips it takes to get a tails-heads-tails sequence . After that, we go through the same process to see how many flips it takes to get Pattern 2, a tails-heads-heads sequence.

On average, which pattern takes fewer coin tosses?

  • They'll happen equally fast, on average. (78%, 1,775 Votes)
  • Tails, Heads, Tails takes fewer tosses! (11%, 258 Votes)
  • Tails, Heads, Heads takes fewer tosses! (9%, 213 Votes)
  • I can't figure it out. (2%, 36 Votes)

Total Voters: 2,282

Loading ... Loading ...

The results weren’t exactly stellar. As expected, the sucker answer of “They’ll happen equally fast, on average.” got the vast majority of the votes. The correct answer of “Tails, Heads, Heads takes fewer tosses!” drew less than ten percent of the total. Worse still, the people who chose “Tails, Heads, Heads takes fewer tosses!”, outnumbered those who admitted defeat more than five-to-one.

It wasn’t all bad, though! Some commenters not only arrived at the correct answer, but produced programs to prove it. The very first such comment was well-formatted LISP code. I have to say, it’s great to be getting feedback back of this level of geek-cred.

Some commenters produced a mathematical derivation of the average number of coin flips that it takes to get a tails-heads-heads sequence vs. a tails-heads-tails sequence. The problem is tricky, but it really is a simple problem. Once it’s properly framed, it’s a first year high school algebra problem– two linear equations to be solved for two unknowns. Here’s a basic walk-through of the process to find out how many flips it takes, on average to get THT:

First, let's define a few terms:
N[THT|TH] is the average flips to get THT once we already have TH
N[THT|T] is the average flips to get THT once we already have T
N[THT|] is the average flips to get THT, starting from scratch

The easiest term to find is N[THT|TH].  There's a 50% chance that
we'll get tails on the next flip.  In that case, the number of flips
to match the pattern is 1.  If we get heads on the next flip, then
the number of flips is 1 + N[THT|]. Therefore,

N[THT|TH] = .5(1) + .5(1 + N[THT|]), or
N[THT|TH] = 1 + N[THT|]/2

If we already have N[THT|T], then we have a 50% chance of
getting heads, which would mean the total flips would be that flip,
plus N[THT|TH], and a 50% chance of getting tails, which would
mean that flip plus N[THT|T].  Therefore,

N[THT|T] = .5(1 + N[THT|TH]) + .5(1 + N[THT|T])
N[THT|T] = 1 + N[THT|TH]/2 + N[THT|T]/2
N[THT|T]/2 = 1 + N[THT|TH]/2
N[THT|T] = 2 + N[THT|TH]

If we're starting from scratch, i.e. N[THT|], we have a 50% chance
of tails, which would give us that flip plus N[THT|T], and a 50%
chance of heads.  Since heads would be useless, that would mean
one flip plus N[THT|].  Therefore,

N[THT|] = .5(1 + N[THT|T]) + .5(1 + N[THT|])
N[THT|] = 1 + N[THT|T]/2 + N[THT|]/2
N[THT|]/2 = 1 + N[THT|T]/2              (subtracting N[THT|]/2)
N[THT|] = 2 + N[THT|T]                  (multiplying each side by 2)

Now, we know that starting from scratch takes two more flips than
starting from T, or four more flips than starting from TH.  We plug
this back in.

N[THT|TH] = 1 + N[THT|]/2               (our first equation)
N[THT|] = 4 + 1 + N[THT|]/2             (substituting for N[THT|T]
N[THT|]/2 = 5                           (subtracting N[THT|]/2)
N[THT|] = 10

On average, it takes ten flips to get tails-heads-tails.

After getting the general idea, it’s very quick to solve for how many flips it takes to get THH:

Here are the basic equations for N[THH|TH], N[THH|T], and N[THH|]:
N[THH|TH] = .5(1) + .5(1 + N[THH|T])
N[THH|T] = .5(1 + N[THH|TH]) + .5(1 + N[THH|T])
N[THH|] = .5(1 + N[THH|]) + .5(1 + N[THH|T])

Solving for N[THH|]:
N[THH|]/2 = 1 + N[THH|T]/2
N[THH|] = 2 + N[THH|T]

Solving for N[THH|T]
N[THH|T] = 1 + N[THH|TH]/2 + N[THH|T]/2
N[THH|T]/2 = 1 + N[THH|TH]/2
N[THH|T] = 2 + N[THH|TH]

Solving for N[THH|TH]
N[THH|TH] = 1 + N[THH|T]/2
N[THH|TH] = 1 + (2 + N[THH|TH])/2
N[THH|TH] = 2 + N[THH|TH]/2
N[THH|TH]/2 = 2
N[THH|TH] = 4

Plugging in and solving for N[THH|], we get:

N[THH|T] = 4 +2
N[THH|] = 4 + 2 + 2 = 8

On average, it takes eight flips to get tails-heads-heads.

Even though the math involved is basic, it’s very easy to jump to the wrong conclusion. As one commenter mentioned, one of the brightest collections of people on the planet tanked on a logically equivalent question. Like me, the speaker of that video was also thinking about the long and ignoble history of experts bungling mathematics in courts. Our brains just aren’t really wired for mathematical abstraction.

Notes:
1) Only one vote per IP address was allowed, but the vote counts on this poll are just as unreliable as any other internet poll. I re-worded the poll options after about 150 votes had already been made, in order to make the question less ambiguous. People were also perfectly free to read all feedback from other visitors before voting.

2) This probability puzzle has a wide variety of applications, including in determining bankroll a successful gambler or investor will need, and in gene sequencing.

3) I’m in a sleep-deprived state as I post this. Please be gentle on any errors.

Ever wonder why so many expert witnesses lead juries astray due to mathematical errors? Or why so many gamblers and investors are so bad at assessing relatively simple probability questions? First imagine that you consider yourself an expert (at something other than math), and then you encounter a question like this…

Imagine there’s a completely random event with two outcomes, say flipping a coin. Each flip has an equal probability of landing heads or tails. Now imagine that we’re interested in seeing how long it takes to get a certain sequence of outcomes.

Pattern 1

Tails, Heads, Tails

Pattern 2

Tails, Heads, Heads

Now, suppose we flip a coin until Pattern 1 is reached, note how many coin flips it took, and then we repeat the process many times and average how many flips it takes to get a tails-heads-tails sequence . After that, we go through the same process to see how many flips it takes to get Pattern 2, a tails-heads-heads sequence. For example if we start flipping a coin for pattern 1 and we see:

tails, heads, heads, tails, heads, tails

Then we reached Pattern 1 after only six coin tosses. Sometimes it will take as few as three coin tosses, but other times it will take many more. If we were to repeat this test thousands of times and calculate the average number of tosses it takes to get Pattern 1 and compare it to the average number of tosses it takes to get Pattern 2, which be the bigger number?

On average, which pattern takes fewer coin tosses?

  • They'll happen equally fast, on average. (78%, 1,775 Votes)
  • Tails, Heads, Tails takes fewer tosses! (11%, 258 Votes)
  • Tails, Heads, Heads takes fewer tosses! (9%, 213 Votes)
  • I can't figure it out. (2%, 36 Votes)

Total Voters: 2,282

Loading ... Loading ...

The first correct answer with a valid explanation wins a beer (if you can make it to Taipei to collect).
Update: Two correct answers are in! Ray Myers, with some lisp code to brute force the answer, and Robin with a clear explanation of why. When and if you make it out to collect, drinks at the Taiwan Beer Factory are on me.

Related Posts:
Even Simple Probabilty Puzzles Can Be Tricky
Game Theory and Bluffing
Good God are There a Lot of Morons on Digg

This is fascinating video about Daniel Tammet, a twenty-something with extraordinary mental abilities. He’s capable of calculations to 100 decimal places in his head, and he can acquire functional fluency in a foreign language in a single week. Most interesting is that unlike the vast majority of savants, he can communicate with and interact with people in a fairly ordinary way.

This documentary follows Daniel’s travel to America, where he met with researchers for a variety of tests, and he also meets the real man behind Dustin Hoffman’s character in Rain Man.

Highlights by the minute

  • Daniel recites the first 22,000 digits of π (05:00)
  • Daniel describes how he sees numbers (17:00)
  • Daniel hustles some NYC chess hustlers (20:55)
  • Meet Rainman (23:45)
  • Daniel takes on Vegas (28:50)
  • Neuro-scientists test Daniel (31:45)
  • Japanese kids develop impressive abilities via abacus study (34:28)
  • The ultimate test- Daniel is flown to a country of the researchers’ choice and given one week to learn the language (41:10)

This is a recent test used in England:
a diagnostic math test for first year university students in England
Royal Society of Chemistry

Here’s a Chinese math test:
a math question from a Chinese college entrance test
continue reading…

I’m so shocked by the sheer amount of ignorant, yet argumentative idiots on Digg that I can barely even muster up a real rant. There’s an article by a math teacher explaining the common confusion his students have with the idea that 1 = .9999… repeating. He went to great lengths to explain very clearly why this is true, and wrote what I thought was a good article. What kind of response did I expect from the supposedly “techie crowd” at Digg? Well, I figured I’d see a few comments saying stuff like, “Hey, good explanation,” or “Duh…” How naive I was.

Instead, reading the comments was like going through a pile of essays written by a ward of lobotomy patients. Comments ranged from wack-ass idiotic unsupported claims such as:
continue reading…

After not seeing any more feature requests or error reports on my tool for converting Chinese numbers, I’ve decided it’s stable enough to present to the Chinese-forums readers. At this point, I can honestly say it offers significantly more functionality than any other online tool for converting Chinese numbers into digits and it does it all without making users wait for page loads. The reason the conversions are good is simple. A gajillion (and no I can’t translate that number into Chinese) bloggers sent me extensive and detailed feedback. Thank you, Gin, John, Kanwa-kyudai, and Weilen. There’s no way I could have anticipated the wide variety of potential user input without you guys.

My goal in writing the converter was to help out beginning Chinese students. In truth, I learned a bit about Chinese numerology myself, thanks to everyone’s comments. Please keep in mind that I don’t know JavaScript. I’ll fully admit this implementation is a kluge. And no, Kanwa-san, I haven’t forgotten about making an Arabic Numeral to Chinese tool. It’s coming soon.

Last night, I went back to Taibei to play chess with my old co-workers. It’s kinda scary, really. They’ve all been playing regularly, Martin’s been reading books on strategy, and I fully expect to get left way behind in terms of ability shortly. Mike W. was there, though and the topic turned to gambling. As many of my friends know, Matt and I got really interested in poker, especially Texas Hold ’em. Matt wrote a program to analyze the strength of various opening hands against different numbers of opponents. I wrote a Perl program to help train myself to group various opening hands in terms of strength based upon where one is sitting. For example, if you’re in a 10 person game, sitting to the dealer’s left and holding an unsuited Ace-Queen, it’s time to fold. If you’re holding the same cards and sitting to the dealers right, you’ll definitely want to pay to stay in and see the flop.

Game Theory

Then game theory and optimal bluffing came up. Sometimes, there are situations in which a consistent strategy will always fail, and yet a somewhat random strategy, or a mixed strategy will prevail. It sounds irrational, but it is true. Mike asked me to explain it, and I wasn’t able to do so very clearly. So, I’ll have another go at it here. First, there are a few important distinctions to make, though.

Optimal Strategies vs. Exploiting Strategies

There are two kinds of strategies used in poker. In optimal strategies, the opponent is assumed to be strong and adaptive. Optimal strategies are evaluated based on how well they would fare against an optimal opponent. Exploiting strategies are designed to exploit a weak opponent as fully as possible. For example, if you play against a timid opponent who never calls, you can win money from him more quickly by bluffing every time (a strategy designed to exploit his weakness) than you could by using an optimal strategy. The bluffing strategy I’m about to describe is an optimal strategy that will work even if opponents know you do it.

An Example in Which Random Betting is Optimal

Imagine that you are playing a poker game in which the first four cards are dealt out face up, and the last card is dealt face down. After each new card is dealt, each player may bet and raise once. In this game, you and your opponent have just been dealt your final cards, there are $40 in the pot and he has bet $10. The maximum bet is $10.

Opponent’s hand:3♣ 3♠ 6♦8♣
Your hand:K♠ J♠Q♦10♥

There are 8 cards on the table. Your last card, which your opponent has not seen, is one of the 44 remaining cards in the deck. Of those remaining cards, any of the Kings, Jacks, Queens or Tens would give you a bigger pair than your opponent’s threes, and any of the Aces or nines would give you a straight. In other words, of the remaining 44 cards, 20 will give you a winning hand and 24 will give you a losing hand. However, you are still in the stronger position if you use an optimal bluffing strategy. Consider these three cases:

You Never Bluff

In 24 cases out of 44, you have the weaker hand and you fold. In the other 20 cases you bet $10. Your opponent, being a strong player, recognized that you do not bluff and never calls your bet. You win the $40 pot in 20 games out of 44. Since half of the money in the pot was yours to begin with, you earn $20×20 = $400. In the 24 games in which you fold, you lose $20×24 = $480. In the long run, if you employ this strategy, you’ll lose $80 every 44 times you play this way.

You Always Bluff

In 20 cases out of 44, you have the stronger hand and bet $10. Your opponent knows you always bluff, so he calls. You win $40 from the pot, plus his $10 from calling. Since $20 of the pot is your money to begin with, you win $30×20 = $600. In the 24 games you lose, you lose your $20 in the pot, plus a $10 bet each time. That’s a $30×24 = $720 loss. In the long run, if you employ this strategy, you’ll lose $120 every 44 times you play this way.

You Use Game Theory to Bluff an Optimal Amount

It is possible to use your opponent’s pot odds to determine how often to bluff. In this case, always bet on the 20 winning cards plus four of the 24 losing cards, and you’ll have the edge. It doesn’t matter how you determine when to bluff, as long as it’s random (at least to your opponent’s perspective). You could say, I’ll bet if I draw a winning card OR a two of any suit. You could ask your friend to give you a random number and then divide it by 24 and only bet on losing cards if the remainder were under 4. Anything random will work. Bet on the 20 winning cards, plus 4 losers. Unless you give tells or your opponent can crack your “randomization” scheme, there is no strategy he can employ that will give him the edge.

Your Opponent Folds When You Bet

You bet on your 20 winners, plus 4 of the losers. Your opponent folds every time, so you win $20 from the pot 24 times for a total of $480. You fold on 20 of the 24 hands in which your last card was a loser, losing $20×20 = $400. In the long run you’ll win $80 every 44 times this situation comes up against an opponent who folds.

Your Opponent Calls You

You bet on your 20 winners, plus 4 of the losers. Your opponent calls each time. On the 20 hands in which you really do have the stronger hand, you win the $20 he put in the pot, plus the $10 call. That’s a total of $30 x $20 = $600. On the four hands in which you bluff and lose, you
lose $30 x 4 = 120. On the 20 hands you fold, you lose $20 x 20 = $400. In the long run, you’ll win $80 every 44 times this situation comes up against an opponent who calls.

Conclusion

Don’t underestimate math geeks! By utilizing game theory, it is possible to construct a mixed strategy that can win in some situations when any consistent strategy would fail.

Notes: I realize that I didn’t address the possibility of the opponent drawing a 3rd three or a 2nd six or eight, each of which would beat a high pair, but not a straight. I’ll leave that as an exercise for the reader. This is a simplified example. For a more realistic one, see the comments below.

The optimal bluff is calculated based on the pot odds your opponent would if you bet. Advantage is maximized when the odds that your bet is a bluff are equal to your opponent’s pot odds.