K successes in Bernoulli trials, or George Lucas movie experiment

Question

I'm reading "The Drunkard's Walk" now and cannot understand one story from it.

Here it goes:

Imagine that George Lucas makes a new Star Wars film and in one test market decides to perform a crazy experiment. He releases the identical film under two titles: "Star Wars: Episode A" and "Star Wars: Episode B". Each film has its own marketing campaign and distribution schedule, with the corresponding details identical except that the trailers and ads for one film say "Episode A" and those for the other, "Episode B".

Now we make a contest out of it. Which film will be more popular? Say we look at the first 20,000 moviegoers and record the film they choose to see (ignoring those die-hard fans who will go to both and then insist there were subtle but meaningful differences between the two). Since the films and their marketing campaigns are identical, we can mathematically model the game this way: Imagine lining up all the viewers in a row and flipping a coin for each viewer in turn. If the coin lands heads up, he or she sees Episode A; if the coin lands tails up, it’s Episode B. Because the coin has an equal chance of coming up either way, you might think that in this experimental box office war each film should be in the lead about half the time.

But the mathematics of randomness says otherwise: the most probable number of changes in the lead is 0, and it is 88 times more probable that one of the two films will lead through all 20,000 customers than it is that, say, the lead continuously seesaws"

I, probably incorrectly, attribute this to a plain Bernoulli trials problem, and must say I fail to see why the leader won't seesaw on average! Can anyone explain?

Answer 1

Here is some R code to simulate the George Lucas experiment:

B<-20000
steps<-2*rbinom(B,1,0.5)-1
rw<-cumsum(steps)
ts.plot(rw,xlab="Number of customers",ylab="Difference")

Running it, we get pictures like these:

where the difference in sold tickets between A and B is on the y-axis.

Next, we run $10,000$ such simulated George Lucas experiments. For each experiment, we compute the proportion of time spent $\geq 0$, i.e. the proportion of the lined-up viewers for which the number of tickets sold to A is greater or equal to the number of tickets sold to B. Intuitively, you'd say that this proportion should be roughly $1/2$. Here is a histogram of the results:

The proportion is $1/2$ on average in the sense that the expected value is $1/2$, but $1/2$ is an unlikely value compared to values close to $0$ or $1$. For most experiments, the differences are either positive or negative most of the time!

The red curve is the density function of the arcsine distribution, also known as the $\mbox{Beta}(1/2,1/2)$ distribution. What is illustrated in the above picture is a theorem known as the first arscine law for random walks, which says that as the number of steps of the simple symmetric random walk approaches infinity, the distribution of the proportion of time spent above $0$ tends to the arcsine distribution. A standard reference for this result is Section III.4 of An introduction to probability theory and its applications , Vol 1 by William Feller.

---

The R code for the simulation study is

prop<-vector(length=10000)
for(i in 1:10000)
{
    steps<-2*rbinom(B,1,0.5)-1
    rw<-cumsum(steps)
    prop[i]<-sum(rw>=0)/B
}
hist(prop,freq=FALSE,xlab="Proportion of time spent above 0",main="George Lucas experiment")
curve(dbeta(x,1/2,1/2),0,1,col=2,add=TRUE)

Answer 2

Both A and B have a $1/2$ chance to be ahead after any odd number of trials $t$ (odd to avoid ties). However, these events are related. Whichever is ahead after $t=1$ has a $3/4$ chance to be ahead after $t=3$, and this gets more dramatic as $t$ increases.

The average number of lead changes does grow to infinity as the total number of trials increases, but slowly. A random walk without drift in $1$ dimension is recurrent, so however far you may be in the lead, the chance you will be tied at some point in the future (with an infinite number of trials) is $1$. However, even if you lead by only one, the expected time until you are even again is infinite. There is a significant chance that it will take an extremely long time to get back to even.

That said, the mode is being used to exaggerate the effect. It actually would be a surprise to see no lead changes at all in $20,000$ trials.

If you would like to compute some of the probabilities, you have to count something akin to lattice walks which don't cross the diagonal. There is a great combinatorial method which applies to random walks (and to Brownian motion) which don't cross such a line, called the reflection principle or reflection method. This is one method to determine the Catalan numbers. Here are two other applications:

The number of sequences so that $A$ ends up ahead $10,200-9,800$ is $20,000 \choose 9,800$. In each sequence ending up at $(10,200, 9,800)$, either $B$ is never in the lead, or there is some point at which $B$ is first in the lead. If $B$ gains the lead, then if you reverse the later trials, you get a sequence ending up at $(9,799, 10,201)$, and this is a bijection. So, the number of sequences which end up at $(10,200, 9,800)$ so that $B$ was never in the lead is ${20,000 \choose 9,800} - {20,000 \choose 10,201} = {20,000 \choose 9,800} - {20,000 \choose 9,799} = {20,000 \choose 9,800} \frac{401}{10,201}.$ So, you can see that the chance $B$ was ahead at some point, given that you end up at $(10,200, 9,800),$ is about $96\%$.

The total number of sequences with any endpoint so that $A$ is never behind is ${20,000 \choose 10,000} \approx 2^{20,000}/\sqrt{10,000 \pi}.$ So, the probability that $A$ is never behind is about $\frac{1}{100 \sqrt{\pi}}$. The chance that the lead never changes is about $\frac{1}{50 \sqrt{\pi}} \approx 1/89.$ The average number of lead changes is about $56$.

Answer 3

"it is 88 times more probable that one of the two films will lead through all 20,000 customers than it is that, say, the lead continuously seesaws"

In plain English: one of the movies gets an early lead. It has to, as the first customer has to go to A or B. That movie is then just as likely to keep its lead as lose it.

88 times more likely sounds, well, unlikely, until you remember that perfect seesawing is very improbable. The chart in MansT's answer, showing this graphically, is fascinating isn't it.

ASIDE: Personally, I think it'll be more than 88 times - due to <buzzword-alert> viral marketing </buzzword-alert>. Each person will ask other people what they saw, and are more likely to visit the same movie. They'll even do this subconsciously: people are more likely to join a long queue to go an see something. I.e. as soon as randomness amongst the first few customers has created a leader, human psychology will keep it as a leader :-).