4: Random Walks in the Matrixby Kirby Urner Pascal's Triangle relates to the Japanese pinball game, Pachinko, wherein userfired balls fall through a lattice of pins, by chance dropping into special cups, in which case points are awarded. The lattice is triangular, like Pascal's Triangle, meaning a ball will fall either left or right to the next row, where it will encounter another pin, fall left or right again and so on. 

The reason for this is most random paths of leftward and rightward moves contain approximately the same number of lefts as rights, meaning an average ball does not stray very far from the center. Less frequently, lefts will greatly outnumber rights or vice versa. 
We can run our trials in Python to get a sense of the relative frequencies involved. The random module, one of the standard extensions to the language, includes a choice function, which takes a list as input and returns a random selection from the list as output. >>> import random >>> mylist = ['Pig', 'Dog', 'Cat', 'Camel', 'Star Fish', 'Zebra'] >>> random.choice(mylist) 'Star Fish' >>> random.choice(mylist) 'Camel' >>> random.choice(range(5)) 2 >>> random.choice(range(5)) 0 
Consider a cubical die (as in "one die, two dice"): we might model it with a list of 6 possible, equally likely, outcomes: [1,2,3,4,5,6]. Of course if the die is "loaded" then the outcomes are not equally likely. In some games, 8 or even 20sided dice are used, so lets have a Python class called Die, which is flexible about how many faces (outcomes) it has. We will then cast our die one or more times, to get our randomized results. 


class Die: faces = 2 # number of faces lowest = 0 # lowest number face def cast(self,n): # return a list with die rolled n times trials = [] options = range(self.lowest,self.faces+self.lowest) for i in range(n): trials.append(random.choice(options)) return trials 
Returning to our model of falling Pachinko balls, lets think of left as 0 and right as 1. By casting a twosided die object N times, and adding all the 1's, we get the number of rightward moves down a path of N falls. We can tally our trials by incrementing a counter for each exit pin by one, each time a ball reaches the last row. Each pin is uniquely identified by the "number of rights" it takes to reach it. In other words, the leftward and rightward moves taken by each ball during its downward trajectory may come in any order, but it's their relative number which uniquely determines the exit pin. >>> import rand >>> odie = rand.Die() # two faces by default, 0 & 1 as possibilities >>> trials = odie.cast(10) # cast the die 10 times, storing to trials >>> trials # show list [0, 0, 0, 0, 0, 0, 0, 0, 0, 1] >>> trials.count(1) # count how many 1s (i.e. how many "rights") 1 >>> trials = odie.cast(10) # cast again, for another list of 10 outcomes >>> trials # show list [1, 1, 1, 1, 0, 1, 1, 1, 1, 1] >>> trials.count(1) # count how many 1s (remember, it's random) 9 How many trials shall we run? The numerical entries in Pascal's Triangle (or Tetrahedron) give a count of the number of pathways to that pin (vertex, sphere). In a random system, the number of encounters with a pin should be directly proportional to the number of pathways leading to it. If "all roads lead to Rome", then many travelers should encounter Rome, even if they wander aimlessly. So let's add up all the entries in row N of Pascal's Triangle, thinking "this is the total number of balls that exited through this bottom row", and then compare bottom row entries with the exit tallies generated by our random trials. Our random trials are provided by the rand.binomial function. >>> import rand >>> import series >>> rand.binomial(10) # 11 numbers because compared with Pascal's Triangle [0, 12, 48, 124, 202, 245, 214, 130, 42, 5, 2] >>> map(int,series.prow(10)) # rows start from 0, row 10 has 11 entries [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] >>> rand.binomial(12) # falling through to row 12 (of 13 spheres) [2, 9, 63, 220, 510, 757, 946, 812, 479, 220, 65, 11, 2] >>> map(int,series.prow(12)) # Pascal's Triangle entries close to same [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1] 

At right we compare graphs generated by series.prow(10), which generates row 10 of Pascal's Triangle, and rand.binomial(10), which runs random trials through the same number of rows. The graphs show up and red and blue respectively, and are clearly giving similar results. >>> import bellcurve, povray >>> import functions >>> g =Povray("gaussian.pov") >>> bellcurve.gauss(10,g) >>> myfile.cylcolor="Red" >>> bellcurve.gauss(10,g,2) >>> functions.xyzaxes(g,4) >>> g.close() Source code for bellcurve.gauss is included in Section 2. 
Gaussian Distributions: Pascal's Triangle, Random Trials 
Of course a "turtle" is also a graphical cursor, and a hallmark of the Logo language. Students entering your course with some background in Logo will find this reference to a turtle positively reinforcing. We will be defining a Turtle object in Python below, and endowing it with the power to leave a graphical trail in Povray, as per our characteristic "dynamic duo" strategy. At each "turn to play" our turtle must select from the range of freedoms available to it. In the case of Pascal's Triangle, or Pascal's Tetrahedron, the turtle has two or three degrees of freedom respectively, always in the "downward" direction (unless we want define a more gravityfree environment, leading to more freedoms). 
These latter options are more characteristic of the nonrectilinear sphere packing lattices. Our Python Turtle class accepts a list of vectors when objects based on this class are instantiated. These become the freedoms, and their number determine how many sides the "internal die object" is defined to have. 
12 degrees of freedom 
from coords import Vector import rand import shapes phi = (1 + 5**0.5)/2.0 root2 = 2.0**0.5 class Turtle: def __init__(self,freedoms,drwfile): self.freedoms = freedoms # list of vectors self.drawfile = drwfile # Povray object self.location = Vector((0,0,0)) # turtle's current location self.color = 'Red' # turtle's current color self.trail = [] # records sequence of directional hops self.ofuzzy = rand.Die() # a die object for randomizing hops self.penstate = 1 # pen is up or down def randomwalk(self, steps=1): # hop randomly for some steps self.ofuzzy.faces = len(self.freedoms) for x in range(steps): dir = self.ofuzzy.cast(1) self.move(dir[0],1) def move(self, direction, steps=1): # hop in freedoms[direction] x steps for x in range(steps): newloc = self.location + self.freedoms[direction] self.trail.append([direction,steps]) if self.penstate == 1: self.drawpath(self.location,newloc) self.location = newloc Here we have an example of "object composition": the turtle objects have die objects inside of them. Our Turtle also accepts manually entered instructions: the user types which direction to move in by number, with N freedoms automatically designated by 0 through (N1)  a convention students might wish to change to 1 through N by reprogramming. Encourage your students to experiment and explore by making changes in the code. def manual(self): print "Manual mode (1 to quit):" while 1: dir = input("?: ") if dir == 1: break elif not dir in range(len(self.freedoms)): print "Invalid direction: range 0"+str(len(self.freedoms)1) else: self.move(dir,1) Below we interactively define and operate a manual turtle in the
YZ plane, with the resulting mywalk.pov shown at
right.


>>> from povray import Povray >>> from coords import Vector >>> from turtles import Turtle >>> import functions >>> mywalk = Povray("mywalk.pov") >>> z = Vector((0,0,1)) >>> y = Vector((0,1,0)) >>> freedoms = [z,z,y,y] >>> oturt=Turtle(freedoms,mywalk) >>> functions.xyzaxes(mywalk,2) >>> mywalk.cylradius = 0.04 >>> mywalk.cylcolor = "Magenta" >>> oturt.manual() Manual mode (1 to quit): ?: 0 ?: 2 ?: 1 ?: 1 ?: 3 ?: 3 ?: 0 ?: 0 ?: 1 >>> mywalk.close() 

Another species of turtle is able to trace out much more complicated paths based on only a few lines in a formal symbolic code known as an Lsystem. The Lsystem turtle or Lturtle comes with an instruction set of about 30 singleletter commands  some of which cause the turtle to reorient itself at random. Substitution rules combine these commands into longer and longer strings, spelling out every twist and turn in a complicated, yet repetitious, journey. 

The fractal tree at right was produced using Python + Povray from the coded Lsystem instructions below. # An LSystem file 9 # recursive depth 45 # turn angle 10 # thickness as a % +(90)c(2)AB # Axiom A = [F[+FCA][FCA]] # Rule B = [F[^FCB][&FCB]] # Rule C = '(0.7071) # Rule @ 
This curriculum was among the first to take significant advantage of R. Buckminster Fuller's philosophical explorations to advance its goals. Oregon Curriculum Network goals include:


Fuller's approach centers around polyhedra organized in a concentric
hierarchy within a uniform sphere packing  the same
cuboctahedrallyconformed sphere packing studied by Johannes Kepler
(15711630), William Barlow (18451934) and many others. Within this hierarchy, the tetrahedron, formed by four intertangent unitradius spheres, is assigned a volume of unity, and thereby becomes the standard "measuring cup" to which all other volumes are referenced. The hierarchy includes many structural relationships familiar to geometers, including the jitterbug transformation, mentioned in earlier sections 1 and 2. 
cuboctahedrallyconformed uniform sphere packing 
This unitvolume tetrahedron convention has some significant, streamlining advantages and is well worth sharing with your students. >>> tetra = shapes.Tetra() # edge=sphere diameter >>> octa = shapes.Octa() # same edges >>> cubocta = shapes.Cubocta() # same edges >>> tetra.volume() # tetra has unit volume 1.0 >>> octa.volume() # has a whole number volume 4.0 >>> cubocta.volume() # ditto 20.0 >>> shapes.Icosa().volume() 18.5122958682 # ... but not the icosa 
concentric hierarchy around a single lattice sphere 
Our approach is also backwardcompatible with more conventional ones. By analogy, if you learn Python, a relatively new computer language, this does not entail your unlearning BASIC or C. One interesting consequence of using this alternative measuring cup is that any tetrahedron with lattice point vertices will have a whole number volume. We can test this claim programmatically in Python, using our new Turtle objects. Robert Gray has also provided a formal, deductive proof. Set four Turtle objects at the origin and define their degrees of freedom to be the 12 vectors to neighboring sphere centers in the lattice. 
Allow all four turtles to wander randomly for N hops  they will usually end up further away from one another, although of course it's possible for two turtles to land on the same vertex (meaning we would not get a tetrahedron), or for all four to end up on the same plane (likewise meaning no volume). In nondegenerate cases (where tetrahedra are actually formed  though rarely regular ones), we compute their volumes using the six edge lengths as inputs. The result is always a whole number, remembering that a 1x1x1 tetrahedron, with six spherediameter edges, is unity by definition. 
Here's some code for generating random tetrahedra using four turtles free to wander in a sphere packing lattice: def randtet(canvas): # 12 degrees of freedom (to corners of cubocta) freedoms = turtles.ivmrays() v = [] # list to receive vertices tlist = [0,0,0,0] # list to receive turtles # initialize four turtles for i in range(4): tlist[i] = turtles.Turtle(freedoms,canvas) tlist[i].penup() # don't show walks # let each take six steps for t in tlist: t.randomwalk(6) v.append(t.location) # append a vector # use the four randomly derived vertices # to define a tetrahedron otetra = shapes.Tetra(v[0],v[1],v[2],v[3]) # get the volume vol = otetra.volume() # discard volumes < 1 if vol<1: rtnval = "Degenerate" else: rtnval = vol if canvas: # draw the tetrahedron otetra.drawself(canvas) # print tetrahedron's volume print vol # return tetrahedron object return otetra Usage: >>> myfile = povray.Povray("randomtet.pov") >>> for i in range(6): rand.randtet(myfile) # draws, prints volumes 40.0 4.0 13.0 9.0 28.0 6.0 >>> myfile.close() 
Another interesting fact is that the respective perpendiculars to the four faces of any tetrahedron, with lengths proportional to facial areas, cancel out. The sumnormals function accepts a random tetrahedron as input and performs the necessary crossproduct computations  the result should always be zero. >>> mytet = rand.randtet() 18.0 >>> rand.sumnormals(mytet) 0.0 This essay was designed to suggest a number of branch points to connected topics, some more explored than others. You of course have a lot of disgression in how you might want to fit these threads into a curriculum of your own. From this discussion of random walks constrained by degrees of freedom, you might want to explore the topic of quadrays, a game with nonhyperdimensional 4tuple vectors based on the 4 freedoms of the tetrahedron (see section 2). Following this fork in the road will bring you back to many points already visited in this essay, plus may encourage your students learn to think more generically about data structures and operations. Or you might want to jump to the topic of spherical coordinates at this juncture, for many of the same reasons i.e. to show how the same position information might be encoded in alternative formats or data structures. You'll find the coords.py module includes subclasses of the Vector class, Svector and Qvector, which accept arguments in either spherical or quadray formats respectively. In all other respects, these additional subclasses of vector behave just like their parent class and may be combined with one another in vector operations. >>> import shapes >>> from coords import * >>> v1 = Qvector((1,0,0,0)) # vectors to 4 corners of a reg tetrahedron >>> v2 = Qvector((0,1,0,0)) >>> v3 = Qvector((0,0,1,0)) >>> v4 = Qvector((0,0,0,1)) >>> otetra = shapes.Tetra(v1,v2,v3,v4) # create the shape >>> otetra.volume() # get its volume 1.0 >>> v1.angle(v2) # central angle of a regular tetrahedron 109.47122 >>> v4.spherical() # r = quadray length relative to sphere diameter (0.612372435696, 125.264389683, 45.0) >>> v3 = Svector(v4.spherical()) # define Svector pointing oppositely >>> v3.angle(v4) # confirm angle between them is 180 degrees 180.0 >>> v5=v3+v4 # add Svector and Qvector (oppositely oriented) >>> v5.xyz # check xyz coordinates of resulting vector (0.0, 5.55111512313e017, 0.0) For further reading:
