“All models are wrong, but some are useful.”  George E. P. Box

Last week I saw a clever short video titled, “Why the other line is likely to move faster.”  It explains, among other things, why it often seems that no matter what checkout line you choose while doing your holiday shopping, you notice that another line is moving faster than yours.  The video generated some interesting discussion, at least on Reddit and Slashdot where I bothered to look.

(Unfortunately, the title of the related Slashdot submission was, “Scientifically, You Are Likely In the Slowest Line.”  This is not just misleading, it is simply false.  As several commenters point out, the argument presented in the video is the weaker statement that “you are likely not in the fastest line.”)

The focus of this post, however, is on another observation in the video, and the corresponding online discussion.  In the first part of the video, the Engineer Guy notes that there are (at least) two approaches to serving customers with multiple servers.  The first approach, common in grocery stores, is to have a separate line, or queue, of customers for each server.  The second approach, used at airport ticket counters, banks, etc., is to have a single queue of customers, with the person at the front of the queue waiting for the next available server.

The interesting observation made in the video is that the latter approach is much more efficient than the former: “… for 3 cashiers, it’s about 3 times faster than having a single line for each cashier.”  From some of the comments, this seems to be “common knowledge” from queuing theory, and businesses that still have separate lines should apparently open an operations research textbook and get with the times.

I am not so sure.  I am not an expert in queuing theory; even my last stochastic processes course was 12 years ago.  So as an exercise, I wrote a series of simple discrete event simulations of this process to see what happens.  For a specific example, let us assume that there are three cashiers as in the video.  Customers arrive with exponentially distributed inter-arrival times at the average rate of one every two minutes.  Each cashier serves a customer in an average time of five minutes, also exponentially distributed.  In each of the two queuing approaches described above, what is the average time that a customer must wait in line?  (This is the same setup used for a puzzle found here.)

Before getting to the simulation results, we can compute analytically what the average waiting times should be in both cases.  (Actually, this is in part why we assume that arrival and service times are exponentially distributed, so that the problem is analytically tractable.)  First, with three separate queues, the average waiting time is:

where (cashiers), (customers arriving per minute), and (customers served per minute by each cashier).

With a single queue feeding all three cashiers, the average waiting time is:

This all matches up reasonably well with the threefold improvement mentioned in the video.  And when I ran the simulation of the single queue case, I also saw an average waiting time of about 7.12 minutes.  Everything makes sense so far.

However, when I ran the simulation with three separate queues, the average waiting time was only 7.77 minutes, nowhere near the predicted 25 minutes.  What was going on?

It turned out that my simulation attributed more intelligence to the customers than is assumed in the above analysis.  In my first draft of the multi-queue simulation, as each customer arrived ready to checkout, he entered the queue that currently had the fewest number of customers.  In this case, the resulting behavior is not significantly worse than the single queue approach, in neither mean nor variance.  When I modified the simulation so that each customer entered a randomly selected queue, the average waiting time jumped to 24.49 minutes as originally expected. (Edit 2020-12-31: Python code for these two simulation variants is available on GitHub.)

Who does this?  Who approaches the front of the store with a full cart and just rolls a die to determine which line to enter?  Of course, queue length is not the only factor to consider: customers also gain some information about potential waiting times by observing the number of items in others’ carts, there are express lanes with different distributions of service times, etc.  Adding any of these factors to the model makes analysis more difficult, usually prohibiting closed form solutions like those above.  (For example, I suspect, but am not sure, that even my original “enter the shortest queue” process does not have a clean analytical solution.)

I think the point here is that the grocery stores and other businesses with multiple queues are not necessarily missing out on a better approach.  The mathematical models that admit clean solutions are only useful to the extent that they capture the relevant characteristics of the system being modeled.  A model stops being useful when it fails to capture even modest intelligence of customers; or the space and logistics required for one long, possibly serpentine line of grocery carts; or the psychological effects of customers seeing exactly the same number of people, not in several smaller lines, but one long line, etc.

Finally, some mathematical musings: first, as mentioned above, is there a simple analytical expression for the average waiting time of the “shortest queue” process above?  I suspect there is not.  Also, what about selecting a queue at random?  In the example above, I can certainly see how the average wait is 25 minutes if there are not only three separate queues, but three separate customer arrival processes, each with an average inter-arrival time of six minutes, for an aggregate arrival rate of one every two minutes.  I suspect that the random queue selection above may be equivalent to this in the sense that it yields the same distribution of waiting times.  Simulation bears this out, but I am not sure if things work out the same analytically.

As you might expect from the title, this post is motivated by gift exchanges common during this holiday season.  In particular, the “Yankee swap,” or “white elephant,” gift exchange involves some interesting mathematics that remind me of the classical secretary problem.

First, the secretary problem: suppose that you must interview each of candidates for a job, and after each interview you must decide whether to accept the candiate, or reject him/her and continue with the next interview.  You cannot return to a previously interviewed candidate.  What should your strategy be in order to maximize the probability of selecting the best candidate?

This problem is interesting in part because the performance of the optimal strategy does not depend (much) on ; you can select the best applicant with probability approximately by interviewing– and rejecting– about candidates, then accepting the next candidate that is the best so far (or the last candidate if a “new best” is not found).

The Wikipedia link above provides plenty of information about the problem and its solution, which I won’t rehash here.  But the reference at the bottom of this post has a lot of additional interesting information about generalizations of the problem.  For example, rather than maximizing the probability of selecting the best candidate, what if you want to maximize the expected rank of the selected candidate?  This frankly seems like a more realistic objective, at least in this particular context.  One fascinating result is that, similar to the original problem, the optimal expected rank is also (nearly) independent of , about 3.8695.

What does this have to do with exchanging gifts?  The Yankee swap gift exchange may be viewed as a more hostile variant of the secretary problem.  Suppose that you represent one of  companies (participants) each hiring a secretary from a pool of candidates (gifts).  The first company interviews a randomly selected candidate, and is initially stuck with that candidate.  Each subsequent company may either interview a randomly selected new candidate, or “steal” a candidate previously interviewed by another company, in which case that company must interview a new randomly selected candidate.  Depending on your position in the selection order, should you choose to “steal” a previously interviewed candidate or interview a new candidate, and what is the probability that you will end up with the best candidate?

(Note that we have made several simplifying assumptions in this problem.  First, this is the “standard” Yankee swap with rules as described above.  There are a lot of variations, including longer series of stealing, “freezing” gifts that have been stolen a number of times, etc.  Also, as with the original secretary problem, the goal is to get the single best secretary, or gift, or whatever, as opposed to the one with the best expected rank.  Finally, and least realistically, let us assume that everyone ranks the candidates/gifts in the same order.)

It turns out that, as expected, the last person to make a selection has the largest advantage, getting the best gift with probability .  More generally, the probability that the person in position ends up with the best gift is

Slightly less obvious is the fact that the optimal strategy does not have the “cutoff” property as in the secretary problem: everyone (except the first) should always steal the best gift seen so far… except that for the second person, their strategy does not matter.  That is, their performance is not affected by whether they steal the first person’s gift or select a new one.  Can you see why?

• M. Ajtai, N. Megiddo, and O. Waarts, Improved Algorithms and Analysis for Secretary Problems and Generalizations, SIAM Journal of Discrete Mathematics, 14:1 (2000) 1-27.

I have been reading Thomas Miconi‘s doctoral thesis, “The Road to Everywhere: Evolution, Complexity and Progress in Natural and Artificial Systems.”  It is available online, and it is very accessible, fascinating stuff.  If you think you understand evolution (I did), read this paper and then consider whether you understood it as well as you thought you did (I didn’t).

One of the most interesting aspects of Miconi’s work is his replication and extension of the earlier work of Karl Sims on simulated evolution of “virtual creatures.”  These are by no means the only instances of simulated evolution (one section of Miconi’s paper describes various historical and current approaches, and is a great read even on its own)… but they are certainly some of the coolest.  The virtual creatures are not just abstract mathematical representations as is often the case, but realistic physical objects that move and interact with each other in a 3D world.  Miconi provides an entire page of links to videos showing these evolved creatures in action; if you only visit one link from this post, this is the one you want.

My particular interest and motivation for this post deals with simulation of (1) “open-ended” evolution, and (2) speciation, and how these two concepts relate to creationists’ difficulties with the theory of evolution.  Simulations of evolution like those described above are sometimes presented as counter-arguments against creationists’ claims of a need for an intelligent designer.  (One interesting such presentation can be found here.  Before continuing, I recommend checking it out to see if you find the same problems with it that I did.)

The difficulty with using results of simulations like these as arguments against ID is that most of them involve an explicit fitness function.  That is, when two creatures (or clocks, or whatever) compete or are otherwise compared to determine who survives or reproduces and who does not, this determination is typically made by measuring how each performs some pre-specified behavior, such as traveling a certain distance, picking up a block, or telling time with a certain accuracy.  The result is that the simulated evolutionary process yields successive generations that tend toward better and better performance of that pre-specified behavior.

In the natural world, however, there is no pre-specified optimal behavior.  Organisms interact, some reproduce, some don’t, some are killed, some starve.  What evolves is simply whatever persists and propagates, not necessarily what might be “best” according to some explicit fitness function.

For a computer simulation to address this issue, its fitness function must be implicit.  Miconi addresses in some detail what is meant by this distinction; my take on it is that the determination of who reproduces and who doesn’t should be based on the result of simulation of physical processes that is explicit only at the lowest possible level.  For example, Sims’ original virtual creatures had oscillators as a primitive building block; Miconi’s later work was an improvement in this sense in that his virtual creatures’ building blocks were more primitive, representing lower-level behavior… and oscillation (critical to locomotion) evolved as a higher-level behavior “implemented” in terms of these lower-level building blocks.  This admittedly comes at a price of higher computational complexity… which is in part why it took us 3.8 billion years to get here.  (One of the more interesting attempts at such “open-ended” evolution is Tierra.)

Another characteristic common to many computer simulations of evolution is the explicit concept of species.  Indeed, in many simulations there is only one species, with no opportunity for divergence; in other cases where there are multiple species, a creature’s species is “hard-wired,” so that species A only reproduces with species A, and only fights with species B.

This last is what got me thinking about all of this in the first place.  Creationists like to make what is to me a rather baffling distinction between “micro-evolution” and “macro-evolution.”  This seems to me to be mostly a difficulty with speciation.  The idea is that, “Okay, maybe members of any given species evolve over time (micro-evolution), but species do not diverge into separate species that subsequently do not interbreed (macro-evolution).”  We might become better humans, but we don’t share ancestors with apes.

To respond to this reluctance, can we simulate speciation?  To do so would require less “hard-wiring” than that mentioned above.  That is, in addition to letting evolution control the morphology and behavior of the simulated creatures, it must also be able to control and modify the mechanism for reproduction.  A simple example of this might be preventing interbreeding between two creatures if the Hamming distance between their genotypes exceeds some threshold.  Different criteria might be suitable for simulations where the genotype is encoded not as a string– as it is in life as we know it– but as a tree, which can be handy and more robust to “crossover” when the encoding is similar to that of a computer program.

This is mostly all just musing on my part, but I am currently between “projects,” and it is fascinating and tempting to pursue such a simulation.  But it turns out that this sort of analysis is certainly not new; links to several interesting papers on the subject can be found here.

[Edit 2024-08-07: The code described below has been updated for VPython 7.6.5, and is available on GitHub.]

This is an update to last week’s post about using VPython to make a robot simulator.  Last week, the vturtle.py module was really just a fancy turtle graphics engine.  The robot could move around and leave a drawing trail, but it could only dead reckon because it didn’t have any sensors.

This week, I added the ability to create obstacles for the robot, in the form of walls… or other robots.  The robot can now “bump into” things, with a stall sensor indicating when its movement is impeded.  You can also add proximity sensors, with configurable range and mounted in configurable locations around the circumference of the robot chassis.  (As before, everything is modeled after the Scribbler; I experimented with the real thing to come up with a reasonable default setup, which includes three sensors looking left, front, and right, with about 10 cm range.)

You can download the updated version at the usual location.  Here is a screenshot of a simple demo with the robot “wall-following” a maze:

The vturtle robot wall-following through a maze.

Admittedly, much of the motivation for this project stemmed from its utility for students learning about programming.  Working with the Scribbler itself is a lot of fun, but it is not always available (e.g., when the students are not in the classroom), and even when it is, it can be a little flaky at times.  This simulator allows students to experiment with pretty complex robot behavior any time, anywhere they have a computer.

But there was another reason I found this project interesting.  There is some nice mathematics involved in the collision detection and proximity sensing, some old hat, some new to me.

All of the sensor-related computation involves detecting the intersection between:

1. Two circles, when the robot collides with another robot;
2. Two line segments, a proximity sensor beam and a wall; or
3. A circle and a line segment (more on this later).

The first case is the simplest; just compare the distance between the robots with the sum of their radii.  The second case is more involved, and is perhaps the most elegant, but is a pretty standard computational geometry problem.

The third case, the intersection of a circle and a line segment, was one I had not investigated before, and occurs in two situations: when a robot collides with a wall, or when a robot’s proximity sensor beam intersects another robot.  The general problem is shown below:

Intersection of a circle and line segment.

Given a line segment and a circle centered at with radius , we want to determine if the two intersect.  Representing points with corresponding vectors, we can parameterize points on the line segment with:

An intersection occurs when a point on the line segment is also on the circle; that is, when is distance from :

Letting and , we can express this condition more efficiently without the underlying square root operation as:

This expands into a quadratic in ,

where

So there is an intersection iff this quadratic has a root in [0,1].  See the vturtle.py code for an example implementation.

Finally, following is example source code for the maze demo screenshot above:

import vturtle

# Create robot on a walled tabletop.
robot = vturtle.Robot(obstacles=vturtle.maze(rows=5, columns=5, cell_size=40))
robot.pen_up()

robot.fast_forward(5)

# Move until we find a wall.
while not robot.sensor(1):
    robot.forward(3)

# Wall-follow, keeping a wall on our right.
robot.left(90)
while True:
    while not robot.sensor(1) and robot.sensor(2):
        robot.forward(3)
    if robot.sensor(2):
        robot.left(90)
    else:
        robot.forward(15)
        if robot.stalled():
            robot.backward(3)
        robot.right(90)
        robot.forward(20)