## Metric and Probability-Based Recommendations

How many of you like to eat, play, and most importantly, drink? (Hopefully, everyone!)

I helped create an app called LocALL. It gives 50,000 recommendations for short trips to eat, play, and drink and support local businesses in Austin. We can extend our app to cover ~400 metropolitan cities in the US and create 20 million recommendations. (Big data and machine learning!)

At the heart of our solution is math. We used spherical geometry and probability to create simple, fast recommendations.

## Monte Carlo Simulations: Buffon’s Needle

Buffon’s needle is a classic Monte Carlo simulation that we can conduct in a classroom. We give the students, say 10 needles each, and have them drop the needles on a paper that we provide also. The paper is special, in that it has parallel lines that are separated by the length of a needle. Each student records how many needles intersect one of the lines, then we tally their numbers to arrive at a very special number. (Guess who?)

In a class of 30, we have 300 samples to determine this special number. If the students had repeated the experiment ten times (any more than this risks frustration and wrath), we would have 3,000 samples at best. But with a computer program, we can make a million samples easily. In less than a second!

So today, we will learn how to write a program that generates needles (line segments). Our program needs to determine if a needle intersects a line. In general, checking if two line segments intersect is not an easy task. It’s rather amazing how we can look at many line segments (like the ones in the picture above) and instantly tell which lines intersect with which others. In our problem, fortunately, the lines on the paper are parallel and are equally spaced apart. We can use this fact to come up with a simple solution. Lastly, we will learn how to vectorize our code. Vectorization allows us to arrive at the answer quickly.

## Monte Carlo Simulations: Penney’s Game

An n-gram is a word of length $n$ that we can create from a set of letters. With two letters $\{\mbox{T}, \mbox{H}\}$, we can form these 3-grams: $\mbox{TTT}$, $\mbox{TTH}$, $\mbox{THT}$, $\mbox{THH}$, $\mbox{HTT}$, $\mbox{HTH}$, $\mbox{HHT}$, and $\mbox{HHH}$. We will let $\mbox{T}$ stand for tails and $\mbox{H}$ for heads, so that a 3-gram can represent an outcome if we flip a coin 3 times.

Penney’s game concerns two good friends and their $n$-grams. The game is simple and seemingly fair. Soon Player 1 will call off their long friendship and leave, however. We will find that, whenever $n \geq 3$, Player 2 is always more likely to win.

## Monte Carlo Simulations: Craps

I want to begin our coding adventure with something simple yet useful in many areas. I think that has to be using Monte Carlo simulation to solve a problem, especially that for which we do not know the exact solution.

In essence, there are 2 stages for implementing a Monte Carlo simulation:

1. Input stage: Define a set of possible inputs for the problem. Randomly generate $N$ inputs from this set. We can do this one at a time, or altogether.
2. Output stage: For each generated input, find the output by following the problem description. I will refer to this “give me an input and I’ll give you an output” as a simulation. Combine the $N$ outputs to arrive at some meaningful result.

The benefit of a computer program shines in both stages. Our computer can create many inputs and evaluate their outputs much faster than we can.

Over the next few posts, we will examine how we can apply Monte Carlo simulation to solve problems in probability and integration. Whenever possible, we will consider the exact solution and see how good our approximate solution is.