# Calculating Odds

I came across an interesting dice game called “Cubes” (which is essentially a simple version of craps) recently and decided to calculate the odds. This post will be interesting if you have some background in Probability and Calculus. It will be even more interesting if you don’t and are curious to know what these maths can do.

## The Game

A player of Cubes places a bet and two six-sided die are rolled. If the sum of the die is 7 or 11 the player wins twice the pot. If the sum of the die is 2, 3, or 12 the player loses the pot. Otherwise the number rolled becomes the player’s “point” and the player makes another bet (which goes into the pot with the first bet) and rolls again. If the player rolls his point he gets twice the pot, if he rolls a 7 he loses. The player keeps betting and rolling until he either loses or wins.

The game is interesting because it’s not immediately obvious how the odds work out. Consider the first roll. The player can win with a 7 or 11 which have probabilities:

and lose with a 2, 3, or 12 which have probabilities:

Below is a simple probability table for reference.

Anyway it would appear upon first inspection that your odds of winning are twice as good as your odds of loosing. Very good. But what about when the player rolls something other than a 7, 11, 2, 3, or 12 and it becomes his “point”? In this case the player has a higher probability of rolling a 7 (note this is the most frequent number in the table above) than any of the possible “points” he could have rolled. At this point the game is a loosing battle. However the player started with much better odds of winning outright. So which of these competing forces wins out?

To figure this out we’ll use some basic Probability and Calculus. We wish to determine the probability of winning a game of cubes. To do this we need to sum up the probability of every way in which we can win. If you’re not familiar with the axioms of probability consider a simple example:

## Warning: Balls in Urn Example

Imagine you have an urn with red ball, a blue ball, and a black ball of equal size, shape, etc.. You win a prize (penguin) if you draw any two balls from the urn and one is red without looking into the urn. What are the possible combinations?

red blue | red black | blue black

Three different combinations, each equally likely. Two of these will win us a penguin. To determine the chance of winning we simply sum the probability (1/3) of each of the combinations that allows us to win. This gives us 2/3 which makes good sense given two of the three options will win use the penguin

Back to the game of Cubes. Now just as in the urn example we must sum up each of the possible ways (or events) in which we can win the game. We already know one event that will lead us to win: rolling a 7 or 11 during the first round (with a 2/9 probability). Now we just need to figure out the remaining ways we can win and add them up.

The only other way we can win is by rolling our “point” before a seven. To get to a point round in the first place we must not have one outright and not have lost out right. Let’s consider the event where we get to the point round by rolling a 5 and win:

Here we have the probability of getting to the first point round multiplied by the probability of rolling a 5. This event constitutes a win, so we’ll add to to our sum. Let’s generalize a bit and call the probability of rolling our point (in this case 5) q. We’ll also expand the idea such that we capture the case where we roll our point after one failure, two failures, etc.:

Where the new term in brackets is the probability of not rolling your point or a 7 (which allows the player to move to the next round). Note this term’s exponent increases by one each turn as the player must continue to not roll his point or a 7. This series is infinite as it’s possible for the rolling to go on forever. Let’s make it look nicer:

This is a geometric series with a closed form solution. I’ll leave the proof of the closed for solution and the algebra to the reader. We end up with a very clean result:

We’re almost done. We’ve accounted for an infinite number of rolls events that lead up to a win but for only a single value of q. We need to adjust this solution slightly such that it accounts for the different possible point values a player could roll and their corresponding probabilities. It turns out we only need to worry about three values of q since 4, 5, 6 and 10, 9, 8 have the same respective probabilities. We multiply each of these possible values of q with the probability that we rolled that point value. For example a player could roll a 4 or a 10 with a probability of 6/36 = 1/6 which would give us a q value of 3/36.

This give us 0.4929292…. It’s actually quite remarkable this game is so close to fair. In any case over a large number of trials we expect to loose. Not a good bet, but a great analysis.

# Irreverent opinions of languages in which I have coded.

This list served as an interlude to a presentation I gave recently.

• SQL – Most boring / useful
• PL/pgSQL – wtf is this? I have to write database functions in this?
• Bash – Useful and fast. Nobody knows how to write in this.
• C – God. Dangerous. Caused heartbleed bug. Bad language! ::Language runs off::
• Matlab – haha
• Perl – Madness. Fast.
• Ruby – For hipsters / designers. Slow but sexy.
• Mathematica – Designed to clash with every other language’s syntax
• Java – enterpriseCodeThatMakesYouWishYouWereDead (deprecated)
• Javascript – Great if used properly. Not used properly.
• PHP – [censored]
• Julia – Smart, Sexy, Fast. Innate parallelism.
• Scala – So many features / idioms it pretty much guarantees a month of  12 hour days before you can read more than 50 lines in a row.
• R – Makes \$. Errors and warnings written by devious children.

# The Lenovo W530 with Optimus Technology and Linux

Recently my 2008 Mabook Pro died.  Although I ended up fixing it as documented in this HOWTO I had been searching for a new laptop anyway and this was just the catalyst I needed to make a move.  After some searching I came across the Lenovo W line.  The machines appeared to be built tough, pack plenty of power, just light enough to carry around on occasion and support Linux fairly well.  I settled on the W530 with mostly stock specs and an upgraded full HD screen.

Out of the box the machine runs really well.  I’ve played with Arch, Archbang, and Ubuntu and everything is (of course) quite snappy.  The only real issue with this machine is its graphics card, which runs Optimus technology; a poorly named feature that means: “optimal use of graphics card considering battery life”.  Essentially software will decide when to turn on the power hungry NVIDIA discrete graphics card.  I spent many hours trying to figure out how best to setup Linux to use the graphics card in this machine.  Hopefully my thoughts will save you some time or aid in your decision to purchase or not purchase this machine.

On the W530, you may select whether you wish to use the discrete, integrated, or optimus graphics in the BIOS.  This is a great feature of this machine, and although you might expect that its availability is ubiquitous among laptops, some of the forum postings I have read lead me to believe that this is not the case.  Anyway on the W530 we can avoid configuring and installing anything related to Optimus simply by selecting either the NVIDIA “discrete” graphics card or the Intel “integrated” graphics.

If Optimus technology is desired, there is an open source project called Bumblebee that will allow you to start applications so that they use the discrete graphics card (in this case you would select Optimus in the BIOS).  Installation instructions are available for most major Linux distributions.  On Ubuntu I was easily able to start Minecraft in this manner.

Now for the quirks:

1.  The Nouveau open source graphics card driver does not offer OpenCL support (and will fall back to software rendering) for the NVIDIA series code named “Kepler” which includes the K1000M and K2000M, one of which is included in the W530.  See the Feature Matrix.

2.  The NVIDIA proprietary drivers work quite well (and include OpenCL support) unless you are running Kernel 3.10.  This is not an issue for many distributions but is causing a serious headache for Arch Linux and other users on bleeding edge Linux distributions.  See the Arch Linux forum post and the NVIDIA forum post.  NVIDIA claims this issue will be resolved on the next driver release.

3.  The VGA output is wired into the discrete graphics card, which means you must be running this card to use multiple monitors.

The last quirk I never got to the bottom of.  I observed that when I ran the graphics in Optimus mode under Ubuntu I *could* use an external monitor, but the screen settings were hard to nail down and the cursor left a trail behind it.  In any case it felt clumsy so I didn’t investigate further.

Given these quirks, what is the result?  For my use case, I will never need to use an external monitor without a power source, so selecting discrete graphics at start up is fine.  When I am out I can use Bumblebee, although I have not found a real need as I rarely employ graphics intensive applications.  I use Ubuntu and Arch, and for now will be booting Arch with the integrated graphics.  Sooner or later either NVIDIA will fix the issue or Nouveau will support OpenCL.

All in all this is an amazing machine.  I am most impressed by the build, as nice specs are not hard to come by.  Its screen is beautiful, Its keyboard has a great feel and has 3 back-light settings, and the laptop as a whole is highly upgradeable.  If you can deal with a few graphics card quirks this is a stellar Linux laptop.

# Bake your Macbook Pro Back to Life

A little over a month ago I put my Spring 2008 Macbook Pro to sleep and it never woke up.  For anyone that works with computers for a living this is quite devastating.  This standard level of devastation was amplified by the loss of my Saturday afternoon habitat of streaming tennis matches on the Macbook.  About 4 hours later my girlfriend broke up with me over text message, which really threw salt in the wound.  Tough day.

I did some troubleshooting and quickly realized the logic board was toast.  The tell tale sign here is that if you remove the RAM, the firmware will beep at you on start up.  No beeps, no firmware, your logic board is in trouble.  Note this is not the first time my Macbook has had issues.  Check out this trackpad failure post which includes *more ranting*.

Relationships can be fixed and so can your Macbook.  There are a few things that may have happened to your board, most of which involve solder cracking due to high temperatures.  If you believe this to be the case and you have a Macbook Pro from the Spring 2008 era, you might try bringing your board to an even *higher* temperature to re-solder everything back into place.

Here’s HOWTO:

1.  Remove the logic board from your Macbook Pro.  The instructions vary by model and can be found on ifixit.  Make sure to peel off any stickers, those little plastic screw guides, the bumpers on the ports, and clean the thermal paste off of the chips.

NOTE:  I tend to use whatever I can to get a job done.  In this case that meant using incorrectly sized screwdrivers.  This is one situation where being a hack caused me some real trouble, and I highly recommend you buy exactly the sizes you need.  Ifixit lists the tools you require and these can probably be obtained at your local Home Depot.

2.  Inspect your oven for cakes, pies, and roasts.  Remove these.

3.  Mount your logic board on some aluminum foil elevated above a baking sheet to avoid direct contact.  I made a few half inch balls of foil, placed them on the baking sheet, and then put a sheet of foil on top.  This ensures the logic board does not touch the (soon to be) very hot baking sheet.  Also consider making a little cup of foil and dropping some solder in.  This will act as your “canary”.

4.  Preheat your oven to 375 degrees F.

NOTE:  My oven is a very non-digital natural gas based device, so your crappy oven will probably work too.

5.  Set a timer for 7 minutes and 30 seconds.  Place the logic board on the middle rack and start the timer.

6.  When time is up remove the logic board.  If the solder in the cup has melted, you’re probably good to go.  If the board is on fire you can skip to step 12.

7.  Let the board cool off for 10 minutes.  Have a beer.

8.  Put your Macbook back together, making sure not to forget the thermal paste.

9.  Take your Macbook back apart and put the little plastic screw guides that you forgot back on the logic board.

10.  Put the Macbook back together.  Really you can leave the topcase off with just the ribbon cable connected if you like.  Probably not a bad time to ensure the fans still work.

11.  Press power.  Hopefully everything will start up!

12.  Begin researching new laptops as this fix has been reported to only last ~4 months and Apple isn’t cool anymore anyway.  I recommend the Lenovo W530 with Arch Linux.

# Quadcopters and Spatially-Centric Data

A few months ago I came across my new favorite toy, the Crazyflie nano quadcopter.  Developed by Bitcraze, the Crazyflie is an open source firmware and hardware flying development board.  With a relatively beefy STM32 ARM Cortext-M3 MCU and an expansion header the Crazyflie is an ideal candidate for upgrades and modifications.  With such expandability, spare CPU cycles and RAM, it should be possible to interface the Crazyflie with the sensors necessary to facilitate autonomous flight and abiotic variable detection.  Given the extremely flexible mobility of the Crazyflie, these variables can be detected nearly anywhere in space.

The Crazyflie is an ideal candidate for unplanned, exploratory flight paths.  Imagine a little quadcopter with a bounded area to explore in the X, Y, Z axis.  The purpose is to explore the matrix in the most efficient manner possible, while altering the flight path real-time given physical obstacles.  If a quadcopter can explore an area in this manner efficiently with a few sensors in tow it is possible to develop a spatially-centric data set; that is a data set with very high spatial resolution and moderate  temporal resolution.

Why is this useful?  Traditionally data has been fetched at high frequencies in static locations.  Areas between those locations are given interpolated values.  Often these values are good enough, but in complex environments key data points are often absent and thus the interpolated values are not a good representation of the area in question.  For example in the Appalachian mountains (where I live), temperature, humidity, light levels, and other abiotic variables can change drastically in a matter of feet.  Each of these little areas are called microclimates and foster very specific plants, animals, and fungi.  Accurate habitat prediction can be quite difficult with low spatial resolutions.

A more familiar example is cold air detection in an old house during winter.  While your upstairs and downstairs thermometers are reading the average temperatures in their respective locations, cracks and holes near windows and doors allow much cooler air to enter the house.  With only 2 static sensors it is not possible to pinpoint these areas.  Interpolating values around the sensors is of little help.  However, with a spatially-centric data set obtained by a quadcopter, areas of cold air can easily be identified.

Several technical challenges need to be overcome to facilitate the autonomous exploration of space.  The Crazyflie kit I ordered has a few extra sensors including a magnetometer (compass) and altimeter (altitude) and can be interfaced with a GPS unit.  These sensors can provide a basic sense of space, so let’s assume we can determine the Crazyflie’s location given a point in time.  Let’s also assume we can programmatically control the Crazyflie well enough to move to a desired location at some resolution X. Our last challenge is to keep the Crazyflie from bumping into things.  To solve this problem, we will mimic a bat and use an ultrasonic proximity sensor for object detection.

The focus of this article is on selecting a proximity sensor, setting up a Crazyflie development and debugging environment, and learning how to program MCUs in general.  There is also a very concise HOWTO on interfacing a proximity sensor with the Crazyflie that omits my opinions and tips for learning how to program MCUs.  Also be aware that while in this article I do include some very specific tips that I found useful in this project, I have assumed a general level of familiarity with Linux, compiling from source, checking out code, etc. and I do not include help that can easily be found elsewhere.

## C, Vim, Cscope, and the ARM Development Environment

I’ve never professionally programmed in C, so it was necessary to spend some time reviewing the language (funny though that it was the first language I learned back in middle school).  “The C Programming Language” by Brian W. Kernighan and Dennis M. Ritchie is excellent.  I’ve always found it difficult to find programming books that fit somewhere between “Learn X in N days” and the spec.  I guess that’s what reference books are for, but this felt better than most.  If you are an experienced programmer and need a great course in C, this is your book.  If you are not, try the tutorial in the beginning.  If it seems overwhelming, start with an introductory book.  Otherwise, work through the exercises for a few weeks and you’ll be well on your way.

To review the firmware, I chose to keep things simple and run Cscope on top of Vim (check out the tutorial).  Building and installing Cscope from source on OS X was easy; on this platform Vim already has Cscope support compiled in.  To generate the Cscope database, navigate to your project’s root directory and recursively search for source files and build a Cscope database (this assumes you have checked out the crazyflie firmware in your home directory):

`cd ~/crazyflie-firmware`
`cscope -Rb`

I prefer to load the Cscope database by hand once inside of Vim. If we are to begin with main.c in our research, we must specify the location of the Cscope database and the relative path from which files will be located:

`cd init`
`vim main.c`
`:cs add ../cscope.out ~/crazyflie-firmware`

Exploring the code was easy using Cscope and I found :split quite useful for header files.  After poking around for a while, I discovered adc.c and adc.h where the analog to digital conversions takes place and where I must make my edits.

In order to build the crazyflie-firmware it was necessary to grab the GNU Tools for ARM Embedded Processors.  Installation was pretty self explanatory.  I added the bin folder to my path and did a test run of make with the Crazyflie firmware.  Check out the Crazyflie wiki here for details on building the project and make goals.

## Picking the Right Sensor

While reading through the firmware, I was also searching around the internet for an ultrasonic sensor suitable for the Crazyflie.  My requirements were that the sensor have a simple analog output, not weigh more than 5 grams, and take no more than 2.8 volts.  The LV-MaxSonar-EZ0 fit these requirements nicely.

It’s worth mentioning that MaxBotix puts out a wide array of ultrasonic sensors, including one that it specifically recommends for quadcopters (check out their article on quadcopters here).  However, the high performance sensors are a little bit heavier than the Crazyflie’s 5 gram limit and in addition required 3.3 volts.  If you can solve the weight problem, the voltage problem can be dealt with using a step-up voltage regulator.

When the sensor arrived I hooked up its ground and +5 V pins to pins 19 and 20 on the Crazyflie’s expansion header respectively.  I intercepted the signal via a breadboard with my multimeter and observed changing millivolt values as I moved my hand above the sensor face.  This particular sensor operates at a 1 inch resolution, and is capable of sensing objects from 0″ to 254″.  Objects closer than 6″ will read 6″.  To scale the mV output the equation (VCC/512) is to be applied.  In my case, this is 2.8/512 or ~5.5 mV per inch.  Given that the Crazyflie’s VCC seemed relatively stable, I felt I had a pretty good scaling factor and accurate sensor ready for flight.

457 mV translates to ~83 inches, the distance from my desk to the ceiling.

## FreeRTOS, and MCU Programming

FreeRTOS is a very simple task prioritization system on top of which the Crazyflie firmware is written.  The idea is quite simple: given some tasks that need to run in near parallel on a single core, switch back and fourth between them to simulate concurrency.   In the case of the Crazyflie, this includes power management, stabilization, radio communication, etc.  Tasks are stubbed out in an infinite loop and the relevant context (memory) is loaded when they are activated.  For my purposes, piggy backing on the adcTask (in adc.c) would be fine.

With my development environment set up and a general understanding of where the voltage values of my sensor would be read in code, it was time to dive into MCU programming.  This quickly turned into a major research task as it turns out MCUs employ all sorts of low level systems I had never programmed before.  Further, there was really no gentle introduction to MCU programming that wasn’t specific to a particular PCB.  The gap between the reference manual and the books I found was quite large.  This is the nature of this type of development and in an some ways what makes it fun.  The Crazyflie is its own beast.

By far the most valuable resource I found was the example code on ST’s website in the STM32F103 Standard Peripheral Library.  It’s worth mentioning that the STM32F103 website is extremely useful in general and has lots of documentation, sample code, stacks, etc.  After looking through the Analog to Digital Converter (ADC) examples, I had a much better understanding of what I needed to initialize in order to start reading values from the proximity sensor.  By reading the example code in conjunction with the reference manual, I was able to get my bearings.  I moved back to the Crazyflie code and began dissecting the implementation of the ADC piece by piece.  I quickly gained a grasp of how the ADC employed the Direct Memory Access (DMA), timers, and interrupts to convert raw voltage into meaningful values.

The high level breakdown of the Crazyflie ADC is as follows:

1. Timer 1 kicks off the ADC 1, ADC2 follows by default
2. ADC 1 fetches the reference voltage and ADC 2 fetches the battery voltage simultaneously
3. The values are moved from the ADC by the DMA to SRAM and an interrupt is generated
4. FreeRTOS adds the values to a Queue
5. Periodically the adcTask (scheduled by FreeRTOS) runs
6. Values are decimated (this is essentially averaging oversampled values to gain higher resolution; see this white paper)
7. The battery values are cleaned and updated

In addition to the example code, a nice high level overview of MCU programming that is ARM specific is “Fast and Effective Embedded Systems Design” by Rob Toulson and Tim Wilmshurst.  Although the target board is the mbed (which offers some nice layers of abstraction not present on the Crazyflie), the high level concepts carry over.  I enjoyed reading the section about the ADC.

## Coding and Debugging

Having completed the research phase, it was time to start writing and debugging code.  A bit of searching led me to a fantastic JTAG debugger, the Bus Blaster V3.  To drive the Bus Blaster, I needed to install openOCD.  I ended up having some dependency issues with libusb on OS X that I was not able to resolve simply.  I decided to upgrade my old copy of Macports to expedite the process.  After cleaning out my local repository packages, updating the Macports repository links, and other housecleaning I was able to get openOCD installed.

I decided that I would keep my toolchain simple and debug using GDB.  GDB is extremely well documented, so I won’t go into detail about how to use it.  However there are a few things that have made my life easier:

• Make sure to connect the Bus Blaster to the computer before powering up the Crazyflie
• ‘monitor reset’ will restart the Crazyflie from within GDB (not a terrible idea before debugging)
• CTRL-C will halt the Crazyflie firmware.  Sometimes this crashes GDB.  Just kill the process; reset everything and start over

Connecting to the Crazyflie is just a matter of making the openOCD target in the crazyflie-firmware project to get the Bus Blaster to connect:

`make openocd OPENOCD_INTERFACE=interface/busblaster.cfg`

Then, connect to the CrazyFlie via gdb and point it to the firmware symbols.

`arm-none-eabi-gdb -ex "target remote localhost:3333" cflie.elf`

Debugging the Crazyflie with the Bus Blaster V3

With GDB properly set up integrating the proximity sensor with the Crazyflie was a pleasure.  I learned a few things about pointers and structures I didn’t know (check out adc.c#adcDecimate for some fun) and gained a working understanding of the ADC code structure.  You can find the final diff here.

## The Results

My Crazyflie with its “Bat Eye”

After the research, coding, and debugging was complete, I ended up with this slightly bug like quadcopter capable of detecting objects around it.  Originally I hadn’t planned on mounting the sensor for this initial development phase.  However, a few days after I completed the code I lay awake in bed and decided to give it a shot.  It turned out to be the easiest part of the entire process.

The marriage between the proximity sensor and the Crazyflie is not yet perfect.  Most notably, the battery life has been diminished quite a bit.  After a few minutes of hovering the Crazyflie begins to have difficulty getting off the ground, sometimes only reaching 4 or 5 feet in height before gradually drifting downwards.  The sensor readings are fairly stable.  There’s some optimizations that can be done in terms of oversampling and speed of readings, but some of the spikes in the data are the limitations of the sensor itself.

Weight concerns and optimizations aside, it’s pretty cool flying the Crazyflie around and watching the graph of proximity readings.  When I set out to interface the Crazyflie with a proximity sensor, my purpose was to add a sensor to the copter that would eventually allow it to avoid collisions.  I believe this research and development work has reached that end.

Good luck, have fun!

# Interfacing the Crazyflie With a Proximity Sensor

This article will teach you how to interface your Crazyflie with a proximity sensor.  It would be wise to test your Crazyflie and the proximity sensor before soldering everything together.  A detailed account of my experience can be found here.

## Bill of Materials

1. Crazyflie nano quadcopter (you can also use the 6-DOF version)
2. LV-MaxSonar-EZ0 ultrasonic proximity sensor
3. Solid wire capable of supporting a 5 gram sensor
4. Soldering equipment

## Methods

1.  Solder the proximity sensor pins  ->  to the Crazyflie expansion header (check out the reference):

```+5  ->  pin 20 GND  -> pin 19 AN ->  pin 14```

2.  Position the wire so the proximity sensor stands straight up, and the eye points towards the front of the copter as shown in the photo.

OR

Clone my fork of the crazyflie-firmware and make the project if you have your development environment setup:

`hg clone https://cfusting@bitbucket.org/cfusting/crazyflie-firmware-proximity-sensor`

4.  Flash the Crazyflie firmware over the radio.  Instructions can be found here.

5.  Add the vProx logging parameter to your selecting logging parameters and restart the Crazyfly Client

6.  Fly around and watch as the Crazyflie detects objects in the Plotter tab!

# A better way (package) to link R and PostgreSQL

Recently I was loading a large (~420mb) CSV file for Kaggle’s Adzuna job salary competition into R and ran into some speed problems.  Specifically R was crunching endlessly and my Macbook pro turned into a paper weight.  It was probably naive of me to attempt loading a CSV of such size into R, but I assumed some well written functions in C would handle this quickly and not block the rest of my processes (actually it didn’t block them but it may as well have).  Anyway for the most part I load data into R via ODBC so I figured I’d throw the data into a local PostgreSQL database and get on with my data munging.

However, OS X didn’t want to play ball.  Apparently, some big cats ago, Apple decided ODBC wasn’t super important (?!) and decided to remove it from the stock install (I recently upgraded to Mountain Lion so my mac would run slower and sometimes fall into an infinite loop during startup).  I searched around a bit and found the usual ODBC suspects that I could install on OS X but quickly recalled the small pains I dealt with doing the same thing with my Ubuntu machine at work.  Anyway I played around with ODBC for a bit and wasn’t really getting the optimal configuration I wanted so I looked a little further and found RPostgreSQL.

Now, having used RODBC over the years I don’t have many complaints except that if you don’t already have a stock ODBC install setting everything up can take time from your cause (fun data analysis in this case) that you generally don’t really have to spare.  What would be better is a package that’s wicked fast and a configuration that’s handled during package install.  Check out the CRAN entry.

After installation I loaded the entire CSV into R in about 3 seconds:

``` drv <- dbDriver("PostgreSQL") con <- dbConnect(drv, db="postgres", user="postgres"); rs <- dbSendQuery(con, statement = "select * from rev1"); df <- fetch(rs, n = -1); ```

Cheers!

_Chris