Bowler Problems

This week’s problem of calculating the probability of the last pin being knocked down in a rhombus of bowling pins is difficult or impossible to calculate exactly without simulation for large N. I started by using a simplified probability model which turns out to have a lot of the same features as the correct simulated calculation and turned out to be what looks like an an upper bound.

We start by calculating a 2D grid with valid entries where the N^2 pins are located and each entry represents the probability of a pin falling down. The combined probability P of a pin being knocked down by either of its one or two predecessors, conditional on either of them having fallen is:

P(pin falling) = 1 – [ (1 – p*P(pin 1 above falling)) * (1 – p*P(pin 2 above falling)) ]

If pin 2 does not exist, as in the edge cases, P(pin 2 above falling) = 0 and the calculation can be identical for all the valid pin entries in a square grid, with entries without pins set to 0. This calculation is not exactly correct as the probabilities of the nodes in the 2D multiply connected grid are not really independent.

Propagating these probabilities for n=5, with the first pin going down with certainty, we see some interesting behavior already:

There are a few interesting things about the above conditional probability calculation:

  • At probabilities around .5 and below it appears that the last pin will show a rapidly decreasing probability of being knocked down.
  • It is possible for a pin to have a greater probability of being knocked down than its immediate two predecessors.
  • There is a condition where the probability of a pin falling equals the two pin probabilities above it and the grid will tend to “lock-up” at a constant probability in the middle. This condition can be calculated by setting all P’s in the first equation above equal, and is:

P = (2p-1)/ p^2

By calculating much larger grids and observing the results it appears that for large N and p > .5 this happens to all grids in the center region as the edge probabilities become irrelevant, and this probability ends up being the probability of the last pin falling down. For p <=.5 the probability of the last pin falling down appears to go to zero for large N.

Below are the last pin falling probabilities estimated with the stability condition and a grid calculation at N= 500. Again, remember these are not exact results but probably more like upper bounds:

p(pin falls)(2p-1)/p^2P(last pin falls): Grid N = 500

Focusing in on the critical p=.50 at larger N:

p(pin falls)(1-2p)/p^2P(last pin falls): Grid N= 5000P(last pin falls): Grid N = 10000

And we note that crucially the p = .500 values are decreasing with increasing N, while values above p =.500 are still stabilizing and actually increasing at this stage. So this imperfect upper bound calculation shows a sharp transition point at .p= .500.

To get exact values we will need to run a simulation. Note we will need 2 random numbers per pin to account for the separate probabilities of striking the two pins underneath.

The simulation behaves a bit differently than our upper-bound calculation and it appears to show a transition point appears at around .600 or so (this sim is N=50 at 1000 reps):

Zooming in:

And here are results with N=100 and 5,000 reps:

p(pin falls)P(last pin falls): Simulation Grid, N= 100, 5,000 Reps

It is difficult to know how stable these results will be with large N and e.g. how sharp the stability cut-off is. The assumption is it gets sharper as N gets larger judging by our simplified probability model results.

Finally, I ran one simulation for p = .700 at N=200 and 10,000 reps and got a result of P= .579 , so I guess that is the end of it for now and we decide that Fosse will win this Battle of the Bowlers 57.9% of the time with the remaining 42.1% being draws. Probably.

Code for the probability calculation:

Somewhat inefficient code for the simulation:

Bowler Problems

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s