Posts Tagged ‘math’
Clock practice for kids update
July 19th, 2010 at 11:00 am
For reasons I can’t explain, my original post on printing time/clock practice sheets for kids always forced you to download a zipped archive of files to your local computer, unzip them in some convenient place, and launch them from your hard drive. While this is no burden to my geekier readers (who might prefer a local copy they can edit to suit their own needs), it’s not the sort of thing the average parent or teacher is used to doing.
So here’s a direct link to a page that shows the clock faces without the download/unzip hassle. Every time you load or reload the page a new set of 12 clock faces will appear, which you can then print out to give your young scholar some practice in telling time.
The minute hand moves in five-minute increments, so it’s not for kids who are first learning to tell time, it’s for those who have mastered “o’clock” and “half past.”
I should mention again that the JavaScript that generates the clock hands is largely based on this work by Mathieu ‘P01’ Henri and his analog clock page.
If you have kids the right age, you might be interested in my other grade school math practice sheets, covering addition, subtraction, multiplication and division.
How many samples?
July 7th, 2010 at 8:30 am
In my Monte Carlo solution of the Two Child Problem, I did 10,000 simulations using Python’s random module. Was that enough? If I didn’t already know the answers (the usual case when doing Monte Carlo simulation), how could I estimate the accuracy of the results? Not surprisingly, the answers to these results can be found in the field of statistics.
When the process being simulated consists of a series of independent trials, each trial having one of two results (which we’ll call passes and fails, although any two mutually exclusive results could be used), it’s said to be a Bernoulli sequence, and the count of passes follows a binomial distribution
where p is the probability of a passing a single trial.1 You may recognize the term with the factorials as the binomial coefficient.
An estimate of p is easily calculated:
where we put the hat over the p to distinguish the estimate from the true (albeit typically unknown) value.
Because we could get a different value of x every time we run a set of n trials, \hat{p} is a random variable. If the number of trials is large enough, \hat{p} will have a normal distribution with a mean of
and a standard deviation of
That the mean of \hat{p} is equal to p signifies that \hat{p} is an unbiased estimate of p: as we increase n, \hat{p} will tend toward p.
Because we know the distribution of \hat{p} and its parameters, we can calculate the probability that \hat{p} will fall within some neighborhood, \pm \delta, around p,
where \Phi is the standard normal cumulative distribution function,
The \Phi function can’t be integrated analytically, but many numerical analysis programs include a function for it. Octave has a function called normcdf that does the trick. Back in the not-so-good old days, you’d have to look up it up in a table; every statistics textbook had a table of \Phi in its appendix.
This is all very nice, but you can only do these calculations if you know p, and the typical reason you’re doing the Monte Carlo simulation is that you don’t know p. What you have is a particular value of \hat{p} and you want to know how good it is.
Enter the concept of the confidence interval. By flipping the terms around and using \hat{p} to estimate the standard deviation,
we can say with a confidence2 of
that the true value of p is in the interval
A more convenient way to work is to introduce a new variable,
and choose a confidence level of 1 - 2\alpha. Then
where \Phi^{-1} is the inverse of the standard normal CDF (Octave function norminv).
The confidence interval at this level is
or, expanding out the \hat{\sigma}_{\hat{p}},
That was a longish derivation, but the result is simple to use. Let’s say we’ve done a Monte Carlo simulation and we want to get the 95% confidence interval for p. Here’s what we do:
- Note that for 95% confidence, \alpha = 0.025.
- Use whatever tools available to determine that \Phi^{-1}(0.975) = 1.96.
Take the values of n and \hat{p} from the simulation and calculate the interval
\hat{p} \pm 1.96\sqrt{\frac{\hat{p} (1 - \hat{p})}{n}}
Now let’s say we’re planning a simulation and want to choose a value of n to get a decent estimate of p.
- For 95% confidence, use \Phi^{-1}(0.975) = 1.96, as before.
- Get a preliminary value of \hat{p}, perhaps by doing a small Monte Carlo run.
- Decide how tight we want the confidence interval, \pm \delta, to be.
Calculate n via
n = \hat{p} (1 - \hat{p}) \left(\frac{1.96}{\delta}\right)^2
Note that if we want a very tight confidence interval, \delta will be small and n will have to be large. This makes sense: to get a close estimate, we need a lot of samples.
Although it’s a common confidence level, there’s nothing magical about 95%. We could just as easily use another value. Here are the \Phi^{-1} values for a few others.
| Confidence | \alpha | \Phi^{-1}(1-\alpha) |
|---|---|---|
| 99% | 0.005 | 2.576 |
| 95% | 0.025 | 1.960 |
| 90% | 0.050 | 1.645 |
| 75% | 0.125 | 1.150 |
| 50% | 0.250 | 0.675 |
As expected, to get higher confidence, we need more samples.
Let’s calculate the confidence interval for the Monte Carlo simulation of the first example of the Two Child Problem. The result was
If we restrict ourselves to families that have at least one son,
the probability of having two sons is 2520/7535 = 0.334
So n is 75353, and \hat{p} is 0.334. The 99% confidence interval is
So if we didn’t already know from earlier work that the true probability was 1/3, we could use this result to say with 99% confidence that the true probability was between 0.320 and 0.348.
I should mention that the formulas in this post aren’t restricted to Monte Carlo simulation. They’re valid any time you’re sampling from a pass/fail type of population.
-
The count of fails also follows a binomial distribution; just substitute 1-p for p and n-x for x. ↩
-
We use the word confidence instead of probability because we’re really not calculating a probability here. The true value of p isn’t a random variable, it’s a number that we just don’t happen to know. ↩
-
Why isn’t it 10,000? In this simulation we filtered out about a quarter of the sample families because they didn’t have sons, leaving 7535. ↩
Graphical Pythagoras
July 3rd, 2010 at 9:47 pm
You may have seen this clever animated GIF floating around the intertubes lately. The original seems to live at http://i.imgur.com/DrROq.gif, but I have no idea who created it.
To me, the whole thing could have been done with just this frame.
Each of the four pink triangles has an area of ba/2, the little blue square in the center has an area of (b-a)^2, and the big square formed by the hypotenuses has an area of c^2. So
Expanding the binomial gives us
The ba terms cancel, and we’re left with
as expected. It’s not as cute as the animation, but I like how the algebra works.
Monte Carlo and the Two Child Problem
June 30th, 2010 at 12:18 pm
In the previous post about the Two Child Problem, we thought about how the probabilities would change under different rules. In this post, let’s write those rules into a program and see how the probabilities change in a Monte Carlo (no relation to Monty Hall) simulation.
To review, the Two Child Problem is this:
Mr. Smith has two children. At least one of them is a boy. What is the probability that both children are boys?
The answer depends on what rules we think the questioner is following. We’ll look at three cases:
- The questioner would never pose this problem if Mr. Smith had two daughters. The problem is restricted to families with at least one son and the question is always about the probability of two sons.
- The questioner isn’t restricted at all. He simply tells us about one child, chosen at random, in a two-child family and asks us if the other child is of the same sex.
- The questioner is biased toward boys. If there’s at least one boy in the family, that’s what he tells us; if the family has two girls, he tells us there’s at least one girl. In either case, he asks for the probability that the other child is of the same sex.
In Monte Carlo simulation, we use the computer to generate lots of random events and then combine the counts of those random events to estimate probabilities. For the Two Child Problem, we’ll simulate “families” by generating pairs of letters: G for girls, B for boys. The counts we need to keep track of are:
- n, the total number of families;
- n_{sons}, the number of families with at least one son;
- n_{2sons}, the number of families with two sons; and
- n_{2daughters} the number of families with two daughters.
Note that n_{sons} + n_{2daughters} = n.
For the first case, we’re eliminating from consideration the families with two daughters, so the probability will be
For the second case, we include all the families. Since we’re choosing the “revealed” child at random and asking if the other child is of the same sex, it’s equivalent to going through the list of all the families and picking out the boy-boy and girl-girl families. The probability will be
The third case is a little trickier. Recognize first that if the family has any boys, the questioner will ask about boys and the probability will be calculated as in the first case. The questioner will ask about girls only if the family has two girls, so the probability of having two children of the same sex under that condition is 1. We use conditional probability to combine these situations:
With our variables, this becomes
With a little algebra this formula reduces that of the second case. Which means that these two sets of rules are equivalent, even though they don’t seem to be.
Here’s a Python program that implements these ideas.
1: #!/usr/bin/python
2:
3: from __future__ import division
4: from random import choice
5:
6: n = 10000
7: sexes = ('G', 'B')
8: families = []
9:
10: for i in range(n):
11: families.append((choice(sexes), choice(sexes)))
12:
13: nsons = len([x for x in families if 'B' in x])
14: n2sons = len([x for x in families if x == ('B', 'B')])
15: n2daughters = len([x for x in families if x == ('G', 'G')])
16:
17: print '''If we restrict ourselves to families that have at least one son,
18: the probability of having two sons is %d/%d = %5.3f''' % (n2sons, nsons, n2sons/nsons)
19:
20: print
21:
22: print '''If we choose the "revealed" child at random, the probability of having
23: two children of the same sex is %d/%d = %5.3f''' % (n2sons+n2daughters, n, (n2sons+n2daughters)/n)
24:
25: print
26:
27: print '''If we "reveal" boys in every case except when there are two daughters,
28: the probability of having two children of the same sex is
29: (%d/%d)*(%d/%d) + 1*(%d/%d) = %5.3f''' % (n2sons, nsons, nsons, n, n2daughters, n, n2sons/nsons*nsons/n+n2daughters/n)
We use the choice function from the random module to generate 10,000 simulated families as a list of tuples. Lines 13-15 then filter the list according to certain criteria and count the number of families left. Line 17 onward does the calculations according to the formulas above and prints the results.
Here’s a sample of the output.
If we restrict ourselves to families that have at least one son,
the probability of having two sons is 2520/7535 = 0.334
If we choose the "revealed" child at random, the probability of having
two children of the same sex is 4985/10000 = 0.498
If we "reveal" boys in every case except when there are two daughters,
the probability of having two children of the same sex is
(2520/7535)*(7535/10000) + 1*(2465/10000) = 0.498
Based on the reasoning of the earlier post, the answers are what we expected. But thinking the problem through from a Monte Carlo perspective does give a different view of what the various rules mean.
The mantra of Richard Hamming’s book Numerical Methods for Scientists and Engineers is
The purpose of computing is insight, not numbers.
I think this exercise is a good illustration of that. We didn’t really have to write the Monte Carlo program; just working out how we were going to write it gave us an understanding of the similarities and differences in the three sets of rules.
Children, coins, and Monty Hall
June 30th, 2010 at 6:18 am
You may have seen links to this Science News article floating around the internets this week. It describes a new variant on a old probability problem and a dispute about its solution. I think the article does a good job describing both the old and new problems and their conventional solutions, but not such a good job with the dispute. I want to discuss the old problem, the difficulties that can arise in interpreting it, and its relationship to another famous probability problem.
The original problem is sometimes called the Two Child Problem and can be stated like this:
Mr. Smith has two children. At least one of them is a boy. What is the probability that both children are boys?
The naive answer is 1/2: Boys and girls are equally likely and the sex of the child we’re told about has no effect on the sex of the unknown child.
The more sophisticated answer is 1/3: There are four equally likely permutations of two children. If we order the children by age, those permutations are girl-girl, girl-boy, boy-girl, and boy-boy. Since we are told that there’s at least one boy, girl-girl is eliminated and we have three equally likely possibilities, only one of which has two boys.
The even more sophisticated answer is “Wait a minute—how did you decide which child to tell me about?”
Because there are some extraneous issues that can confuse the Two Child Problem (boys and girls really aren’t equally likely, and what about identical twins?), and because it doesn’t lend itself to thinking about repeated trials (if Mr. Smith keeps having two children again and again, Mrs. Smith will get pissed), I want to use a probabilistically equivalent problem:
I’m in my office. You’re in another room where you can’t see, hear, feel, smell, or taste what I’m doing. I flip two fair coins onto my desk, take note of how they landed, and cover each of them with an upside-down cup. I call you into my office and tell you (honestly) what I’ve done. I then reveal one of the coins to be a head and ask you the probability that the other coin is also a head. What should you answer?
As with the Two Child Problem, there’s the naive answer of 1/2, the more sophisticated answer of 1/3 (based now on permutations of HH, HT, TH, and TT), and the even more sophisticated answer that we’re going to explore.
Strangely, what you should answer depends not on any immutable laws of probability, but on my behavior, which hasn’t been fully defined in the problem statement.
Is the problem set up so that I must always reveal a head? Do you know that before you enter my office?
Twenty-five percent of the time I’ll flip two tails; what should I do then? Leave you to rot in the other room? Flip again until I get at least one head? Change the problem and reveal a tail instead?
If you know ahead of time that I won’t ask you into the room unless I’ve flipped at least one head, and if you know that I must reveal a head, then you’re justified in saying that the probability that the other coin is a head is 1/3. But without those constraints on my behavior, you don’t have that justification.
Suppose the problem were stated this way:
I flip two coins onto my desk, cover them up and call you in. When you enter I reveal one of them and ask you the probability that the other is the same. What should you answer?
Clearly, this time you should answer 1/2, because the coins are the same in two of the four cases (HH, HT, TH, TT).
If my behavior isn’t constrained—or you don’t know that my behavior is constrained—you wouldn’t know the difference between the earlier coin-flipping game and this one. So maybe the naive answer of 1/2 isn’t so naive, after all. This is the point made by Yuval Peres in the aforelinked Science News article.
We can look at the Two Child Problem the same way: are we asking this question only of men that have at least one son, or would we change the question to be about girls if Mr. Smith had two daughters? Unless you know the constraints, you don’t know what the best answer is.
If you’re familiar with the Monty Hall Problem, you may see some similarities between it and the Two Child Problem (or our coin-flipping equivalent). In both cases, there’s an element of chance and you’re given information that may or may not influence your answer. Here’s the Monty Hall Problem, as given on its Wikipedia page:
Suppose you’re on a game show, and you’re given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host [Monty Hall1], who knows what’s behind the doors, opens another door, say No. 3, which has a goat. He then says to you, “Do you want to pick door No. 2?” Is it to your advantage to switch your choice?
I won’t give you the answer; if you don’t already know it, you can follow the Wikipedia link. The important point is that there is an answer, because Monty’s behavior—unlike mine in the coin-flipping problem—is well defined:
- There is always a car behind one door and a goat behind each of the other two, and Monty knows which is which.
- After you make your first choice, there will always be another door with a goat behind it.
- Monty always reveals a door with a goat behind it.
Because of these constraints, and because you know these constraints going in, you can develop a strategy. In the Two Child Problem and our original statement of the coin-flipping equivalent, you can’t develop a strategy until you know more.
If you’re having trouble following the logic, don’t despair—you’re in good company. According to the Science News article, Martin Gardner didn’t understand the subtleties of the Two Child Problem the first time he wrote about it.
Update 6/30/10
There’s a bit more about the Two Child Problem here
-
This setup is similar to the “Big Deal of the Day,” the last contest on each episode of the old TV game show Let’s Make a Deal. The host of Let’s Make a Deal was Monty Hall, hence the name of this problem.) ↩
PCalc 2.0’s resolution mix
June 25th, 2010 at 2:41 pm
A week ago, James Thomson sent out a beta of PCalc 2.1 for iPhone to his testers. It’s the “Retinal” version of PCalc, with the graphics redrawn to take advantage of the higher resolution of the iPhone 4’s screen. At the time, I had no use for the higher-res graphics, but I downloaded and installed it anyway, because there was another improvement I wanted to test.
Yesterday morning, I picked up my iPhone 4 and installed all my apps and music. The PCalc beta wouldn’t install, presumably because it uses the Ad Hoc distribution method and my new phone’s device ID isn’t in the beta app’s provisioning profile. I’m sure James will update the list of his testers’ device IDs soon, but in the meantime I have no calculator.1
After a PCalcless day, I went to the App Store and got the unRetinal 2.0.1 version. I had already bought PCalc back before I was a beta tester, so there was no need to cough up any more money. I fired it up to make sure the settings were right and immediately noticed two things:
- It starts up really fast on an iPhone 4.
- The user interface is a hybrid of (lower-res) graphics and text, which gives it something of a split personality on the new screen.
Here’s a 320×480 view of the screen, what you would see on a 3GS or earlier:
Here’s a section of it in glorious 640×960 resolution:
See how the text—most of it, anyway—is really sharp and the images are kind of fuzzy? It looks like some things you would think are text, like the trig functions, are actually images.
PCalc works fine, of course, it’s just a little funny looking.
The fuzziness will be banished in version 2.1, which is going through the approval process as I type this. I’m looking forward to going back to the future.
Update 6/26/10
I’m back in business with PCalc 2.1. See a screenshot comparison with the new Retinalized keyboard here.