Thousandth, and last, post.

This is the last post here at God Plays Dice. It happens to be the thousandth, but I didn't plan that.

I'm moving to Wordpress, and to gottwurfelt.wordpress.com. (The obvious subdomain was taken, by somebody that I don't want to send traffic to.)

I'm also hoping to update more frequently there. Wordpress seems to have better support for adding images to posts, definitely has better support for mathematical notation, has built-in analytics, and, let's face it, has a better image. So it's (perhaps past) time to move.

So update your bookmarks, your feed readers, or whatever you kids are using to follow blogs these days. I'll see you there.

Solution to distance between random points from a sphere

So I asked on Sunday the following question: pick two points on a unit sphere uniformly at random. What is the expected distance between them?

Without loss of generality we can fix one of the points to be (1, 0, 0). The other will be chosen uniformly at random and will be (X, Y, Z). The distance between the two points is therefore

√((1-X)² + Y² + Z²)

which does not look all that pleasant. But the point is on the sphere! So X² + Y² + Z² = 1, and this can be rewritten as

√((1-X)² + 1 - X²)

or after some simplification

√(2-2X).

But by a theorem of Archimedes (Wolfram Alpha calls it Archimedes' Hat-Box Theorem but I don't know if this name is standard), X is uniformly distributed on (-1, 1). Let U = 2-2X; U is uniformly distributed on (0, 4). The expectation of √(U) is therefore

∫₀⁴ (1/4) u^1/2 du

and integrating gives 4^3/2/6 = 8/6 = 4/3.

(The commenter "inverno" got this.)

Of course it's not hard to simulate this in, say, R, if you know that the distribution of three independent standard normals is spherically symmetric, and so one way to simulate a random point on a sphere is to take a vector of three standard normals and normalize it to have unit length. This code does that:

xx1=rnorm(10^6,0,1); yy1=rnorm(10^6,0,1); zz1=rnorm(10^6,0,1)
d1=radic(xx1^2+yy1^2+zz1^2)
x1=xx1/d1;y1=yy1/d1;z1=zz1/d1;
xx2=rnorm(10^6,0,1); yy2=rnorm(10^6,0,1); zz2=rnorm(10^6,0,1)
d2=radic(xx2^2+yy2^2+zz2^2)
x2=xx2/d2;y2=yy2/d2;z2=zz2/d2;
d=radic((x1-x2)^2+(y1-y2)^2+(z1-z2)^2);

and then the output of mean(d), which contains the distances, is 1.333659; the histogram of the distances d is a right triangle. (The code doesn't make the assumption that one point is (1, 0, 0); that's a massive simplification if you want to do the problem analytically, but not nearly as important in simulation.)

A geometric probability problem

Here's a cute problem (from Robert M. Young, Excursions in Calculus, p. 244): "What is the average straight line distance between two points on a sphere of radius 1?"

(Answer to follow.)

If any of my students are reading this: no, this should not be interpreted as a hint to what will be on the final exam.

Wind and Mr. Ug

You should watch Vi Hart's stop-motion animated story of Wind and Mr. Ug.

In which I declare four things which my probability class is not about

In class today, I said approximately this:

So people decide whether to have children by flipping a coin, and if it comes up tails they have a kid, and if it comes up heads they don't. They repeat this until it comes up heads. This is probably not a good model of how people decide whether or not to have children, but maybe it's good in the aggregate. And anyway this isn't a class about how people decide whether to have kids.

Then there are two kinds of children, girls and boys -- well, not always, but this isn't a class about that -- and each child is equally likely to be a boy or a girl -- well, wait, that's not exactly true, but it's not a horrible assumption about how reproduction works on a cellular level, but this isn't a class about that either.

And people's decisions to stop having kids is independent of the sex of the children they've had -- which says this isn't China, because people do interesting things under the one-child policy -- but this isn't a class about that.

(Then I actually did some math -- namely, assume that the number of children a random family has is geometrically distributed with some parameter p, and assume that all children are equally likely to be male or female and that their genders are independent of the gender of any other children or the number of children in the family. Pick a random family with no boys. What is the distribution of the number of children they have?)

11/11/11

You may have heard that it's 11/11/11. (Or, if you live in the UK, 11/11/11.) When I was growing up, I'd get confused and think that World War II ended on this day, one hundred years ago. You know, at the eleventh hour of the eleventh day of the eleventh month of the eleventh year.

The New York Times says that marketers are viewing this as a singular event -- but they went on about this four years, four months, and four days ago.

The Corduroy Appreciation Club says it is Corduroy Appreciation Day.

A bit more mathematically, you can watch a video about the number eleven by James Grime, which appears to be the first of a series of Numberphile videos.

Edited, November 12, 12:29 pm: from the New York Times, a hundred years ago: "To-day it is possible to write the date with the repetition six times of a single digit." The article also points out that a digit will probably never occur again seven times in the date -- we'd have to make it to November 11, 10011 for that to happen.

Small sample sizes lead to high margins of error, unemployment version

The ten college majors with the lowest unemployment rates, from yahoo.com. I've heard about this from a friend who majored in astronomy and a friend who majored in geology; both of these are on the list, with an unemployment rate of zero.

The unemployment rates of the ten majors they list are 0, 0, 0, 0, 0, 0, 1.3, 1.4, 1.6, and 2.2 percent.

I would bet that the six zeroes are just the majors for which there were no unemployed people in the sample. The data apparently comes from the Georgetown Center on Education and the Workforce; there's a summary table at the Wall Street Journal, and indeed the majors which have zero unemployment are among the least popular. Just eyeballing the data, some of the majors with the highest unemployment are also among the least popular. The red flag here would be, say, an unemployment rate of 16.7% (one out of six) or 20.0% (one out of five) for some major near the bottom of the popularity table, but I don't see it; I guess their sample is big enough that no major is that small, or maybe they actually made some adjustments for this issue.

The actual Georgetown report seems to be available here but I am having trouble viewing it.

In case you were wondering, mathematics is the 28th most popular major (of 173) and has 5.0% unemployment; "statistics and decision science" is 128th most popular and has 6.9% unemployment, which seems to go against the popular wisdom these days that statistics majors are more employable than math majors. (But I work in a statistics department, so my view of the popular wisdom may be biased.)

Solution to a puzzle from a few months ago

I never posted a solution to this puzzle, and today one of my students asked me about it.

The puzzle was to find all three-digit numbers that, when multiplied by their successor, give a number concatenated with itself.

So of course when you concatenate a three-digit number x with itself, you get 1001x. So the question becomes: when is k(k+1) a multiple of 1001?

1001 is 7 times 11 times 13. k and k+1 have no prime factors in common, so we have to have that some subset of 7, 11, and 13 are prime factors of k, and the rest are prime factors of k + 1. Furthermore these are going to be proper subsets; if we have that 7, 11, and 13 are prime factors of k and none of those are prime factors of k+1, or vice versa, then we get that k doesn't in fact have three digits.

So we can have the following six situations:

(1) k is a multiple of 7 and k + 1 is a multiple of 143;

(2) k is a multiple of 11 and k + 1 is a multiple of 91;

(3) k is a multiple of 13 and k + 1 is a multiple of 77;

(4) k is a multiple of 77 and k + 1 is a multiple of 13;

(5) k is a multiple of 91 and k + 1 is a multiple of 11;

(6) k is a multiple of 143 and k + 1 is a multiple of 7.

In each case we can then use the Chinese remainder theorem to find k. Let's consider the first case: we have that k ≡ 0 (mod 7), k ≡ -1 (mod 11), k ≡ -1 (mod 13).

The CRT tells us that the solution to the system of congruences

k ≡ a₇ (mod 7), k ≡ a₁₁ (mod 11), k ≡ a₁₃ (mod 13)

is

k ≡ a₇(143)(143^-1)₇ + a₁₁(91)(91^-1)₁₁ + a₁₃ (77)(77^-1)₁₃ (mod 1001)

where I'm using (a^-1)_b to stand for the inverse of a mod b. The other solutions differ from this by multiples of 1001. We can find the inverses by brute force:

(143^-1)₇ = (3^-1)₇ = 5, (91^-1)₁₁ = (3^-1)₁₁ = 4, (77^-1)₁₃ = (12^-1)₁₃ = 12.

So we finally get

k ≡ 715 a₇ + 364 a₁₁ + 924 a₁₃ (mod 1001).

Now, the case (1) corresponds to a₇ = 0, a₁₁ = -1, a₁₃ = -1; so we get

k ≡ 0 - 364 - 924 (mod 1001)

and so we get the solution k = -364 - 924 + (2)(1001) = 714. Indeed (714)(715) = 510510. (714 and 715 are a Ruth-Aaron pair.) The other five situations lead to, respectively, k = 363, 923, 77, 637, 286 and k(k+1) = 132132, 852852, 6006, 406406, 82082.

Using generating functions to prove that the only sequences which are their own sequence of running averages are the constant sequences

Here's a problem that occurred to me yesterday: consider a sequence of real numbers a₀, a₁, a₂, ... . Let b_k = (a₀ + a₁ + ... + a_k)/(k+1) be the average of the first (k+1) of the a_i. When is a sequence equal to its own sequence of averages? That is, if we see a bunch of numbers, when is it true that every number we see is the average of all the numbers we've seen so far?

Of course the answer is the constant sequences. But can we prove this using generating functions?

It turns out we can. If we have

f(z) = a₀ + a₁ z + a₂ z² + ...

then

f(z)/(1-z) = a₀ + (a₀ + a₁)z + (a₀ + a₁ + a₂) z^2 + ... = b₀ + 2b₁ z + 3b₂ z^2 + ...

and let's call the right-hand side here g(z). What can we do to g(z) to transform it into

h(z) = b₀ + b₁ z + b₂ z² + ... ?

Well, a linear operator that takes the function (of z) z^k to the function (of z) z^k/(k+1) could be applied to g in order to get h. Clearly this is related to integration. In fact the operator

I φ(z) = (1/z) ∫₀^z φ(s) ds

does the trick. So we have

h(z) = I g(z) = (1/z) ∫₀^z f(s)/(1-s) ds.

But remember that we wanted the generating function h of the averages to be just the generating function f of the original sequence. So this gives

f(z) = (1/z) ∫₀^z f(s)/(1-s) ds

and this is in fact a differential equation. Multiply through by z and differentiate both sides to get

z f'(z) + f(z) = f(z)/(1-z).

A bit of rearranging gives

f'(z)/f(z) = 1/(1-z)

and we recognize that the left-hand side is the derivative of log f(z). Integrating both sides gives

log f(z) = log(1-z) + C

where C is a constant of integration, and finally we get f(z) = e^C/(1-z). But this is just the generating function of a constant sequence.

The quadratic equation, Dr. Seuss style

I've been busy, but here's a quick one: The quadratic equation, Dr. Seuss style, by Katie Benedetto. My favorite stanza:

Each value there was, well she renamed each one
Claiming that nice names would make this more fun.
“Variables, well, they’re whatever we wish
So like one, two, red, blue, I’ll call this one “fish”!

This is the antidote to if the IRS had discovered the quadratic formula.

Some thoughts on the mathematics of tax withholding

Here's a question of some practical importance: let's say that I make $2,000 in each of the first six months of the year, and $4,000 in each of the second six months. Will I have more or less tax withheld than if I make $3,000 every month?

(This is inspired by the fact that I taught this summer, and was paid for doing so, but because of the way my contract is written, my pay for the academic year is spread out over twelve months. As a result I got extra-large paychecks over the summer, partially for the work I was doing in the summer and partially for work that I had already done in the previous academic year or will be doing in the next academic year.)

For those not familiar with the US tax system: if your net pay is X you don't get a check for X, but for some smaller amount, because various taxes are withheld. Chief among these is the federal income tax. Now, the federal income tax is not a flat tax, but a progressive tax -- if your income is higher then you pay a larger percentage of your income in tax. Tax returns have to be filled out on a yearly basis, but most people get paid more often than yearly. So the amount of tax withheld is determined, based on the amount of the paycheck and the period that the paycheck is for, in such a way that the total amount of tax withheld is somewhere near the amount that you're expected to owe. (Most Americans actually end up overpaying through this system, and get a small refund back at tax-filing time.)

So say that if you make 36x per year, then your taxes will be f(36x). Then you'd expect that if you make 3x in a given month, you will have f(36x)/12 withheld, for a total of f(36x) over the course of the year.. If instead you make 2x in each of six months and 4x in each of six months, then in each of the months in which you make 2x tax will be withheld as if you make 24x per year, and in each month in which you make 4x tax will be withheld as if you make 48x per year. So total withholding will be

6f(24x)/12 + 6f(48x)/12

or, simplifying, [f(24x) + f(48x)]/2. Call this T'. Is this less than or greater than f(36x), which we'll call T?

We can easily see that T' ≥ T if and only if

f(48x)-f(36x) ≥ f(36x) - f(24x).

That is, T' ≥ T if and only if the amount of extra tax owed when you go from $36,000 to $48,000 is more than the extra amount owed when you go from $24,000 to $36,000. But since marginal tax rates are increasing -- since the tax is progressive -- this is true.

More generally, given progressive taxation, withholding is smallest for a given annual income if that income is spread out exactly evenly throughout the year. This is a consequence of Jensen's inequality. The more unevenly spread out the earnings are, the more money will be withheld.

In reality this is slightly more complicated because there are tax brackets, which are reflected in the withholding formulas, so f is actually piecewise linear (see page 36 of this IRS publication). For example, a single person paid between $883 and $3,050 per month (after subtracting withholding allowances) will have $70.80 + .15(x-$883) withheld from a paycheck of x; a single person paid between $3,050 and $7,142 will have $395.85 + .25(x-$3050) withheld. (Note that putting $3,050 into either of these formulas gives $395.85; the amount withheld is a continuous function of the amount earned.) So if every paycheck is under $3,050, or if every paycheck is over $3,050, then the amount withheld ends up being the same no matter how the pay is distributed. But a person who makes, say, $3,000 in each of two months will have $388.35 withheld from each, for a total of $766.70; a person who makes $2,000 in one month and $4,000 in another will have $238.35 withheld from the first and $633.35 withheld from the second, for a total of $871.70 withheld.

I had known all this intuitively before this afternoon but I'd never bothered to actually write down why it is...

This all applies to people who make varying amounts in differing pay periods from a single job. People who have multiple jobs can be burnt in the withholding process because we have progressive taxation; if you make x in each of two jobs you have less withheld than if you make 2x in a single job. If that's you, be careful.

(I'm not an accountant. None of this should be taken as financial advice.)

God tweets about playing dice

There's a book coming out in November, The Last Testament: A Memoir by God. "God" tweets at TheTweetOfGod, and "He" just twote:

Do you ever lose when you play cards?" Remember Einstein! I play not cards, but dice. And I never lose. The dice are loaded. And so am I.

There you have it, folks. The title of this blog is correct.

867-5309

The number 8,675,309 is the title of a song. It is also a prime number, and as far as I can tell, it's the largest prime number to appear in a song title. According to this list of songs with numbers in the title from Wikipedia (which is currently in the "Wikilists" space because it was deleted from mainstream Wikipedia, larger numbers in song titles are: 9 million, 30 million, 93 million, 100 million, 1 billion, 1 trillion, 1 quadrillion, 1 googolplex, infinity minus one, and infinity.

I'm not surprised to see that most of these are "round numbers", simply because they're easier to say; in particular by inspection they are not prime, since they're all multiples of large powers of 10. But I'm wondering if anybody out there has written a song titled, say, "six billion and one".

(No fair going out and writing such a song.)

A puzzle about splitting up numbers into groups

A puzzle from David Radcliffe: "Split {1,2,...,16} into two groups of the same size having equal sums, equal sums of squares, and equal sums of cubes."

Solution: one group is A, D, E, G, J, K, M, P; the other is B, C, E, H, I, L, N, O. (I've replaced each number with the corresponding letter of the English alphabet to obscure things a bit.)

Here's how I found this. It's often useful to look at cubes mod 9, because any cube of an integer is either a multiple of 9, one less than a multiple of 9, or one more than a multiple of 9. These cases correspond to the integer itself being a multiple of 3, one less than a multiple of 3, or one more than a multiple of 3. So 1³ + 2³ + 3³ is a multiple of 9; so are 4³ + 5³ + 6³, ..., 13³ + 14³ + 15³. Since 16³ is one more than a multiple of 9, so is the sum of the first sixteen cubes, which we'll call N.

We want to find eight integers in 1, ..., 16 that have sum of cubes equal to N/2. Now, if N is congruent to 1 mod 9, then N/2 is congruent to 5 mod 9. This means it's relatively far from a multiple of 9, so a lot of the numbers that are one more than a multiple of 9 are going to have to go into the same group. In particular, each group must contain either five more 1 mod 3 than 2 mod 3 integers, or four more 1 mod 3 than 2 mod 3 integers. Keeping in mind the limited supplies -- we only have six integers in our set congruent to 1 mod 3, and five each congruent to 0 and 2 mod 3, the only possible groups are:

≅ 0 (mod 3)	≅ 1 (mod 3)	≅ 2 (mod 3)
3	5	0
1	6	1
4	0	4
2	1	5

Furthermore we either have a group of the type given in the first row and one of the type given in the fourth row, or one of the second-row type and one of the third-row type, in order to meet the supply restrictions.

But it's not possible to have a group of the first-row type and a group of the fourth-row type. Let's consider a group of the fourth-row type -- that is, it has two multiples of three, one number that's one more than a multiple of three, and five that are one less than a multiple of three. The five that are one less than a multiple of three must be 2, 5, 8, 11, and 14. The square of each of these is one more than a multiple of three, so 2² + 5² + 8² + 11² + 14² is congruent to 2 mod 3. Call the other three members of this group x, y, and z. From the table above, two of these are multiples of 3.

But the square of every integer is either 0 mod 3 (if it's a multiple of 3) or 1 mod 3 (if it's not a multiple of 3) and so the sum of the first sixteen squares is 2 mod 3. So each group must have sum of squares congruent to 1 mod 3. The five integers that we've already put in the group have squares summing to 2 mod 3; thus x² + y² + z² is also 2 mod 3, contradicting the fact that exactly one of x, y, and z is not a multiple of 3.

So we must have groups of the type in the second row and of the type in the third row. Let's look at the group of the second-row type. It contains all six integers in {1, 2, ..., 16} congruent to 1 mod 3 -- that's 1, 4, 7, 10, 13, and 16. By symmetry the other two elements -- call them t and u -- must sum to 17. Furthermore the sum of the first 16 squares is (16)(16+1)(2×16+1)/6 = 1496; so the sums of the squares in each group must be 1496/2 = 748. 1²+4²+7²+10²+13²+16² = 591 and so we must have t² + u² = 748 - 591 = 157. So we need two integers that sum to 17, with squares summing to 157; solve the quadratic t² + (17-t)² = 157 to get t = 6 or t = 11, and correspondingly u = 11 or u = 6.

So if there's any way at all to do what we were asked, it's with one group being 1, 4, 6, 7, 10, 11, 13, 16 -- and this checks out.

Of course, it would be trivial to write a program to check this...

Dimensional analysis for gravity trains

A surprising fact: drill a straight tunnel through the earth, between any two points. Drop a burrito in at one end. Assuming that you could actually build the tunnel, and that there's no friction, the burrito comes out the other end in 42 minutes. This is called a gravity train and it's not hard to prove (the version I link to is due to Alexandre Eremenko of Purdue) that the time it takes the burrito to get from one end to the other is (3π/4)^-1/2 (G ρ)^-1/2, where G is the gravitational constant and ρ is the density of the Earth. Alternatively this can be written as (r³/Gm)^1/2, where r is the radius of the earth and m its mass.

Everyone's so surprised, when they see this, that the time doesn't depend on the distance between the two points! And this is interesting, but as a result you don't see the more subtle fact that the time doesn't depend on the size of the planet. If I make a super-Earth that is twice the radius but made of the same stuff, so it's eight times as massive, then the density stays the same. Somewhat surprisingly you can see this using dimensional analysis. It's "obvious" that this time, if it exists, can only depend on the mass of the earth, the radius of the earth, and the gravitational constant. The mass of the earth, m, has dimension M; the radius, r, has dimension L; the gravitational constant has dimension L³ M^-1 T^-2. The only combination m^α r^β G^γ that has units of time is G^-1/2 m^-1/2 r^3/2.

Of course I'm making a big assumption there -- that the constant time "42 minutes" is actually a constant! It seems perfectly reasonable that it could depend on the distance between the two termini. I'll handwave that away by saying that it depends on the angle formed by the two termini and the center of the earth. And angles are of course dimensionless.

(The Alameda-Weehawken burrito tunnel, being non-fictional, uses magnets to accelerate and decelerate the foil-wrapper burritos and takes 64 minutes instead of the theoretical 42.)

Give your money to Samuel Hansen's math kickstarter!

Alright, folks. You should give some money to Samuel Hansen's Kickstarter project Relatively Prime: Stories from the Mathematical Domain. This is what it sounds like -- Samuel will tell eight hours' worth of stories about mathematics. Samuel is perhaps the world's most accomplished mathematical podcaster -- or at least the most prolific --- and is the force behind Combinations and Permutations (sort of a mathematical comedy podcast), Strongly Connected Components (interviews with mathematicians), and Math/Maths with Peter Rowlett. Here's Samuel's blurb about the project:

Relatively Prime will be an 8 episode audio podcast featuring stories from the world of mathematics. Tackling questions like: is it true that you are only 7 seven handshakes from the President, what exactly is a micromort, and how did 39 people commenting on a blog manage to prove a deep theorem. Relatively Prime will feature interviews with leaders of mathematics, as well as the unsung foot soldiers that push the mathematical machine forward. With each episode structured around topics such as: The Shape of Things, Risk, and Calculus Wars, Relatively Prime will illuminate each area by delving into the history, applications, and people that underlie the subject that is the foundation of all science.

He needs $8,000 in pledges. With 12 hours to go (until 11:13 PM US Eastern Time tonight) he's got $7,115. The way Kickstarter works is that Samuel only gets any of the money if at least $8,000 gets pledged. So if

Maybe the puppets from Avenue Q will convince you, although they're raising money to found a Monsterssori school. But hey, they're both good causes. On some level storytelling is what all education is about.

A cute number theory puzzle

Today's MAA number of the day, when multiplied by its successor, gives a number concatenated with itself. (Like 455 * 539 = 245245, except 539 isn't the successor of 455.)

Puzzle: find all such three-digit numbers. (The fact that I'm phrasing it this way should indicate to you that there's more than one.)

Meta-puzzle: generalize this. (I have some generalizations in mind.)

X-Y correspondence

Google hits for "Pascal-Fermat correspondence": 3,230. For "Fermat-Pascal correspondence": 206.

Does anyone have any idea why? In particular it seems like one would sort either on importance (but which of these two is more important?) or alphabetically (but that gives the wrong result).

And given two individuals X and Y, how can we predict whether "X-Y correspondence" or "Y-X correspondence" is more common? I'm sure there are no hard and fast rules here but there must at least be some trends, and would expect a situation similar to how gender is assigned to words in languages, foreign to me, where words have gender.

A mathematics quiz on Sporcle that isn't just basic arithmetic

From Sporcle: name the famous mathematicians associated with some theorems.

I don't think I'm giving anything away by telling you that one of the answers is Euler. I also take issue with the result they give under this name (link goes to Wikipedia article with the same name as one of the answers).

The most well-read cities in the United States

From Berkeleyside: Berkeley is the third most well-read city in the US, according to amazon.com data.

This is among cities with population 100,000 or greater. Number 1 is Cambridge, Massachusetts (105K people); number 2 is Alexandria, Virginia (140K); number 3 is Berkeley, California (112K); number 4 is Ann Arbor, Michigan (114K); number 5 is Boulder, Colorado (100K). There are 275 cities of population greater than 100,000 in the US; Alexandria, the most populous of these five, is ranked 177.

My first thought upon seeing this is that these are all small cities, and of course you expect to see more extreme results in small cities than in large cities. Small cities are perhaps more likely to be homogenous. (This seems especially likely to be true for small cities that are part of larger metropolitan areas.) Actually, my quick analysis of the top five doesn't hold up for the top twenty; the average rank of the top twenty cities listed at amazon is 127.1, which is LOWER (although not significantly different) from the 138.5 you'd expect if being on this top-twenty list was independent of size. But it's certainly possible that, say, some 100,000-person section of the city of San Francisco actually has higher amazon.com sales than Berkeley. (There are a surprisingly large number of bookstores in the Mission.)

Also, people in college towns tend to read a lot -- that's no surprise (although one does hear that students don't read any more a lot these days). Four of the top five (all but Alexandria) are college towns; also in the top 20 are Gainesville (Florida), Knoxville (Tennessee), and Columbia (South Carolina). And in case you're wondering, Alexandria is not named after the city in Egypt with the Great Library.