Suppose you’re building a widget that performs some simple action, which ends in either success or failure. You decide it needs to succeed 75% of the time before you’re willing to release it. You run ten tests, and see that it succeeds exactly 8 times. So you ask yourself, is that really good enough? Do you believe the test results? If you ran the test one more time, and it failed, you would have only an 72.7% success rate, after all.
So when do you have enough data, and how do you make the decision that your success rate is ‘good enough?’ In this post, we’ll look at how the Beta distribution helps us answer this question. First, we’ll get some intuition for the Beta distribution, and then discuss why it’s the right distribution for the problem.
The Basic Problem
Consider the widget’s tests as independent boolean variables, governed by some hidden parameter μ, so that the test succeeds with probability μ. Our job, then, is to estimate this parameter: We want a model for P(μ=x | s, f ), the probability distribution of μ, conditioned on our observations of success and failure. This is a continuous probability distribution, with μ a number between zero and one. (This general setup, by the by, is called ‘parameter estimation‘ in the stats literature, as we’re trying to estimate the parameters of a well-known distribution.)
Beta distribution for 8 successes and 2 failures. The blue curve is the probability density function P(x=μ|s, f). The expected value for μ is 0.8 (marked in black). The green line indicates 90% certainty that mu is greater than 0.633. The red curve is the cumulative density function, which is useful for finding confidence bounds.
I’ve been playing around with Cities: Skylines recently, the super-popular SimCity knock-off. Dealing with traffic is a core theme of the game (as it should be). Traffic tends to accumulate at intersections, and it’s well known that one-way streets have higher traffic flow. The logical conclusion, then, is to try to build a city with a single extremely long one-way street… Unfortunately we have to compromise on this perfect vision, because people want to get back home after work and so on.
Hilbertville: The space-filling city.
A Quick Intro to Space Filling Curves
Meanwhile, a space-filling curve is an mathematical invention of the 19th century, and one of the earlier examples of a fractal. The basic idea is to define a path that passes through every point of a square, while also being continuous. This is accomplished by defining a sequence of increasingly twisty paths (H1, H2, H3, …) in such a way that H∞ is well-defined and continuous. Of course, we don’t want a infinitely twisty road, but the model of the space filling curve will still be useful to us.
There are a few important ideas in the space filling curve. The first is a notion that by getting certain properties right in the sequence of curves H1, H2, H3, …, we’ll be able to carry those properties on to the limit curve H∞.
The Moore curve is an example of a (continuous!) space-filling curve. The color changes keep track of time as you move along the path; notice that in the very twisty sixth path, a small change in time still keeps you in the same (blocky) neighborhood.
The second main idea is how to get continuity. Thinking of the curve as a function where you’re at the start at time 0 , and you always get to the end at time 1, we want an H∞ where small changes in time produce small changes in position. The tricky part here is that the path itself gets longer and longer as we try to fill the square, potentially making continuity hard to satisfy… When the length of the path doubles, you’re moving twice as fast.
In fact, because of continuity, you can also “go backwards:” Given a point in the square, you can approximate what time you would have passed through the point on the limit curve H∞, with arbitrary precision. This gives direct proof that the curve actually covers the whole square.
Here’s an example of a space filling curve which is not continuous. Define Bk as the curve you get from following these instructions:
Start in the lower-left corner.
Go to the top of the square, and then move right by 1/k.
Move to the bottom of the square, and move right by 1/k.
Repeat steps 2 and 3 until you get to the right side of the square.
The problem here is that a very small change in time might take us all the way from the top of the square to the bottom of the square. We need to be twistier to make sure that we don’t jump around in the square. The Moore curve, illustrated above, does his nicely: small changes in time (color) don’t move you from one side of the square to the other.
Actual Simulated Cities
What happens if we try to use space filling curves to build a city in Cities: Skylines?
My first attempt at building ‘Hilbertville’ was to make large blocks, with a single, winding one-way road for access, using the design of a (second-order) Hilbert Curve. In addition to the roads, though, I placed a number of pedestrian walkways, which allow people on foot to get in and out of these neighborhoods directly. I like to think that this strongly encourages pedestrian transit, though it’s hard to tell what people’s actual overall commuting choices are from the in-game statistics.
Hilbertville, two blocks. The lower view highlights where the roads are, and are color-coded for the amount of congestion along each segment of roadway. There’s a bit of congestion at the output of each block, as cars wait at the intersections.
Skylines only allows building directly facing a road; corners tend to lead to empty space. You can see a large empty square in the middle of the two blocks pictured above. There are also two smaller rectangles and two small empty squares inside of each of these two blocks. Making the top ‘loop’ a little bit longer removed most of the internal empty space. This internal space is bad from the game perspective; ideally we would still be able to put a park in the empty spaces to allow people to extra space, but even parks require road access.
Intersections with the main connecting roads end up as ‘sinks’ for all of the traffic congestion. So we should try to reduce the number of such intersections… The Moore curve is a slight variation on the Hilbert curve which puts the ‘start’ and ‘finish’ of the path next to one another. If we merge the start and finish into a wide two-way road, we get this:
A space-filling road based on the Moore curve.
We still get the wasted square between neighborhoods, but somewhat reduce the amount of empty interior space. Potentially, we could develop a slightly different pattern and alternate between blocks to eliminate the lost space between blocks. Also, because the entrance and exit to the block coincide, we get to halve the number of intersections with the main road, which is a big win for traffic congestion.
Here’s a view of the full city; it’s still not super big, with a population of about 25k. We still get pretty heavy congestion on the main ring road, though the congestion is much less bad than in some earlier cities I built. In particular, the industrial areas (with lots of truck traffic) do much better with these long and twisty one-way streets.
Full view of Hilbertville, population 25k. There are fourteen blocks here; note the two Moore curve blocks at the bottom, and the slightly modified Hilbert curve block in the lower left, which reduces empty space at the expense of a slightly longer road.
The empty space is actually caused by all of the turns in the road; fewer corners implies fewer wasted patches of land. The easiest way to deal with this is to just use a ‘back-and-forth’ one-way road, without all of the fancy twists.
The other major issue with this style of road design is access to services. Fire trucks in particular have a long way to go to get to the end of a block; the ‘fire danger’ indicators seem to think this is a bad idea. I’m not sure if it’s actually a problem, though, as the amount of traffic within a block is next to none, allowing pretty quick emergency response in spite of the distance.
Overall, I would say it’s a mixed success. There’s not a strong reason to favor the twisty space-filling curves over simpler back-and-forth one-way streets, and in either case the access for fire and trash trucks seems to be an issue. The twistiness of the space-filling curve is mainly used for getting the right amount of locality to ensure continuity in the limit curve; this doesn’t serve a clear purpose in the design of cities, though, and the many turns end up creating difficult-to-access corner spaces. On the bright side, though, traffic is reduced and pedestrian transit is strongly encouraged by the design of the city.
My laptop, android phone, and a Raspberry Pi plugged into a crappy hotel TV, all running terminals. This happened while trying to compile Sage on the Pi in January, 2012.
One of the graduate students asked me about how one goes about learning the Linux command line, so I thought I would write down a few of the things I think are most useful on a day-to-day basis. Such a list is sure to stir controversy, so feel free to comment if you see a grievous omission. In fact, I learned the command line mainly through installing Gentoo Linux back before there was any automation whatsoever in the process, and suffering through lengthy forum posts getting every bit of my system more-or-less working. (Note: Starting with Gentoo is probably a bad idea. I chose it at the time because it had the best forums, but there are probably better places to start these days. I mainly use Xubuntu these days.)
So, off to the races. I’m going to skip the really, really basic ones, like ls, cd, apt-get and sudo. In fact, there’s a nice tutorial at LinuxCommand.org which covers a lot of the basics, including IO redirection. Finally, I’m assuming that one is using the bash terminal.
I attended a really nice talk by Arash Amini yesterday about detecting ‘communities’ in sparse graphs. The basic problem is: In a big graph (like the Facebook graph, or the graph of scientific papers citations) you have clusters of friends/associates, and you want to pick out those clusters. Dr. Amini and his collaborators have been working on methods to solve this problem in particularly noisy cases. The methods presented were developed for cases where you know the specific number of clusters you are seeking to find. It was a fascinating talk, and I came away wondering if there are good methods to use when you aren’t sure of how many clusters there are.
At the left is a randomly generated block-diagonal adjacency matrix (using a stochiastic block model). The center is the same matrix with the rows randomly shuffled; you can’t “see” that it has block diagonal structure. The right is the matrix with blocks recovered using the techniques outlined in this post. Note the noise in the lower-right corner; these correspond to individual, isolated vertices that ended up in their own clusters.
I’m teaching an intro calculus class this year (specifically, ‘Math for Life and Social Science’), and came a while ago to the section on optimization. It’s a really important subject, and yet the optimization problems one finds in Calculus books (even good ones) tend to be contrived examples which I refer to as ‘box factory problems.’ Things along the lines of ‘minimize the surface area of a rectangular box with volume ‘.
Hey, kids! Let’s take a field trip to the box factory!
These are fine for a problem or two: There’s a useful skill in taking a real-sounding problem and translating it into the mathematics you’re learning. We use the constraints (in this case, on the volume) to reduce the number of dimensions, turn the problem into a one-variable calculus problem, and then solve. All well and good, but these problems somehow completely miss the impact of optimization on society at large. Largely because the optimization problems that occur most commonly in the wild have a slightly different flavour.
Problem: In Boston, we observe that the monthly rent for three one-bedroom apartments are $1300, $1150, and $950. Rent on three two-bedroom apartments were $1500, $1700, and $1200. Assuming that the cost of a 0-bedroom apartment is $500, find the best possible line describing the rent as a function of the number of bedrooms. Continue reading →
3rd Maseno Maths Camp group photo (silly version).
The third annual Maseno math camp ran in the third week of August; it’s a bit hard to believe that we’re up to three already!
The week started with a great talk from Rejoyce Gavhi, a South African mathematician who just finished a postdoc in Canada, and who is now starting a new job with AIMS:Sec. She talked about the challenges she overcame in pursuing mathematics as a woman from Africa, and was quite inspirational for everyone involved.
As usual, we divided this year’s camp up into five ‘themes.’ The themes this year were programming, modelling, geometry, combinatorics, and code-breaking. I mainly helped put together the combinatorics section with Ingrid Mostert (from AIMS:Sec) and Santiago Borio, a Geogebra virtuoso who teaches school in London; the sessions were about the bijection between subsets and lattice paths, and seeing the binomial coefficients from different perspectives. Chris Clarke put together some great sessions in the modelling section (for example, using massively multi-player dice-games to model the spread of a disease in a population). The programming section focused on building flow charts to describe algorithms, which was a pretty different tack than we’d previously considered, and I think a good one. I never really think of flow charts when I program, but breaking a process down into some ‘decision points’ and considering all possible outcomes is quite useful as a programmer. Approaching the process via flow charts is a great way to organize that process in a visual way.
Balázs Szendrői works with participants at the Mombasa algebraic geometry workshop.
This week I’ve been giving lectures at an algebraic geometry workshop in Mombasa. I know what some of you are thinking: ‘But Tom, you’re nothing like an algebraic geometer!’ And that’s true. But often the best way to learn something is by putting yourself in a position where you have to know it, like standing in front of fifty people expecting a clear explanation. In this case, I’ve learned some basics of Grobner bases (mostly from an excellent book by Cox, Little, and Shea) and have been augmenting the lectures and exercise sessions with Sage. I’ve written up some notes on the talks, and I’ll probably convert them into a web-based format with Sage cells and stuff sometime next week…
The workshop has participants attending from Kenya, Tanzania, Uganda, Rwanda, and Zambia. The participants have been super motivated; we’re just finishing up the third and final week of the workshop, and the participants have been staying up late working on final projects. Attendance has stayed high throughout the workshop, to a degree you wouldn’t expect in (say) North America. The chance for exposure to math going on at the international level is a big draw, since it’s still so rare for international mathematicians to come through East Africa. I imagine it’s like if you only got to eat ice cream once every year or three: you’re not going to let anything go to waste.
Group shot from the Bahir Dar math camp. The waterfall in the background is one of the major sources of the Nile!
I’ve spent this last week helping with the first-ever Ethiopian math camp, hosted by the math department at Bahir Dar university. As with the Maseno math camp, we focused on giving activity-based sessions, teaching interesting math topics outside of the standard curriculum. The intention is to boost student interest in maths and to expose some teachers to different ways of thinking about mathematics. The big difference between the Maseno and BDU camps is that the students in Ethiopia are mainly Amharic speakers, with maybe a couple years of learning English under their belt. This makes it essential to build up and utilize the local staff to a degree that we aren’t forced to in Maseno. Luckily, the local staff is bright, imaginative, and ready to try new things. On the whole, it was a fantastic first attempt.
We gave thirty-ish sessions, divided into five topic areas: geometry, scientific research, card tricks, history of numbers, and ‘rules.’ I was a few days late arriving at the planning week, due to some medical exams I needed to get done in Addis, and so was mainly designing the card trick sessions. I also did a lot with the geometry group and gave a session each on cryptography and complex numbers.
Passwords being cracked by some really simple python code I wrote. Who knew ‘Tigger’ was such a common root word for passwords?
(These are notes adapted from a presentation I gave at the LakeHub workshop this week. They owe a lot of debt to this article, which inspired the talk. If you already know that you should just use bcrypt or something similar, and why, you can just skip to the ‘conclusions’ section.)
So let’s suppose you’ve just made a hot new website from which you’ll make a million dollars a year. You get to the point of creating a database for all of your users who will be logging in and doing things like buying airplanes, so you put together a database table. Maybe it looks something like this:
Name
Email
Password
Bill Gates
bill@microsoft.com
passw0rd
A few weeks after launch, you have two million users, and someone breaks into your server and steals the database. Of course, they don’t tell you that they did this; they’re much happier to keep the database, pull out a name and password, log in as someone else, and use your site to steal lots of money and undermine the basic building blocks of democracy and common decency. After sending apologies to the userbase, you decide that your database structure was flawed.
Ligretto is an awesome fast-paced game of breaking glass. (That one in the upper-left corder exploded about ten seconds after this picture was taken.)
LakeHub has been churning steadily along; we had our third event on Saturday, and it was quite successful according to me and everyone else I’ve talked to. We’ve settled on a basic format for the time being, with an event happening every Saturday from 1-5pm. Half of the time these are big group-oriented events with demos and big inclusive activities, and the other half of the time they’re ‘hang-outs’ where people get together to work with other tech-oriented people nearby, and to check in with ongoing study groups.
There are three study groups started already: one on microcontroller programming, hosted by Peter Mbari of Access Energy, one on javascript and web development hosted by Simeon Obwogo from IPA and James Odede of the Maseno ICT Guild, and finally a group doing game design, run by yours truly. We wanted a less-technical group to complement the other two programming-heavy study groups; luckily I know some things about games, and game design is actually really useful in thinking about business and web technologies. Especially with ‘gamification’ as a big buzz word. So this week I’ll talk a bit about games, to get my mind going on the subject!
‘.
Inventing Situations. 