As part of my Introduction to Computer Vision class, I got to implement and analyze an algorithm of my choice. I ended up picking the Greedy Snake algorithm as described by Williams and Shah. Snakes are active contour models which, when positioned near an object, tend to converge to its edges. They are thus useful to track or find objects within an image given a decent initial guess. One interesting application of this algorithm is in video tracking, where the output from one frame can be used as the input to the following frame, making it possible to track the object’s position from frame to frame cheaply.

If you are interested in the details, I posted the MATLAB code as well as the analysis on Github, so go ahead and fork it!

It has been nearly a year since I wrote my last post while travelling to Istanbul. It thus seems like an appropriate time to refresh this blog with some sort of update about what I have been up to.

After a stop in Manhattan over the summer where I interned at Bloomberg, I am now in Redmond, WA working for the tech giant that is Microsoft. Spending the summer living in the West Village, at the heart of New York City, has been an incredible experience. It is a beautiful city that never ceases to surprise you with new things to do. Getting the opportunity to work at Bloomberg on risk analysis was also an interesting experience.

However, after four months in a forest of glass and concrete, Redmond and its giant trees already feels like a nice break. There I have joined the Xbox team, with which I will be spending the next four months. My goal for this internship is to try something different and gain as much knowledge about the field as possible. I don’t know much about the specifics of the project I will be working on, but I already received my Xbox gear to practice in the meantime.

I got back on campus last weekend after a week stop in Istanbul. I have to say, the city is full of amazing things to see, but one thing in particular got my attention. When I first got hold of a Turkish 10 lira bill, I noticed a mathematical formula written in small on its reverse side. After an afternoon of wondering what this formula was all about, I got back to the hotel and 10 minutes later, I was reading the Wikipedia article on the Arf invariant.

I wish more countries had mathematics written on their currency.

Today, during my microeconomics class at UC Berkeley, I came across an interesting paradox that reminded me of one of The Drunkard’s Walk main thesis. In his book, Leonard Mlodinow argues that most people react badly to situation involving probabilities due to their inaptitude at calculating probabilistic outcomes correclty. The St. Petersburg paradox is a perfect example of this.

The St. Petersburg paradox takes the form of a lottery, where the player buys his way in for a fixed fee. The dealer then puts a dollar in a jar and flip a coin. If the coin ends on tail, the game is over and the player takes the money currently in the jar. However, if it ends on head, the amount in the jar is doubled and the coin is flipped again. This is repeated until a head appears and the player takes the money in the jar.

Now, the paradox doesn’t come from the game itself, but from the fixed fee. The question is, how much would you be willing to pay to enter the game? When asked this question, most people are reluctant to put more than $25. An easy way to calculate the maximum amount a person should be willing to put is to calculate the expected value of the game. A rational person would not bet more than its expected gain. But what is the expected gain of the game exactly? Here are a list of possible gains and their probability.

And so the expected gain can be calculated by adding the individual gains multiplied by their probability of happening.

Which is a series that does not converge.

And results in an infinite expected gain. So what does that mean? That means that you should be ready to pay any fixed fee to enter the lottery. This may seems counter intuitive at first, but here is the result of a simulation using a simple python script with an initial fee of $25 and 500,000 repetitions.

As can be seen, the final gain is more than $4,000,000! So next time you gamble in St. Petersburg, don’t hesitate to borrow.

Here is the code used for the simulation.

#!/usr/bin/env python2.7
#
# Copyright 2010 Renaud Bourassa

"""
A simple simulation for the St. Petersburg Paradox. Run the simulation and then
plots the results.
"""

__author__  = 'Renaud Bourassa'
__version__ = '1.0.0'

import random
import sys
import matplotlib.pyplot as plt

class Lottery(object):
    """
    Simple Lottery object to simulate one or more game of St. Petersburg lottery
    and keep track of the balance of the player.
    """
    def __init__(self, fee, balance=0):
        """
        Sets the fee and initial balance.
        """
        self.fee = fee
        self.bal = balance

    def play(self):
        """
        Plays one game, returning the resulting balance.
        """
        pot = 1
        while int(random.random() * 2):
            pot *= 2
        self.bal += pot - self.fee
        return self.bal

    def multi_play(self, num_plays):
        """
        Plays multiple games, returning an history of the balance as alist.
        """
        return [self.play() for _ in range(num_plays)]

def get_args():
    """
    Tries to parse the command line arguments.
    """
    try:
        fee = int(sys.argv[1])
        num = int(sys.argv[2])
        bal = int(sys.argv[3]) if len(sys.argv) > 3 else 0
        return {'fee':fee, 'num':num, 'bal':bal}
    except:
        print "usage: %s FEE PLAYS [BALANCE]" % (sys.argv[0])
        return None

if __name__ == "__main__":
    """
    Runs a simulation and graph the results.
    """
    args = get_args()
    if args:
        l = Lottery(args['fee'], args['bal'])
        plt.plot(l.multi_play(args['num']))
        plt.show()

Here is a follow up to my previous post with another talk by Gerald Jay Sussman at the University of Waterloo. This time it is on propagators, an interesting architecture pattern inspired by electronic circuits. Enjoy!