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!

I am back on campus in Waterloo, which means the talk season is now open again. The first talk I attended this term is a public lecture by Gerald Jay Sussman, the Panasonic Professor of Electrical Engineering at MIT. He gave a pretty interesting presentation on how programming provides us with a set of tools to express ourselves. Here is the video.

It has been a while since I posted anything here. I started working at Facebook in Palo Alto last week. I have to admit it is pretty different from my previous work term. First, the working hours are way different from what I’m used to. I have to reconsider my definition of being late and leaving late. One good thing is that there are a lot of smart people working there and some unbelievably interesting projects. You can’t get a better work environment when it comes to motivation. I have to say the free food is also pretty good. The company is also really open with its employees, holding regular talks where everybody is invited to discuss issues and new projects.

For those interested in getting a job there, here are a couple of tips I learned from my interviews. First, do stuff on you own. Everybody does the school projects, that doesn’t make you special. Don’t go over the “reverse a linked list” or “how do I find anagrams” algorithms before your interview, you would be losing your times. They come up with unusual questions that are not too hard, but that require some knowledge of basic algorithm concepts (e.g. dynamic programming) and that test your problem solving skills, not your memory. If your want to train for these, Project Euler is a good place to start. Also, make sure to visit their programming puzzles page.

Last week I assisted to a tech talk by a Senior Hardware Engineer for the Zune team at Microsoft Entertainment & Devices. He went over a number of subjects, ranging from cloud computing to handheld devices. A pretty good talk overall and a good look at what might come in the future at Microsoft. I managed to film everything, but not from the best angle.

Last Friday, Yahoo! was back at the University of Waterloo for Hack U 2009. After a week of talks by web gurus, such as Rasmus Lerdorf and Douglas Crockford, came the 24 hours hack event. This year, we decided to do something useful and in this tough economic time, we ended up creating a mashup to follow job trends across the United States. We scraped all the data we could from the U.S. Bureau of Labor Statistics, making it possible to search for statistics and open positions relevant to a certain type of job. We then display the result on a map using different metrics such as the average salary or the number of workers.

The result is called JobU and can be found here: http://renaudbourassa.com/projects/jobu/.

We won 4th place (when really, we should have won at least 3rd). The first place went to Docuvine, a really interesting web application that mimics Google Wave. Here are some picture of the event.

For more pictures of the event, see Rasmus Lerdorf or Jamie Lockwood flickr photostream.