Random Thoughts on Self-Avoidance

January 31, 2025 11:53 AM

Every Sunday morning you go for a walk in the city, heading nowhere in particular, with just one rule to your rambling: You never retrace your steps or cross your own path. If you have already walked along a certain block or passed through an intersection, you refuse to set foot there again. This recipe for tracing a loopless path through a grid of city streets leads into some surprisingly dark back alleys of mathematics—not to mention byways of physics, chemistry, computer science and biology. Avoiding yourself, it turns out, is a hard problem. from How to Avoid Yourself [American Scientist]
posted by chavenet (17 comments total)

Oh, this is totally my jam. Literally right now I'm working on some turtle.py module stuff for Python, but previously I've also wanted to create a random space-filling curve thing which has the same problem of not stumbling "into a blind alley, getting trapped at a lattice site where none of the neighbors are unvisited."

I've also been meaning to read The Algorithmic Beauty of Plants (free book PDF) to learn about L-systems. And maybe finally read the entirety of Godel Escher Bach.

Thanks for posting this.
posted by AlSweigart at 12:10 PM on January 31 [4 favorites]

Been avoiding myself since the 1960s
posted by JohnnyGunn at 12:19 PM on January 31 [10 favorites]

I was just listening to a friend talk about these walks! (A self-avoiding talk is when you always get a student author to present the paper.) Anyway...the talk was about the conjecture that if you make the step sizes smaller and smaller, in the limit (defined carefully) as step size goes to zero you get a fractal curve that obeys certain very cool properties.
posted by TreeRooster at 12:32 PM on January 31 [3 favorites]

I've been wanting this idea implemented into an app to help me fully explore a city. Bonus points for collaborative mode to help you walk with friends, connect with strangers, and catalog public art or other points of interest.
posted by grokus at 12:36 PM on January 31 [4 favorites]

Oh ho, the summary made me think Brian Hayes, whose blog I haven't read for a while. And, indeed, that's the author. Tnx for heads-up.
posted by BobTheScientist at 12:57 PM on January 31 [2 favorites]

Always live on a randomly Eulerian graph, is my advice.
posted by Wolfdog at 12:58 PM on January 31 [7 favorites]

In lockdown in 2020 I rebuilt a derelict motorbike, and one of the first long rides I made was a Eulerian trip around the vehicle ferries of Sydney. It’s surprisingly satisfying to work out.
posted by Fiasco da Gama at 1:27 PM on January 31 [6 favorites]

You had me at "random". I very much enjoy, whenever possible, taking streets/paths/routes that are new to me, just to see and discover new places. Especially great on a bicycle.

The novelty of exploring a new route is usually an effective way to get me "out" of myself, at least for a while. So that's also self-avoidance, no? But math-ing it up could add new interest.

I have a copy of Godel Esher Bach. I dip into it when I want to think I'm intelligent, or need to be reminded of my intellectual shortcomings.
posted by Artful Codger at 1:52 PM on January 31 [2 favorites]

For the last several years, I have been transcribing numbers from online Sudoku puzzles into a 9 x 9 spreadsheet grid. It allows me to add value like counting the numbers of each digit in the grid and annotating rows and columns with partial solutions. ANNyway, the transcription is a travelling salesman problem and I try to be efficient minimizing the number of cursor strokes to get 24-27 numbers onto the grid. I guess self-avoidance is one aspect of that. But I don't try tooo hard to get the best solution because how would I know? Cogitating the transcript is also part of the process of brain engagement that is supposed to fight off senility. Tho I appreciate that it may seem to readers that I'm there already.

GEB-EGB? Back in the late 70s Douglas Hofstadter published a 800pp tome called Gödel Escher Bach an Eternal Golden Braid . I ate it all up at the time as it was long, discursive and full of interesting connexions. About twenty years ago I took the book down from its shelf and tried to read it again. Clearly my attention span had slumped several points in the intervening decades because I found it Eat Bray Gibbön.
posted by BobTheScientist at 2:29 PM on January 31 [1 favorite]

Very cool. This type of city walk is actually a plot point in Paul Auster's novel; City of Glass.
posted by CplCarrot at 2:34 PM on January 31 [2 favorites]

There used to be an app I loved that divided the world into little squares. If you traveled into the square it colored in the map. I don't remember what it was called but I know it disappeared from the app store at some point, which was a shame.
Before that, I remember doing this in an analog way. I got a paper map of the city, and drew over the streets with a marker to indicate that I had walked down them already. I recommend it!
posted by BuddhaInABucket at 3:01 PM on January 31 [3 favorites]

Mr BlueHorse has a thing where when in Boise, he just has to drive different roads to get from A to B. Drives me nuts, because I'm an A to B‐shortest/familiar route person. Part of his reasoning is that he grew up in Boise and likes to see old places or how things have changed. Mostly it's avoiding stoplights, construction, or traffic, and part is that he just Does the Thing. What it means for me is that I have seen things I wouldn't have seen otherwise, and that I don't get lost, even being from out of town, unlike friends that live in Boise but don't drive different routes. I might not know exactly the shortest way to to get somewhere new, but I can get you there. The downside is trying to remember if Pine is before or after Franklin going North , or which road doesn't go through to State St.
It's all good.
posted by BlueHorse at 3:50 PM on January 31 [2 favorites]

It seems curious that he doesn't mention Dérive or Psychogeography, which might seem closely related to a project like this? Of course, Brian Hayes is pretty focused on the mathematics of random walks, and not the surrounding environment.

The sudden change of ambiance in a street within the space of a few meters; the evident division of a city into zones of distinct psychic atmospheres; the path of least resistance that is automatically followed in aimless strolls (and which has no relation to the physical contour of the terrain); the appealing or repelling character of certain places—these phenomena all seem to be neglected. In any case they are never envisaged as depending on causes that can be uncovered by careful analysis and turned to account.

Debord was talking about walking in Paris, and interesting place for something like this.
posted by ovvl at 4:47 PM on January 31 [4 favorites]

Anything that gets us out of our rut, or helps us find our own strangers path (JB Jackson). Unlike Mr Jackson I think we each have our own strangers path through a place.
posted by unearthed at 5:16 PM on January 31 [2 favorites]

Oh man, I love random walks and especially self-avoiding walks. I've gone down a bunch of little amateur rabbit holes on lattice walks over the years, feels like I get sniped into thinking about this or that variation again every year or two. I made some plotter art of accumulations of self-avoiding walks in 2021, plus probably a dozen twitter or mastodon threads full of Inkscape and graph paper scribblings while I thought out loud about bits and pieces.

And it bumps into one of my other pet math objects, space-filling curves, which are in a sense just very well-behaved self-avoiding walks -- instead of wandering at random and sparsely across a lattice they fill up a confined section entirely; Hilbert curves and Peano curves are among the most famous and elegantly orderly of the bunch, but the set of possible space-filling curves for a given n*n lattice itself grows significantly with n, though even more slowly than the set of unrestricted self-avoiding walks for the same size lattice.
posted by cortex at 9:34 PM on January 31 [2 favorites]

This is my usual strategy when going for walks or runs myself, but I knew nothing about the math behind it. Thanks for sharing!
posted by hydropsyche at 1:22 PM on February 1 [1 favorite]

This is so out of my wheelhouse that I'm over here thinking: this person lives in a city with such logical, cooperative streets... and not on a dead end.
posted by stormyteal at 7:44 PM on February 1 [1 favorite]