Meandering through search strategies.
“We only came here to pick up some beer!” you think. “Why does this keep happening?” You and your friend walked into your supermarket of choice only five minutes ago and headed straight for the beer isle. You had agreed in advance that you needed beer and only beer, that this would be a clean, clinical run, the Bin Laden Assassination of Thursday evening beverage collection.
And yet somehow, just like every time, your dumb idiot friend wandered off somewhere. You only stopped briefly to examine a sweet deal on Maltesers and took just a tiny detour into the magazines aisle to check out a funny headline you thought you saw, but still somehow your friend managed to wander away and get themselves lost. Every damn time, you think. Why do you keep hanging out with them anyway? Worse still, those girders in the roof are blocking your phone signal and you can’t even phone your friend to sort this out. Dammit life really sucks.
Time is of the essence. Your friend’s flatmate has been giving you sultry looks and you think you just might be in there. You have that film you know they really like queued up on your laptop and you have your moves all planned out. But if you don’t get back soon, they’ll have gone to bed and the moment will be lost. It’s clearly really important that you pick the optimal searching strategy so you can find your friend and get the hell out of there as quickly as possible. What do you do?
To Search or Not To Search?
Like any good supermarket, this one has an NxN grid layout.
My mother used to tell me that if I get lost I should just stay where I am. That way I’m easy to find. What do we expect to happen if you do that? If you stay still and your friend searches methodically, searching every intersection in turn until they collide with you, you’ll be found after searching at most
N² intersections (which we’ll hereafter call
N² time). Awesome.
But there’s a problem. What if your friend’s mother was also as wise and brilliant as mine? If they’ve been given the same advice then they might also stay where they are, waiting for you to come find them. If that happens you will never find each other no matter how long you wait. You will live out the rest of your days at the same intersection, surviving on dairy products scavenged from other people’s abandoned shopping carts. You will ask passers-by for news of your friend from faraway lands but their glazed expressions will look through you like you’re some immaterial ghost, like they’re afraid your desperation and longing and sadness might be contagious, like there is a great deal on pesto just behind where you’re standing. Eventually you will die. Your flesh will rot and your bones will be picked over by the resident supermarket vultures. You will never get to make out with your friend’s flatmate. This is a dark future indeed.
That’s what happens if you both decide to stay still. What about the opposite case? What if both of you start searching methodically, visiting every intersection in order? Of course, this would probably work and you’d eventually run into each other. But consider this worst case: it is possible that you both end up following the same path of searching around the store but out of sync with each other. If that happens then once again you’ll never find your friend. You will have constant near misses, doomed to endlessly repeat your strange orbit. Eventually you will keel over from exhaustion. If your friend still has the strength to make one more circuit of the supermarket then — in at most
N² time — they’ll come across your limp body. For a second they’ll wonder if you’re even breathing: perhaps they came too late? But no, they will see your emaciated chest slowly rising and falling and they will weep, weep with relief that you’re alive and with primal, unbridled joy that your ordeal is finally over. “Why, why did we both decide to search methodically?!”, your friend will cry. “Why didn’t I stay where I was?!”.
You will still not get to make out with your friend’s flatmate.
Rules save the day
Both the above strategies fail when you and your friend follow the same actions. If there’s a way to coordinate so that you can ensure that you both act differently then we can prevent this. How could we go about coordinating like this?
The most straightforward thing to do is to agree a strategy between you when you enter the store. I’ve tried this though, and apparently most people aren’t as worried about the possibility of being infinitely lost in a supermarket as I am. Saying “hey, how about if we get separated, I’ll stay where I am and you take a hamiltonian path around the supermarket until you find me” just gets me funny looks.
Here’s another idea: we need to agree as a society on an heuristic to use in these situations, so that the choice to make in this situation is implicitly known. What we need is a surefire way to break symmetries between pairs of people. The simplest way to do this is to bijectively map the population to a total-ordering (that is to say, order everyone) so that everyone can easily tell how they order compared to each other. Ideas I’ve entertained include:
- Gender: no good. Not a bijection. If two men walk into the supermarket together, gender is useless as a symmetry breaker.
- Birthday: Slightly better than gender. But what happens when you’re buying cake for a joint birthday party with someone born on the same day as you? Chaos, that’s what.
- Height: not bad. Height is effectively a continuous scale and so it’s unlikely (probability 0, or ‘almost certain’) that two people are going to be exactly the same height, making this a bijection to a total-ordering. We can put this into practice by saying “the shorter person must go to find the taller one”. I recommend doing it this way round because tall people are easier to spot.
- On the other hand, I don’t know offhand how I rank height-wise compared to all of my friends, and things like hats and heels complicate the issue by fuzzing the height mapping. Obviously we can resolve this in time honoured fashion by doing that back-to-back thing… but that requires being next to each other already, which rather defeats the point.
- Name: now we’re getting somewhere. Let’s order ourselves lexicographically, surname first. For clarity we can say we’ll use the most common spelling of the full name, so Tom becomes Thomas and Ellie becomes Eleanor. Then we have a total-ordering, and we can decide that the person who’s name comes first should go find the other one. Sorry Aaron Aaronson, you’re going to get tired legs.
This works perfectly until you’re in the supermarket with someone with the same exact name as you. When I was 16 I was invited to a Facebook group containing twenty-three people named Mike Heaton. If we all got together for some weird Mike Heaton convention… well, I guess we’d need to stay the hell away from supermarkets.
The other issue (the ONLY other issue) is that this genius idea requires everyone in your party to know the convention, otherwise it’s useless. I’m hoping the government makes a PSA video about this idea, so together we can beat Supermarket Death. Until that day I recommend sharing this article with all your friends. Even better — you can use “have you read Mike Heaton’s blog?” as a great way to identify the smart, interesting, attractive people that you want to be your friends.
Walk Like a Drunkard
Actually there’s another strategy, one which you can implement unilaterally without worrying about this silly coordination bollocks.
To reiterate, the problems we found above arose because there was the possibility of the two participants following the same path through the store. We can prevent this by adding randomness to our movements.
Suppose at each intersection we make a blind choice of direction to go next.
The path we follow is colloquially known as a drunkard’s walk for obvious reasons, and non-colloquially known as a discrete markov decision process on Z² with uniform single-stepped transition probabilities. Of course, because we’re acting randomly we can’t tell exactly when we’re going to find our friend. But we can bound the expectation (average time) as
O(N²), regardless of our friend’s strategy.*
Life Imitates Maths
So we’ve engineered some pretty optimal solutions to this problem. But this is actually a case where human beings have come up with a nearly optimal solution already. Remember that my mum told me that I should stay where I am when I get lost. I wager your parents probably did too. This is a naturally arising example of a symmetry-breaking heuristic: in the important case when a parent and a vulnerable child are separated, the younger person stays where they are.
Second, when you do get lost in the supermarket with someone who hasn’t read my blog, you do end up exploring more or less randomly. And it does work, more or less. In fact we would do better to add more randomness to our movements. I’m sure we’ve all had situations where we try to find our friend by methodically peering down all the aisles one at a time, and where this ends hurting us because our friend is doing the same thing and you accidentally pass each other without realising. Any deviation from the perfectly random strategy increases the worst case outcome conditional on your friend’s strategy.
All right, let’s think bigger. Now imagine you have warped to the Supermarket Dimension to buy Space Beer from the Space Supermarket with your space friend. The Space Supermarket extends infinitely in two dimensions because, y’know, space.
Unfortunately you’ve got space separated! What do you do? Suppose you decide to methodically look for your friend. There’s clearly no question of searching “every” intersection in the space supermarket because it’s infinite. Fortunately all is not lost. If you adopt a search pattern which spirals out from your starting location, then you will visit any given intersection in finite time, including the one your space friend is waiting in. If you started some straight line distance
d apart, you’ll find your friend in
O(d²) time using this method.
But again, if you’re both searching at the same time using this method, it’s entirely possible that you and your friend will never meet. Even worse, unlike in the finite case you never revisit the same space twice, and so your friend will never even find your corpse if you eventually keel over from exhaustion. You can fix this by modifying the path like so: first do a radius 1 spiral from the start location, then return to the start location; repeat the radius 1 spiral and extend it to radius 2, then return to the start location; repeat the radius 2 spiral and extend it to radius 3; and so on. Unfortunately then you’re repeating your
O(d) times before you find your friend, so you’ll take
O(d³) time. Giving you even less chance of getting to try your luck with your friend’s space flatmate.
And what about moving randomly? Let’s say we chug our space beer and begin a drunkard’s walk from our start location, and suppose our friend is standing still. Now the maths gets a bit interesting. Can we expect to ever find our friend? It’s not obvious that we will — our walk could just spiral off in the wrong direction and never return to where our friend is. But interestingly it turns out we can be sure we will eventually find our friend: with probability =1, a given 2-dimensional drunkard’s walk will visit any given coordinate in some finite time.
In fact we’re agnostic as to whether our friend stays where they started, or decides to go on their own random walk. Given that there are no exterior walls to our space supermarket we only care about the relative movement between the two of us. So we don’t care whether we’re moving or they’re moving, it’s the same thing, and we can still be sure of finding our friend. It might be clearer to imagine that we move at time
t=0,1,2 and so on, and our friend moves at time
t=0.5, 1.5, 2.5… . Then having two walks going on at the same time is like having one walk which moves twice as fast.
Ok so we know we can be certain we’ll find our friend. How quickly do we expect this to happen? Bad news.
- It turns out that the expected ‘first hitting time’ from one point to another is at least as big as the expected ‘first return time’ from a point to itself, up to a positive constant multiple.
E(O(first_hit(x,y))) >= E(O(first_hit(x,x)))
- Also, the first return time turns out to be equal to the reciprocal of the proportion of time we expect to spend in that state over infinite time.
E(first_hit(x,x))) = 1 / long_run_time_proportion(x)
- Our system with infinite states and random walking doesn’t favour any state over any other, so in the long run we expect to spend the same amount of time in each.
- But there are infinitely many states, so the long-run time proportion is equal to zero for each state.
long_run_time_proportion(a) == long_run_time_proportion(b) ∀a,b
⎲ long_run_time_proportion(x)) == 1
so long_run_time_proportion(x) == 0 ∀x
- The expected first return time is the inverse of this.
- Which means it’s infinite.
- Which means the first hitting time for any other space is infinite.
E(O(first_hit(x,y))) == ∞
This applies for any point in the supermarket other than the one we started in. If we start even just one aisle over from our friend, then we should expect to spend an infinite time looking for them. Even though we are guaranteed to find them eventually. Maths is weird.
Bumbling About in Babel
One final hypothetical situation. You might have read Luis Borges’ Library Of Babel short story, imagining an infinite library which extends forever in every direction — including up and down, through the use of spiral staircases. The library contains every book which could possibly exist. The information-theoretic implications of this are themselves fascinating, but for now let’s just concentrate on the topology.
Suppose you get separated from your friend in this library. Easy to do, as there are a literal infinity of literary fineries to distract yourself with. Now we have even worse news. We can still do the methodical search method and, if they are standing still, we will find our friend in
O(d³) time. But it turns out (the proof is here) that the probability of hitting a given point on a drunkard’s walk is only 34%. So we will probably never find our friend if we move randomly. Why is this? Intuitively, in three dimensions or more we have ‘too much freedom’ and it becomes possible to wander off to infinity and never return. How dreadful.
There are several important morals we should take away from this pleasant walk through algorithms and Markov processes:
- Society needs to agree on the lexicographic convention for finding people in supermarkets.
- Failing this, when you get lost in a supermarket, get drunk.
- Friends don’t let friends enter the infinite supermarket without an emergency plan.
- Finally, if you find yourself trapped in a Borges story… for god’s sake don’t wander off.