“Ben, you’re good. Alex, you’re good.” The sound of Mr. Jackson-Strong confirming that my brother and I were checked in and ready for study hall was exactly the same time every day—7:30 PM. Study hall started shortly after—at 7:45 PM, which left an awkward interval of time on our hands. In the Croft common room sat a ping-pong table, perfect for occupying that gap in our schedules. I handed Ben a paddle and we began to play. Ben is as good as I am at ping-pong, so each game we play could go either way—depending on if one of us can get a tricky spin or simply makes a blunder. When our match was over and we needed to head to study hall, it was pretty much an even split as to whoever was winning any given day. 

I decided that I’d had enough of losing to him, but I also wasn’t about to practice ping-pong drills for hours on end to try and outplay him (though with the length of this project that may have been the more time-economical solution). I was going to try and cheat my way into victory while still playing by the rules. 

It went a little something like this:

Score: 0-0

Ben wins

Score: 0-1

I win

Score: 1-1

I win

Score: 2-1

“Ok nerd, I win. I’m gonna head to study hall now,” I gloated

“But it doesn’t start for another—” Ben countered. I couldn’t hear the rest because I was already out the door.

Next day.

Score: 0-0

I win

Score: 1-0

“Alright that’s enough ping-pong, i’m gonna head to study hall. Looks like I win again”

And repeat. As of now, onlookers (at least those who’d been watching for the past two days) would’ve thought I was handily better than Ben—even though we were still equal. I wanted to know though—If I kept this up, how good would I look to onlookers? What was my expected win rate against Ben?

My first thought to solve this question was to map it out in a game tree, which looked like the picture below. Unfortunately, the tree rapidly expands to be unreadable, though it did gain me some insight into the problem. I learned that the game only ends on odd numbers of games and that the endings of the games are always X to X-1, where X is an integer.

I asked the math office and the science office for insight into the question. The math office tried to solve the question using statistical techniques to no avail. Dr. Peterson and Mr. Grant both suggested I simulate the question.

I decided to simulate the question. I asked Louis Ye and Zach Kamenov for help with simulating it. They suggested I learn the computer programming language Python. I downloaded the application Python3IDE, which runs python 1.6 on my computer. The first few days of my project were spent completing python tutorials on pythontutorial.net, a website which includes many resources for students learning python. This taught me about the major components of the language which will be of use to me in this project, including lists, which allow for expandable data storage, for loops, which repeat a certain action a specified number of times, and while loops, which allow for an action to be repeated while a condition is met. These, in conjunction with variables and the print command, were all I needed to create my first simulation.

Equipped with my new knowledge, I was ready to simulate a ping-pong match

Pictured is my code for a randomly generated match of ping-pong. 

Python is unable to natively generate random numbers, so I import the random module in line 2. 

My wins and losses both start at zero, which are set in lines 3 and 4.

Skipping to line 6, an “addition” variable is defined as a random integer, 0 or 1. This integer is added to my win count. 1-addition is equal to the other value, 0 or 1, which is then added to the loss counter. I then print the result so I can track the match as it progresses. 

The “while” loop on line 5 checks to see if losses are greater than or equal to the wins. It only iterates the steps listed above if this condition is met. 

Finally, on line 10, I print the final score. 

Monte Carlo is possibly the most famous casino in the world, making up a large portion of the GDP of the country Monaco. Monte Carlo is also the name of a statistical technique for statistical sampling, where a very large sample of numbers are selected, tested, and averaged to find a result. This method reduces the possibility of outliers to affect your data, if the sample size is large enough (similar to the Monte Carlo Casino, where one high-roller doesn’t significantly affect the casino’s profits)

Here’s how it works in my simulation:

I import the random module to allow for randomness simulation. The user submits a number of games it would like the program to run. 

This program is very similar to my initial simulation, except line 9 allows to loop it some number of times

Additionally, I’ve included an automatic winrate calculation. This works by adding each match’s winrate to a running counter, and dividing by the total number of matches at the end to find an average. 

Pictured is a test of the program having requested 10 matches. My computer has low processing power and was insufficient to properly test this simulation, so I had to borrow Louis Ye’s Razer Blade. I used it to run a test with 1,000,000 games as a sample size and recieved a number of around 78.4%±0.2%. This gave me a very good estimate of the answer, but would always be an estimate, even if I optimized it using C and was given access to a supercomputer to run my simulation. To solve this question, I had to try another option. 

In order to make my simulation accurate, I needed to remove its dependence on randomness. To do this, I needed to make it procedurally generated. I have a diagram below to show how a procedurally generated approach works. This diagram is similar to the diagram from chapter one. The code effectively expands that tree, but uses computing power to get much further. 

A list is created with all the matches simulated so far. In this case, the list would look like [1,0,2,1,1,2,1,2,0,3]. The winrate overall is calculated by dividing the wins index of the list (even numbers) by the wins index plus the losses index (odd numbers), then multiplying by a factor which determines how probable the game is to occur (this factor is a negative power of 2, calculated by adding the wins and losses). This is looped through the entire index to find the total winrate at that level. 

My code for doing this is shown below. 

The way the code works is that it iterates through the entire list, detecting each match to see if it both satisfies the continue condition (wins are less than or equal to losses) and it is the lowest total games played that hasn’t been iterated yet. If both are true, the entry is deleted and two new entries are added in their place, one with losses increased by one and one with wins increased by one. 

Also notable in my system is that matches below a winrate of 50% are increased to 50%. This is consistent with the law of large numbers, and allows this simulation to more quickly approach the winrate. 

Pictured is a test run of this version of the simulation. Immediately an issue is present: the list rapidly explodes in size, and the computer quickly becomes swamped even when simulating small numbers of games. 

I left the previous simulation on overnight and only got to a score of around 20. The number of matches per number of games grows so quickly that simulating it this way to any success was infeasible. I needed some way to speed up the process

If you refer to the previous simulation test, you can see that I have plenty of repeat terms simulated in the exact same way. If i could find a way to combine them and simulate them together, the computer would run much quicker. A diagram of what I am suggesting is shown directly above. 

My idea was to add a third term to the list to represent the number of a certain score in each simulation. Instead of [1,0,2,1,1,2,1,2,0,3], the list read [1,0,1,2,1,1,1,2,1,0,3,1]. Though this list is longer now, when the list expands to have many more cases, it will become much more efficient. This was by far the hardest challenge in this project, and the way I’ve programmed it is shown below. 

The program “scans” for repeats while scanning for the lowest games of the list at the same time. If a match is detected to have both the same number of games and the same wins as the current lowest match, it is added to a list and then subtracted later, and the number of copies of that list is added to the current lowest list’s copies before it is iterated. 

An issue I ran into while using this approach was that it would add larger games that are both repeats and the lowest in the list so far. This caused the values to be added to the actual smallest instead of the corresponding game. I solved this by including a sublist so that the values would be added to the correct matches. 

This was very good at compressing the simulation. My computer was able to run completely absurd amounts of games in very short amounts of time. The winrate quickly approached an asymptote of around 78.54% after just a few seconds of simulation. I let it run for a few minutes on Louis’s computer to allow it to approach a number. 

Just visualize, for a second, each atom in the universe. If each atom held its own universe, each with my brother and I playing ping-pong from the beginning of time until the heat death of the universe

.

That’s how many games of ping-pong this simulation was able to compute in 5 minutes. The winrate was just below 78.54%. 

This, however, was also not perfect. I had a number which was clearly irrational. No matter how many universes I let this computer run through entirely contained with ping-pong, I would not know the exact number purely with a simulation approach. 

All this simulation did, however, turn out to be extremely helpful in finding a pure approach to the question.

Since my simulation was able to generate the smaller numbers perfectly, i could accurately describe the numbers of games ended at each step. All that would be needed was the simulation to describe the first terms of a pattern and me to extrapolate from there. 

1,1,2,5,14,42,132,429,1430,4862...

A graph on Desmos is shown below 

This number series is a documented number series in math known as the Catalan Series. The Catalan series shows up occasionally in combinatoric problems and is defined by the equation:

(2n-2)!/(n)!(n-1)!

A Desmos Graph of it is shown below.

Another way to express the Catalan series with respect to this problem is this “halfscal’s triangle”, an analog of Pascal’s triangle bounded on one side. This series shows the number of games which win at each win number. 

It turns out that during my time doing math to calculate my winrate for ping-pong, Ben has been practicing ping-pong. He can now beat me more than half of the time. My calculations have been thrown out the window. I need a new simulation that is capable of withstanding uneven probability inputs, and I need to know if I can still beat my brother at ping-pong. 

The first thing I need to do is to find out exactly when to stop playing. For the 50-50 simulation, it’s obvious: stop playing when you’re ahead.

But why do we stop when we’re ahead? The winrate of the two continuations of the sequence, when averaged together, is less than the winrate of the current sequence. This implies that we have beaten the odds and continuing would be unwise. (Ignore the possibility of continuing the sequence continuations. This will be covered later) 

When factoring in any winrate, not just 50%, we use the following formula to decide when to stop:

wins > winrate(wins+losses)

Putting this into my code for the Monte Carlo simulations allows me to input any individual game winrate and find a resulting approximate expected winrate. For example, I ran the simulation for 10% winrate over 10000 games and got an expected winrate of around 27%. 

Once again, I need to create a deterministic version of this equation. this is much harder than the original, as the games can't simply be stored in a list. ]

After much deliberation, I decided to update the compression algorithm code to be able to change the winrate. This was very difficult, considering the current sequence took a sequence and created two new ones, with no respect to the probabilities of each event. I could either write a formula to factor that in, which would be a monumental task, or I could try something else.

What I did was include the probability with the number of games played. Instead of creating two games, I only had one game, separated among the two continuations with respect to probability. For example, the game 0-0 with 1 instance used to be separated to 1-0 with 1 instance and 0-1 with 1 instance. Now, it was separated to 1-0 with [probability] instances and 0-1 with [1-probability] instances. 

Not only did this fix the issue of not allowing a probability input, but it also made the computing faster as the winrate calculations were done in the same step as the list creation.

There were still two issues with this situation:

1. It did not give me a completely accurate answer to the question of winrate

2. The numbers i was making python use were very small

Problem 1 is very hard to solve. I would need to rewrite the program to separate winrate and probability so my summation is compatible with the program.

Problem 2 isn’t really a limitation given that the program gives me good approximations anyways, but Python3IDE treats my small numbers on the order of 10^-300 as though they were zero, lowering the actual win percentage.