Advice for Mathematicians: Randomly Choosing a Direction

Suppose you want to randomly choose a direction. Maybe you’re a neutrophil, a type of immune cell, and you’re searching for a bacteria. Which direction should you choose? Maybe you’re coding, or building a mathematical model and you want to choose a random direction to move in. Let’s begin by asking a more specific question.

How do you uniformly choose a direction in 2-dimensions?

I think that the easiest thing to do is to uniformly pick an angle, \theta \in [0, 2 \pi), and then convert to a vector on the unit circle:

x=\cos \theta, \qquad y=\sin \theta.

direction

This method works! If you sample 100 points from a uniform distribution on \theta \in [0,2\pi), and plot the result, it looks pretty uniform on the unit circle:

CirclePointPicking100

The reason this works is that we want any little segment of arc length on the unit circle to have the same number of points. In terms of differentials (arc-length-elements and theta-elements), we have

ds = \sqrt{dx^2 + dy^2} = \sqrt{d\theta^2} = d\theta

because x = \cos \theta and y = \sin \theta.

Does the same method work in 3-dimensions?

Interestingly, no! If you were to randomly choose two angles \theta \in [0, 2\pi) and \phi \in [0, \pi], and use spherical coordinates

x = \cos \theta \sin \phi, \quad y = \sin \theta \sin \phi, \quad z = \cos \phi,

then you would observe cluster of points at the poles. You can see this in the figure on the left, or by looking at a top down view, as on the right:

spheretopdown

This method fails in 3D due to the fact that not all latitudes have the same circumference! In other words, our method breaks because the area element

d \Omega = \sin \phi d \theta d \phi

is a function of \phi. Note that you could choose a transformation other than spherical coordinates so that this works nicely if you wanted to (http://mathworld.wolfram.com/SpherePointPicking.html).

n-dimensional uniform distributions on the unit sphere.

It turns out that one of the easiest ways generate a uniform distribution on the n-dimension unit sphere is to actually use n normal distributions…

The density function for a normally distributed random variable vector X is

p(x; \mu,\Sigma) = \frac{1}{\sqrt{ (2 \pi)^n \det(\Sigma)}} \exp \left( -\frac{1}{2} (x-\mu)^T \Sigma^{-1} (x-\mu) \right).

For the sake of example, consider the case where the covariance is identity, \Sigma = I, and the mean is \mu = \vec{0}. Then

p(x;0,I) = \frac{1}{\sqrt{ (2 \pi)^n}} \exp \left( -\frac{1}{2} \sum_{i=1}^n x_i^2 \right) \\  = \frac{1}{\sqrt{ 2 \pi}} \exp \left( -\frac{x_1^2}{2} \right) \cdot \ldots \cdot \frac{1}{\sqrt{ 2 \pi}} \exp \left( -\frac{x_n^2}{2} \right).

In general, we can conclude that a n-dimensional Gaussian with mean \mu \in \mathbb{R}^n and diagonal covariance matrix \Sigma = \text{diag}(\sigma_1^2, \dots, \sigma_n^2) is the same as a collection of n independent Gaussian random variables with mean \mu_i and variance \sigma_i^2.

From this, we can sample uniformly random points on the n-dimension unit sphere by

  1. Generate n standard normal random variables x_i,
  2. and normalizing: \frac{1}{\sqrt{x_1^2 + \cdots + x_n^2}} (x_1,\dots,x_n)^T.

On the unit sphere in n-dimensions, \sum_{i=1}^n x_i^2 = 1,

p(x;0,I) = \frac{1}{\sqrt{ (2 \pi)^n}} \exp \left( -\frac{1}{2} \sum_{i=1}^n x_i^2 \right) = \frac{e^{-\frac{1}{2}}}{\sqrt{ (2 \pi)^n}}

is spherically symmetric, i.e., the distribution is constant!

This works! No clustering!

sphere_correcttopdown_correct

Advertisements

The Travelling Beer Problem

I saw a link to a map containing place markers for most (if not all) of the beer breweries in British Columbia, and someone had suggested that this map led to the “ultimate” Travelling Salesman Problem. I didn’t need any additional motivation to try and figure out the best possible route!

The Travelling Beer Problem: You wish to visit all the beer breweries in B.C. and you wish to do so while traveling the shortest distance.

Solution

Step 1: Learn about the Travelling Salesman Problem. Thank you, Wikipedia.

Step 2: Scrape Google Maps for a complete listing of BC Breweries.

Easily enough, it is possible to download a Google Map as an KML file which contains information about each place mark, such as name, latitude, and longitude. Furthermore, a quick search revealed a handy MATLAB script for converting KML files to MATLAB structural variables. Thank you, kml2struct. After a couple quick edits to the file to only obtain the data I was interested in, I had all the data required.

Step 3: The Travelling Salesman Problem is one of the most studied problems in optimization; however, when I first saw this problem I was simply thirsty for a solution. As a result, I didn’t spend a lot of time reading and learning about what I actually did to find a solution. I also don’t mean to be an overly enthusiastic MATLAB cheerleader, but the MATLAB documentation contains an example of how to use integer programming to solve the Traveling Salesman Problem. I happily borrowed that code. Look for a future post discussing how this actually works.

Step 4: Cheers!

beerbig

bits of string too short to save

A bit about the short subtitle.

A friend once told me the story about how he helped another friend clean out a decreased grandmother’s house.

“She was a labeller,” he said. “Everything had labels.”

Knives. Forks. Plates. Glasses. Jars. Junk. Standing from the centre of the kitchen, he could deduce the contents behind each closed door by reading the label. Opening each cupboard revealed the treasured contents. A collection of knives. A pile of forks. A stack of plates.

And sure enough, in the drawer labelled “bits of string too short to save” was a collection of pieces of yarn, string, and twine all too short to be useful.

However funny, I think my friend plagiarized this story. A quick google search reveals a book…

http://www.godine.com/book/string-too-short-to-be-saved/