The Shifty Origins of "Origin Shift"

Disclaimer: I'm not an expert in graph theory, so please let me know if I get anything wrong. All proofs are either easy enough to work out yourself or can be found in the papers below. I use a variety of terminology throughout the video and in retrospect that was a terrible idea, so sorry about that.
Thanks to CaptainLuma for coming up with Origin Shift!
• New Maze Generating Al...
Thanks to DqwertyC for creating the maze generator tool!
/ @dqwertyc
Maze generator:
dqwertyc.githu...
Papers referenced:
David J Aldous, "The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees"
Andrei Broder, "Generating Random Spanning Trees"
V. Anantharam and P. Tsoucas, "A Proof of the Markov Chain Tree Theorem"
Yiping Hu, Russell Lyons and Pengfei Tang, "A Reverse Aldous-Broder Algorithm"
The puzzle of doing "Aldous-Broder on a ring" is taken from Broder's paper, and an alternative solution can also be found there.
Also thanks to Russell Lyons for making a lot of useful resources freely available on their website.
rdlyons.pages....

[@The-Limited-Fun]

A couple of extra points: One important stopping condition I forgot to mention is 'the cover time', when the random walk has visited every cell. Once that's happened, the resulting maze will no longer depend on the "original maze" at all. Then, Origin Shift and Aldous-Broder have the same probability distribution, so in particular Origin Shift will generate a uniform spanning tree at cover time regardless of where it starts. Also, I realise I mostly focused on comparing the algorithms mathematically rather than practically. So, notice that if you started with the "basic maze" (with horizontal lines and one vertical line on the right), then you could start Aldous-Broder in the bottom-right corner. Each time it reaches an unvisited cell, first delete the edge immediately to its right (or immediately below it if it's on the right wall), and then add the edge you'd normally add with Aldous-Broder. This version of Aldous-Broder has an identical probability distribution to Origin Shift (if you run them both for the same number of turns). You can stop it at any moment and get a perfect maze. Of course, with Origin Shift, you have to remember which direction each edge points in, whereas with Aldous-Broder you have to remember which cells you've visited. You'll also likely end up having to make more changes if you use Origin Shift.

[@miguelanjo2776]

we just learned. origin shift predates aldous broder. the origin has shifted

[@captainluma7991]

So its true that origin shift is mathematically equivalent the reverse Aldous Broder! I had a couple comments telling me to check out the reverse Aldous Broder, but the math was too confusing for me lol. But you explained it in a way that made a lot more sense and I was finally able to understand it. I tried it myself in my Minecraft world and was surprised to find that it worked. Reversing the sequence of an Aldous Broder path, and using origin shift results in the same spanning tree. Great work on this video! It's clear that you put a ton of effort into the research behind the true origins of origin shift.

[@ITR]

Not sure if "true origins" is the correct phrase here, since you didn't make origin shift with any knowledge of Aldous-Broder. Like, an "Independent discovery" is different than "Standing on the shoulders of giants"

[@GreyMaria]

I can summarize this entire video in ten seconds by saying "Origin Shift improves on Aldous-Broder by actually fucking initializing a valid maze state."

[@The-Limited-Fun]

Yep, exactly! It's a clever idea! And interestingly, any other growing-tree algorithm can also be initialised with a valid maze state! And even more shockingly, it turns out that if you initialise Aldous-Broder with the same starting maze as Origin Shift, and start them in the same place, then they end up with the same distribution at each step!

[@Deusovi]

I think you're understating the isomorphism between the two a bit. The fact that one is just the "reverse" of the other is a much 'tighter' connection than just "they simply have the same final results". That would've been true for many other algorithms as well (at least, if you include the stopping condition of the walk visiting every cell)! You could visualize this by 'tracing out' the random walk in 3d (i.e. do the random walk, but also travel up a few blocks each time). Then, Origin Shift is just looking at the result from the top, while Aldous-Broder is just looking at it from the bottom. Still though, cool video, and I appreciated the emphasis on avoiding being dismissive! It's a natural instinct for those of us more familiar with the field - like, yeah, it probably HAS been done before... but so what? "Hey here's this idea that's similar to yours - people have studied it in a ton of detail" should be the start of a conversation, not the end of one!

[@The-Limited-Fun]

Yeah, I suppose you're right! And one way to structure the video would have been to focus a lot more on the case when you're generating an entire maze with both algorithms, since then the isomorphism is very natural. But I thought people familiar with Origin Shift would find that a bit unfair to the algorithm, since its main supposed benefit is that it can "change a maze" and can be stopped at any time. So I partly just wanted to explain why the fact that Origin Shift can "change a maze" isn't as unique as it sounds. But more importantly, the fact that Origin Shift (or Reverse Aldous-Broder) and normal Aldous-Broder have the same distribution (at each time step) even when you start them in the same place definitely isn't as obvious as saying that one is the other but backwards! And I can't find any other algorithms that this would also apply to, even ones that also generate a uniform spanning tree (such as Wilson's algorithm). So that was the surprising result of the video I wanted to focus on. And I think just saying that "one is just the reverse of the other, so they're obviously the same" is an easy way to convince yourself that it's a lot simpler than it actually is. I definitely found at least one source while researching that did exactly this! But yeah, I like your 3D way of looking at it! I guess "looking at the walk from above" means "only looking at the edges that you can see the far end of", which means that "looking at it from below" is exactly the same thing but from the other side. And I suppose it helps visually explain why Origin Shift can keep changing the tree, unlike Aldous-Broder!

[@isaiah0xA455]

At 7:43 I think you’re missing the point of an ever changing maze. It’s supposed to be a maze (that is, a navigation puzzle). You’re not supposed to wait for the walls to open, you’re supposed to go around them. To that end, I would argue that having most of the maze be static most of the time is a feature. If all of the maze is changing all the time, it’s not really a maze, it’s a waiting game as you head directly towards the end.

[@The-Limited-Fun]

I think you're right. An ever-changing maze does sound quite cool actually!

[@xoeleox2079]

I believe the real issue here with using either algorithm to create a changing maze is that the changes only ever proceed to adjacent nodes, which is what would allow a player to follow the changes. A changing maze, for it to be successful in performing the task, must be more dynamic in when/where it can change, otherwise a player is incentivized to follow the region of change until they find the end, trivializing the task.

[@Pystro]

@@xoeleox2079 You could also keep the player from following the changes (or waiting for the changes to come to them) by just killing players in the cells that you change. And it doesn't actually matter for that if you use origin shift or if you change connections completely at random. The only difference is that if (like in origin shift) the changes are localized to a certain small area, then the player can attempt to run away from them.

[@TimothyChapman]

So, Origin Shift both predates Aldus-Broder and improves on it. And the only practical difference between the two is that origin shift can redirect existing links while Aldus-Broder cannot, and Origin Shift always leaves a trail pointing back to the origin.

[@NicknamingName]

mazes are just complex dead ends with a through hole

[@ASE_Ridern123]

Thank you Sherlock

[@2stral]

Great video, one question: why the word 'shifty' in the title? To me, at least, that implies something shady, but i may be wrong

[@rileymack1489]

It's just a pun

[@megaing1322]

Because it's funny. It has no actual meaning in this case.

[@2stral]

Fair enough

[@iharding01]

One thing that I don't think you mentioned was the complexity of the algorithms. Based on how they work, I would assume they take the same amount of time, but if one is more efficient than the other then that's definitely a point in its favor.

[@Oshroth]

They are similarly complex. The main difference between them is the time to complete the process. Aldous-Broder takes a random amount of time to complete because it doesn't have an fixed upper bound (in theory a run of the algorithm could take infinite time to run, or longer than the heat death of the universe), while Origin Shift is "complete" at the end of each step, so you can stop at any time and have a solvable maze. If you want to generate a completely random maze using Origin Shift (i.e. by continuing until every node is visited at least once), then it will take as long as Aldous-Broder and produce an output that would match a maze produced by Aldous-Broder.

[@conando025]

Dude what a great explanation. I study Computer Since and explanation of complex algorithms tend to get quite heavy to follow if they go into detail but this was wonderfully crafted to be approachable shile not missing out on important details

[@cmyk8964]

TL;DR: Origin Shift is equivalent to Aldous-Broder, except that it starts with a valid (but shitty) perfect maze as its initial state, instead of a blank field (if you pretend the overwritten cells were like their end state the whole time).

[@isabellegalletly1814]

Always fascinating videos on things I didn’t know existed

[@kaiserinjacky]

these algorithms having the same results and distribution doesn’t seem particularly interesting to me. they’re both uniform spanning trees, meaning any maze is just as likely as another maze - this isn’t unique to aldous-broder. wilson’s algorithm also produces a uniform distribution of mazes. i get origin shift being aldous-broder but backwards is significant, but i think the point of them having the same distribution was way overstated in importance in the video

[@burt-burt]

very underrated youtuber, great job man

[@nodthenbow]

So like half way through the video you said something to the effect of "these evenly distributed random maze generating algorithms both produce the same mazes with the same likelihood" and like that's required by definition. Either I missed something, something was missing from the explanation, or you didn't know that, but regardless you might want to go over your script more to make sure it is harder to miss whatever I missed. Also you should talk about efficiency, that's almost always the most important part of finding a new algorithm to do something we already have an algorithm for (or at least it is in my field).

[@nodthenbow]

Okay I watched through again, it is the "in the same number of steps" part of the generating the same thing part that was missing at the time. It is true that by definition they both generate the same trees with the same probability, but that doesn't extend to "in the same number of steps" which probably should have been stressed earlier in the video

[@The-Limited-Fun]

​ I think I've worked out what you're referring to, and yes, you're right! I think I mostly remembered to mention "stopping conditions" but I evidently forgot to once about halfway through. Thanks for pointing it out!

[@JasonLucio-g2h]

Maze? Or something. I think I forgot.

[@JasonLucio-g2h]

Tree

[@JasonLucio-g2h]

Oh ahoy?

[@anselmschueler]

2:38 🤓 Actually this is a forest