Random sums of sines and random walks

John Cook, at his Probability Fact twitter feed (@ProbFact), asked (I’ve cleaned up the notation):

What is the expected amplitude for the sum of N sines with random phase? i.e. sum of \sin(x + \phi_i) where \phi_i ~ uniform[0, 2\pi]

Intuitively one expects something on the order of sqrt{N}, since we’re adding together what are essentially N independent random variables. It’s not too hard to throw together a quick simulation, without even bothering with any trigonometry, and this was my first impulse. This code just picks the \phi_i uniformly at random, and takes the maximum of f(x) = \sum_i \sin(x + \phi_i) for values of x which are multiples of \pi/100.

x = (0:200)/(2*Pi)
n = 1:100
num.samples = 100


max.of.sines = function(phi){
max(rowSums(outer(x, phi, function(x,y){sin(x+y)})))
}


mean.of.max = function(n, k){mean(replicate(k, max.of.sines(runif(n, 0, 2*pi))))}
averages = sapply(n, function(n){mean.of.max(n, num.samples)})

This is a bit tricky: in the matrix in max.of.sines, output by outer, each column gives the values of a single sine function \sin(x + \phi_i), and rowSums adds them together.

We can then plot the resulting averages and fit a model y^2 \sim Cx. I get C \approx 0.7872 from my simulation, which is close enough to pi/4 to ring a bell:


C = lm(averages^2~n+0)$coefficients


qplot(n, averages, xlab="n", ylab="mean", main="means for 100 samples") +
stat_function(fun = function(x){sqrt(C*x)})

sample-means

At this point we start thinking theory. If you’re me and you haven’t looked at a trig function in a while, you start at the wikipedia page, and discover that it actually does all the work for you:

\sum_i a_i \sin (x + \delta_i) = a \sin (x+\delta)

where

a^2 = \sum_{i,j} a_i a_j \cos (\delta_i - \delta_j).

That is, the sum of a bunch of sinusoids with a period is a single sinusoid with the same period, and an amplitude easily calculated from the amplitudes and phases of the original sinusoids. There’s a formula for \delta as well, but it’s not relevant here.
In our case all the a_i are 1 and so we get

a^2 = \sum_{i, j} \cos (\delta_i - \delta_j)

If you take the expectation of both sides, and recognize that E \cos (\delta_i - \delta_j) is 1 if i = j (it’s cos(0)) and 0 if i \not = j (just the average of the cosine function), then you learn E(a^2) = N where N is the number of summands. That agrees with our original guess, and is enough to prove that E(a) \le \sqrt{N} by Jensen’s inequality.

To get the exact value of E(a) we can expand on David Radcliffe’s comment: “Same as mean dist from origin after N unit steps in random directions. Agree with sqrt(N*pi/4)”. In particular, consider a random walk in the complex plane, where the steps are given by exp(i \theta_j) where \theta_j is uniform on the interval [0, 2\pi). We can work out that its sum after N steps is

S_N = \sum_{j=1}^N exp(i \theta_j) = \sum_{j=1}^N (\cos \theta_j + i \sin \theta_j)

and so, breaking up into the real and imaginary components,

|S_N|^2 = \left( \sum_{j=1}^N \cos \theta_j \right)^2 + \left( \sum_{j=1}^n \sin \theta_j \right)^2.

Rewriting the squared sums as double sums gives

|S_N|^2 = \left( \sum_{j=1}^N \sum_{k=1}^N \cos \theta_j \cos \theta_k \right) + \left( \sum_{j=1}^N \sum_{k=1}^N \sin \theta_j \sin \theta_k \right)

and combining the double sums gives
|S_N|^2 = \sum_{j=1}^n \sum_{k=1}^N (\cos \theta_j \cos \theta_k - \sin \theta_j \sin \theta_k)

and by the formula for the cosine of a difference we get

|S_N|^2 = \sum_{j=1}^n \sum_{k=1}^N \cos (\theta_j - \theta_k)

which is exactly the a^2 given above. So the amplitude of our sum of cosines is just the distance from the origin in a two-dimensional random walk!

It just remains to show that the expected distance from the origin of the random walk with unit steps in random directions after N steps is \sqrt{\pi N/4}. A good heuristic demonstration is as follows: clearly the distribution of the position (X, Y) is rotationally invariant, i. e. symmetric around the origin. The position X is the sum of N independent variables each of which is distributed like the cosine of a uniformly chosen angle; that is, it has mean \mu = {1 \over 2\pi} \int_0^{2\pi} \cos \theta \: d\theta = 0 and variance \sigma^2 = {1 \over 2\pi} \int_0^{2\pi} \cos^2 \theta \: d \theta - \mu^2 = 1/2. So the X-coordinate after N steps is approximately normally distributed with variance N/2. The overall distribution, being rotationally symmetric with normal marginals, ought to be approximately jointly normal with X and Y both having mean 0, variance N/2, and uncorrelated; then sqrt{X^2 + Y^2} is known to be Rayleigh-distributed, which finishes the proof modulo that one nasty fact.

From the “amusing recommendation engine” files: pe

People who bought Alexandre Grothendieck: A Mathematical Portrait from Amazon also bought some nice-looking Japanese chalk which I’ve seen referred to as dream chalk and praised on MathOverflow. (And a bunch of math books, but you probably expected that.) Mathematicians, as you may know, are one of the last populations on earth to have a fondness for chalk, although I found this ecologist praising chalk.

When I left academia, I remember thinking of it as “putting down the chalk”. I’m not looking to go back to teaching, and I don’t miss having random dust on all my clothes, but I kind of miss it. In the “real world” we use whiteboards, which are superior in some ways — no dust!. But they’re inferior in other ways — their markers always seem to run out of ink and people don’t bother to throw them out, so any work at a whiteboard begins with searching the office for the one set of whiteboards that works.

Actually in the “real world” we mostly sit at desks and use computers. It’s difficult to get real thinking done this way; when I need to think up new ideas, as opposed to writing the code that implements them or communicating the results, I get better work done with a pen and paper. I wonder if this is an artifact of my age – 30, which is just old enough to remember the time without computers, as observed in The End of Absence by Michael Harris. (He puts it as “people born before 1985”. I’d rephrase this as “1984 or before” because of the symbolic significance of 1984.)

And to marry recommendation engines and surveillance: in the spring Alexis Madrigal pointed out that Amazon’s recommendation engine had created a guide to dealing drugs.

Jeopardy! link roundup

The Jeopardy! Tournament of Champions begins today. Here’s a quick roundup of some Jeopardy!-related links I’ve come across recently:

From Gawker, How a geek cracked the Jeopardy! code. The “geek” in question is Roger Craig, who built a tool to help him study for the show; it seems to have helped, as he won six games, and set the one-day record of $77,000.

Slate had a roundup of some of the most common categories which is pretty interesting. This came out around the time of Watson.

In fact, IBM’s Journal of Research and Development had a whole issue on Watson.

And there’s Eric Feder’s model for the probability of winning at a game of Jeopardy! (based on the state within a single game) and a forum thread discussing it.

The data from the Jeopardy archive has been scraped as well if you want to do some of your own analysis.

The Final Wager analyzes the game theory of Jeopardy! wagers.

What I’m curious about right now are the odds of winning today, given that you won yesterday – and more generally, building a model of player strength, in order to predict things like the odds of winning a tournament.  In this year’s tournament there are two that stand out above the rest: Julia Collins (who won 20 games) and Arthur Chu (who won 11). They’re very different players – here’s a profile in the Wall Street Journal.  SB Nation wants them to have an Ultimate Jeopardy Battle of Fire and Lasers. Can I get odds on that battle happening, or on its winner? It seems quite difficult to do this accurately, though – most ranking problems depend on the fact that players will play each other repeatedly, but the Jeopardy! format, in which once you’re gone, you never come back (except for possibly in a tournament) make the analysis more uncertain.

(Bayes should help.)

Links for November 9

Pierre Cartier wrote a long profile of Grothendieck for the new journal Inference: International Review of Science.

Jonathan Touboul wrote a paper The hipster effect: why nonconformists all look the same. Here’s apopular summary by Gabe Bergado at Mic. Basically, if you don’t want to look like everyone else, but it takes you some time to figure out what everyone else is doing, you’ll end up synchronizing with the other people with the same preference for nonconformity,

Portrait of the Hilbert curve by Aldo Cortesi.

Becca Cudmore and Jennifer Daniel at Nautilus show us five ways to lie with charts.

Here’s an interesting paper on best practices for scientific computing. One of the authors, Greg Wilson, is from an organization called Software Carpentry which teaches programming to scientific researchers.

From Natalie Wolchover and Peter Byrne at Quanta, In a multiverse, what are the odds? (First in a series; the second one should be out tomorrow.)

jasmcole has written about the mathematics of stereographic lampshades, which are made so that the light that shines through them makes interesting patterns on your walls. This was inspired by a blog post of Alex Bellos on the work of Henry Segerman and Saul Schleimer. Of course this can be made into reality with a 3-D printer, and you can buy it at Segerman’s shapeways store.

Is it professional for a professor to ask “surprise” questions on a test?, from Academia Stack Exchange. (Short version: the question is poorly phrased, but yes, and perhaps it is part of the professor’s duty, because being able to figure out things you haven’t seen before is usually one of the things you should learn in a course.)

We always think we’re right, but we don’t think we’re always right.

Jordan Ellenberg on how many states Nate Silver is going to get wrong, according to Nate Silver. (This refers to the elections of US Senators taking place tomorrow.) For each state Silver gives a probability of winning; we can give a probability that Silver will be wrong which is just his own predicted probability that the underdog wins. The answer is an an expected value of 2.5. Silver has been saying since the 2012 election that he got lucky in calling all fifty states correctly. In some sense it would have been more impressive if he’d missed a couple, which would have shown his predictions were calibrated correctly. (I remember trying to explain this to colleagues at my job at the time, where I’d been for a bit over a month; I think I did so successfully, but it’s a subtle point.)

Silver’s famous 50-for-50 2012 presidential predictions are still available; according to his own predictions, he would have expected to get about 1.8 states wrong, on average. It’s hard to say just how good going 50-for-50 is, though, because the errors are correlated.

However, it almost never makes sense to look at binary outcomes, but rather at the continuous outcomes that they collapse. (For example, when looking at sports data use difference in points scores instead of win-loss records.) Andrew Mooney at the Boston Globe did exactly this, and saw that 68% of the time Silver got within his stated one-standard deviation margin of error, and 96% of the time within two standard deviations.

Index of ignorance, or just innumeracy?

From Zach Wener-Fligner at Quartz, <a href=”http://qz.com/288707/everything-you-think-you-know-about-the-news-is-probably-wrong/”>Everything you think you know about the news is probably wrong</a>, based on <a href=”https://www.ipsos-mori.com/researchpublications/researcharchive/3466/Perceptions-are-not-reality-10-things-the-world-gets-wrong.aspx”>this Ipsos MORI study</a> of online panels in fourteen countries: Australia, Belgium, Canada, France, Germany, Hungary, Italy, Japan, Poland, South Korea, Spain, Sweden, Great Britain and the United States of America. Ipsos MORI compute an “index of ignorance” – but to some extent this may just be an index of innumeracy.

For example, the average American, when asked, guessed that 24% of girls aged 15-19 give birth each year. The actual value is 3%. In every country surveyed people were off by a factor of at least five. I’d posit that this is not a question of being uniformed so much as innumerate. If 24% of girls aged 15-19 give birth each year, and nobody gives birth before 15, then the average number of children of a woman at age twenty would be 1.2. Do people seriously think the average twenty-year-old woman has more than one child? I doubt it.

The other questions were percentage of Muslims (most people overestimate), Christians (most underestimate), immigrants (overestimate), percentage who voted in the last major election (underestimate), percentage “unemployed and looking for work” (overestimate), and life expectancy of a child born in 2014 (pretty much right on).

One of these numbers is not like the others. We’ll all die someday, and we all have some idea of how long people live, so we naturally get this right. But the others are asking for percentages, and I don’t think most people could tell the difference between “10% of people have this trait” and “20% of people have this trait” just by guessing. South Koreans and Japanese overestimate the number of Christians – and those are the two countries on this list in which Christians are a minority. I wonder, if you looked at the estimates people gave for a lot of these percentages, if they’d show a peak at 50%, the thought process being “well, people with trait X exist, but not everybody has trait X, so what’s a number in between? I’ll just pick the simplest rational number between 0 and 1.”

I’m a bit puzzled about the unemployment numbers, though. These are generally fairly loudly trumpeted in the media, so I’d expect people at least give estimates in line with those ranges, and yet, for example, the US guess is 32 percent. (The percentage of people “unemployed and looking for work” is actually lower than the unemployment rate, by definition, as the unemployment rate is the percentage of people in the labor force who are looking for work – the unemployment rate has the same numerator and a smaller denominator.) Even if people think about the experiences of those close to them instead of the public at large, on average this shouldn’t change things unless unemployed people happen to have lots of friends and family who take these surveys.

I’d also be interested to see how estimates correlated with political views. For example, are people who think there are more immigrants more likely to be anti-immigration? Do people who think the unemployment rate is higher support policies that would stimulate their nations’ economies?

Links for November 2

John Rauser of Pinterest gave a talk at the Strata Conference / Hadoop World on statistics without the agonizing pain – you replace the pain of statistics with the pain of simulation, which for an audience of programmers is much less painful. Via revolution analytics.

Surfacing this week on Hacker News was this article by NASA engineer Don Pettit on “The tyranny of the rocket equation”.

Tim Gowers writes on the results of an experiment concerning computer-generated mathematical writing.

Vi Hart made a scary Halloween video featuring candy corn and the Sierpinski calendar.

The video from the Online Encyclopedia of Integer Sequences conference is available online.