Random walk

A random walk[1] is a statistical concept which is often humorously introduced by comparing it to the trajectory of an inebriated person wending their way home after the saloon has closed for the night. Lurching from lamp post to lamp post, having forgotten from whence and unsure of where to go, chance selects the next destination. How long will it take to get home, or even to return to the bar? More formally, given a graph with nodes and links and probabilities with which to choose among them, what is the probability of getting from one node to another. Or dispensing with probabilities, one could simply try to make a list of possible paths.

The process applies to the Game of Life when it is found that there are certain basic patterns which can be polymerized, and someone wants to know how many, and in what ways. Examination of lists of Life patterns confirms the tendency towards family groupings. Identifying closed walks has a special importance given the tendency of open walks to be fuses rather than wicks. Or the necessity of finding appropriate boundaries to contain them.

Domino walks
a domino wick stably terminated by a house

Single live cells tend to occur with a certain frequency as time goes on, which can be predicted but is otherwise not very informative. On the other hand, sparse pairs of cells, orthogonally connected to form dominoes, polymerize readily into common and recognizable patterns. By polymerize, we mean that they can form stable chains. Two dominoes can touch at the corners if they are perpendicular to one another (a bridge). Parallel contact is unstable, as is any edgewise contact. Unless the polymer is closed into a loop, it will disintegrate from the ends, but stabilizing terminations can often be found.

The result is an extensive collection of lakes, of which the smallest is a ring of four dominoes called a pond. The element of random walk enters because, seen from the point of view of the last domino, the next one can be placed either to the right or to the left (but not two simultaneously, one in each direction).

Pond walks
  • a pond is a domino tetramer
  • a bipond is a pond dimer
  • straight tripond
  • bent tripond
  • a pond of ponds, a tetramer

What is now interesting is that ponds can act as squarish dominoes, in the sense that two can be joined at the corners, to get a bi-pond. Whereas left and right for a domino is reckoned with respect to its long axis, the long diagonal is more appropriate for biponds, leaving straight and bent to describe continuations. The straight successor of a bipond would be a tripond, thereby founding a family of multiponds. The bent succession, for which left and right are still apropriate, closes after four steps when they are taken with the same handedness. That would be the start of a new recursive process, because the resulting tetramer now behaves just like a pond.

All in all, in contrast to the dominoes, paths can now branch at both corners, creating a veritable marshland agar. Possible branching represents an important distinction. When only one branch at a time is permitted, although the resulting pattern may lie in a plane and be extremely convoluted, it is essentially one-dimensional. Associated possibilites which have to be considered include whether or not the walk is self-intersecting or even closed. If the intersection is consistent, the path just continues onward. But branching along a cut line into another of multiple planes may be used to reduce confusion. Calculating the liklihood of closure, implying return to the starting point, is an important goal for the study of walks.

The territory that could be covered by multiply branching walks would be two-dimensional, a genuine meshwork rather than just a line. It may still have holes, not having to cover the whole plane uniformly.

Herparian walks
a snake resembles a domino in many ways
snake bridge snake, one of three similar snake dimers

Another object which polymerizes even more readily than a domino is a snake. First, as a freestanding object, there is no concern for stabilizing terminal monomers. Then, better than for ponds, there are three joining alternatives, one of which leaves the bodies of the snakes parallel; more of a tie than a bridge. Walking a snake is little different than walking a domino or walking a pond, so the same conditions of wandering, crossing, and closure apply. The more complicated the basic unit, the more intricate the resulting wick or agar; their grand variety is a consequence of having multiple choices for connecting the same basic pattern.

Combined Loaf and Beehive walks
one of many walks combining beehives and loaves

A beehive resembles a pond shortened in one direction, while a loaf looks like a pond cut in half by its diagonal. Pairwise combinations include beehive at beehive, beehive at loaf, and half-bakery, showing that the figures readily form mixed polymers. Many other still lifes, such mangos, loops and cis-fuses with two tails can also be included in this polymer. Some still lifes, such as hat can be used at the end, but not the middle. Allowing a random walk to stop rather than to close by returning to its starting point or more likely to continue indefinitely, leads to a variant picturesquely known as a "random walk with manholes" (pity that poor inebriate!).

The implication for random walk theory is that stepping can be combined with a phase change, whose probability should be included along with that of directional choices. Even if there is no change of direction, there will be uniform subwalks of varying lengths mingled with each other.

Phoenix walks
  • three phoenix avatars
  • smallest closed phoenix walk
  • an avatar appearing in four polymers

Some phoenix avatars are shaped just like dominoes. Although they oscillate with period 2, giving alternate generations two different colors and superposing them in the same diagram makes the resemblance more evident. Their joining rules can be much more complicated than just choosing the ingredients and directions for continuing a walk. Even with that restriction numerous interesting patterns can be constructed or recognized as resulting from random walks. The prototype phoenix is the homologue of a pond or a snake ring.

Summary

By its nature, the word walk implies a one-dimensional structure; to say random suggests an element of choice. One expects to be able to enumerate the possibilities and explore their relative frequencies. But all walks are not the same, inviting a discussion of their origins and various characteristics, including the following:

  • origin
  • dimension
    • one dimensional on a line (frieze)
    • one dimensional embedded in a plane
  • objects visited or transported
    • points or simple objects on a fixed lattice
    • objects with an internal structure affecting their linkage
    • various mutually compatible objects
    • oscillating or variable objects linking in all phases
  • recursion
    • objects formable in one walk become hyperobjects for a hyperwalk
gollark: ↑ browser
gollark: ```html<!DOCTYPE html><input type=url id=i><iframe id=j></iframe><script>i.oninput = () => j.src = i.value</script>```
gollark: You should launch osmarksßbrowser™.
gollark: Browsers are conceptually complex even if you're used to them.
gollark: They didn't have to remove the switch to keep the old UI.

References
  1. William Feller, An Introduction to Probability Theory and its Applications, Volume 1, John Wiley and Sons, 1957
This article is issued from Conwaylife. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.