How a Lottery Quest Led Me to The Powers of PyTorch

Introduction

At some point in time, you have probably heard that your chances of winning a lottery are very slim. As with all things related to probability, multiple trials might tilt an outcome in your favor. Now, if you were to participate in many lotteries, your chances of winning one would be a bit better, depending on how many more lotteries you participated in. This is still by no means a guarantee that you will eventually win, but with (in this case meaning a large number of lotteries), we can arrive at relatively more likely possibilities.

It's important to understand that each new lottery is independent of any other, and the same lottery "ticket number" could win many different lotteries (following the law of large numbers). You could also be unlucky and pick the wrong number in every lottery, regardless of how many times you tried. You have two options now:

1. You can try a random number every time.


2. You can try the same number every time.

Theoretically (and mathematically), both scenarios have an equal likelihood of occurring. However, scenario 2 will give you a slight edge. As the number of times approaches infinity, every number will eventually be selected. The problem is that with scenario 1, you need to try more times with the hope that the number you've picked at the time matches the number that wins. With scenario 2, you're sure that as the trials tend to infinity, your number will at some point "win". For this blog post, we will use scenario 2.

So, do you think you can answer this question before I tell you the answer?

"If all lotteries around you had slots for exactly 1 million people and you picked the same ticket [x] for everyone you played, how many lotteries would you have to play to finally be a winner?" (Feel free to comment on what your initial answer was)

The answer is...

The Logic

The ticket numbers of a lottery of 1 million people would range from 1 - 1,000,000 (or 0 - 999,999). Players can only pick a number within that range for each lottery, and the winning ticket can only be from that range. Essentially, we can say we will have a set of 1 million numbers.

Accounting for the fact that a user can pick any number within that range, we need to satisfy the condition of every item in the set being hit at least once. This is because if every number has been called at least once, it would cover any possible ticket number a player could have picked. This also means we do not care about how many times each number runs, making a "set" the ideal Python data structure to use for our simulation. We will start with an empty set, and populate it with a randomly generated number at each iteration until the set contains every number within the specified range. Since Python sets do not repeat numbers, we do not have to worry about ensuring uniqueness.

def calculate_lottery_chances(lottery_players_count):

  number_set = set()

  count = 0



  while len(number_set) < lottery_players_count:

    gen_number = random.randint(1, lottery_players_count)

    number_set.add(gen_number)

    count += 1



  return count

For a lottery of 1,000,000 people, the function call would look like: calculate_lottery_chances(1000000), and it would return the number of lottery attempts before winning. Arranging the code in this manner makes it very extendable.

.

Output

To ensure my GPU was used during execution, I opened my Windows task manager and navigated to the "performance" section before running. On running, I saw a noticeable spike in GPU resource usage.

For context, here is a before vs after:

Before:

Notice the GPU usage is at 49%

For the runtimes for varying values of n, the GPU was several times faster. It ran values of n below 100 consistently at less than a minute, and was able to calculate for a value of n at 5000 (five thousand!)

Here's a table of runtimes using the GPU:

To have a visual sense of how large the performance gap between the GPU and CPU operations was for this experiment, here's a data visualization to think about:

The x-axis was capped at 100 because I could no longer get realistically "timely" output from the CPU, thus leaving no room for comparison with the GPU. Performing the experiments with numbers within the range of 1000 - 5000 gave me about "14.4 million times" as a result, more often than not. That's how I got the answer from earlier.

Caveats

This experiment made assumptions and relied on certain ways of doing things. Additionally, my inexperience with PyTorch potentially means there may have been a more efficient approach. Here are some factors to consider that may have influenced either the accuracy of my findings or the execution times:

1. I made a subtle assumption that computer-generated randomness mimics randomness in real life (the physical world).


2. While I switched a bit of the logic to use PyTorch, the rest of the code still relied on the CPU. For instance, in the average_over_n_times() function, it's possible that both the addition in the loop and the averaging may have benefitted from PyTorch equivalents. I suspect there would have been a performance boost.


3. I'm unsure of the impact of the batch_size I used on accuracy and performance.


4. All CPU and GPU tests were done with my PC plugged in, to allow the machine to work at its best. Running them with a device on battery power may see longer runtimes.


5. PyTorch's CUDA might have the edge over "XPU", but my PC doesn't have support for the former.


6. I avoided letting my PC "sleep" during the tests. Tests may potentially take longer to run if your computer sleeps.

Finally, I'd like to point out that this was my first time using PyTorch for anything, and I was quite impressed with the performance.

Conclusion

When I went down the rabbit hole with this, I didn't expect to see such gains in performance. I learned the idea behind tensors and a few things about the supporting mechanisms behind even more computationally complex tasks. You have the freedom to use, replicate, or modify the code snippets as you please.

Thank you for indulging me, and I hope you had a fun read.

Till next time,

Cheers. 🥂