Random Walk Revisited

In October 1967, Tony Pritchett was asked to prepare a computer program for the automatic production of a short section of animated film at a cost of £75 and that approval from the Institute of Computer Science should be obtained by 4 December, 1967.

On 14 November 1967, a letter [A1] from David Roseveare, Schools Television Producer at the BBC, outlined the requirement for the random walk film.

Most of the work on the project was completed by March 1968 with demonstration of the completed film. Final form regarding holds in the film were finalised (for when the presenter needed to speak over the film) in March 1968.

Tony Pritchett and the Chilton Atlas Console, 2016

The production run on the London Atlas Computer to generate the output magnetic tape (destined for an SC4020 microfilm recorder) was run on 9 June 1968. The actual film was probably produced on the SC4020 at the Atlas Computer Laboratory at Chilton. It is also possible that the film was produced on the Benson-Lehner 120, a later SC4020-compatible recorder, situated at Culham.

The card deck for the Fortran program and its data still exists as does the output listing from the Atlas computer run on the London Atlas. In consequence, a good re-creation of the original program is possible. Most of the Fortran cards had printing across the top, rather faded at times but with this plus the program listing from the actual run, the Fortran program listing is quite accurate.

The data used by the program primarily consists of the coordinates of the three random walks and the final positions of a further 1000 random walks (100 cards). A large proportion of the data cards had no printing on the top so it was then necessary to read the hole punchings on the card. This can be error prone.

Each data card consisted of 10 X-values followed by 10 Y-values (each using 4 columns) giving 10 positions on the screen area.

Typical Fortran Program Card and Data Card

2. Storyboard

From the discussions with the BBC the storyboard for the short film was assembled:

3. SC4020 Programming

It is worth illustrating the difference between defining an animation using the standard animation process and that using a microfilm recorder. The Storyboard from the BBC required:

The diagram below illustrates the animation for the first two steps. Click on the cyan button:

Start of Random Walk

The holds are quite long as requested by the BBC to give the presenter time to describe the process.

A conventional animation would probably be produced by having cels for the blob, circle and cels for several intermediate states of each line for the two steps to give the impression of the line being drawn and it would be the operator of the animation stand who ensured that the cels were positioned correctly for each frame of the film.

The process on, say, the SC4020 microfilm recorder is different. A 16mm or 35 mm camera in a light proof bay has an accurate white phosphor tube below it on to which can be drawn quite short lines or character symbols. The camera shutter is open and anything drawn on the tube immediately fades away but is captured on the film. The only other control is to advance the film in the camera. So the contents of the magnetic tape that drives the microfilm recorder must contain all the instructions to generate every line or symbol on every frame of the film.

The SC4020 has an addressable space of 1023 in the X and Y directions. As its name implies it can output large volumes of text very quickly on to 35mm film as a fast alternative to a lineprinter and requiring much less storage space. Drawing lines between two points whose X and Y coordinates differ by 0 to 63 positions on the raster is provided.

In the random walk film, a line representing a step is 60 units long and so is below the maximum allowed so that each step only requires a single SC4020 instruction to draw it.

For the first line, assuming the circle is positioned at the origin, the line is from [0,0] to [58,15]. This position was chosen at random by selecting an angle theta randomly between 0 and 360 degrees and calculating the point to draw the line to as [60 × cos(theta), 60 × sin(theta)]. Unfortunately, the result has to be rounded to the nearest position on the SC4020 addressable region which is [58,15]. So the actual length of the line is 59.908!

The next problem is that to make the line appear to be drawn we need to choose a set of intermediate points between the origin and [58,15]. Suppose we choose 8 positions then we need the line to appear to be drawn from:

Two ways of drawing the intermediate lines of the step on each sub-step

One of the problems with the SC4020 was keeping the intensity of long and short vectors the same. So the decision here is between executing more SC4020 instructions with the hope of better matches of intensities over the number of instructions generated. In one case only a single line is drawn per frame and in the other 4 on average. Tony made the decision to keep the length of vectors the same and accept the need for more instructions generated. It was probably the correct decision to make.

How realistic the line drawing looks obviously depends on the time between line segments being added and the length of the lines. Quite long lines are shown in the following diagram. For the three early steps, the segments are added every 8 frames (about 0.33secs per segment) while the following steps are drawn every 3 frames (nearer 0.1sec).

Times between line segments being added.

4. SCFOR Routines

Paul Nelson's SCFOR system was the standard way of accessing both the Culham BL 120 and the Chilton SC4020 microfilm recorders from Harwell, Rutherford Laboratory, Atlas Computer Laboratory, London University and universities in general. The program for the BBC Random Walk is no different being a mixture of subroutines to solve the random walk problems and SCFOR to give the best access to the two microfilm recorders.

There is nothing very remarkable about the routines used apart from the problem of outputting many identical frames of film efficiently and the handling of standard backgrounds behind content that would change frame by frame.

The subroutines SAVEA and SAVEB provide the option of generating the SC4020 instructions for some specific background and using it many times later via the USEIT subroutine.

The problem was recognised in the SC4020/BL120 hardware where the contents of a frame of output could be output on the next frame and following frames. The feature is obviously of value for holds. The ADVREP instruction allowed the SC4020 to advance the film, rewind the magnetic tape to the previous advance film command, and read the tape again to output the same information on the next frame. In theory, up to 64 frame holds could be executed.

One drawback was that the continued rewinding and rereading the same piece of magnetic tape just wore the tape out. So the high numbers of advance repeat were constrained to ensure the magnetic tapes lasted longer ;-)

The random walk program takes a midway position saving the set of instructions that generated a hold frame and repeated it, say, 16 times within the saved instructions. Then re-outputting the code a few times via USEIT so that a long hold consisted of a number of short advance repeats one after the other.

At the Atlas Computer Laboratory, the problem arrived sufficiently often that it was possible to switch between the ADVREP subroutine either using the SC4020 instruction or instead substituting a SAVE/REPEAT in software.

The blob in the sequence where 1000 blobs are displayed needs to be reasonably efficient so that instead of multiple lines being generated to create a blob a set of four over-exposed upper case letter O characters were output.

5. Random Walk Program

5.1 Introduction

From various listings, the decision was made to generate the random walks off-line and then provide the coordinates of these as data to the Random Walk program itself. This data consisted of:

This avoided the need for multiple computations of the random walks as the program was being constructed and also ensured that the output from each run was consistent in the random numbers used.

5.2 Blob

The first phase of animating the first three random walks have been discussed above but the blob itself needs some explanation. The SC4020 is quite efficient in outputting its standard text symbols. The CRT beam is extruded through a stencil that contains the outline of the symbol so a character at any position on the screen can be output efficiently.

The decision was to output a pattern of four characters of an overexposed upper case letter O carefully placed to give the impression of a filled in circle.

A blob

For this reconstruction, a filled in circle will be used as this can be generated more efficiently than the original blob and is less dependent on the font being used.

5.3 Three Random Walks

The first part of the Main program is concerned with the animation of the three random walks in some detail. It generates 1008 frames of output for the first 3 steps of the first random walk. This is primarily because of the long holds to allow the presenter to explain what was happening.

The rest of each random walk takes a further 400 frames. The only complication is that each frame drawn has to remember to draw any previous blobs denoting walk end points and all the steps already taken as well as the next one.

The three random walks are animated below. The long holds have been reduced in length.

The three random walks

On the BBC film, there is a short sequence that zooms out on the three blobs but this appears to have been done afterwards, possibly by film editing, as it does not appear in the Fortran program. An insert has been added showing how the 60-length steps of the first three random walks are now 48-length steps in the 1000 step section that follows.

5.4 Blobs Galore

The second part of the film is showing the end points of 1000 random walks that are added 50 at a time. It is quite straightforward. The blobs are no longer four letter Ohs. Instead they consist of two asterisks side by side but look quite similar. The main difference is that each blob only takes half as many instructions as the earlier blobs used on the first three random walks.

End Points of 1000 random walks

The red circle shows the starting point for all 1000 random walks. The diagram above looks very similar to Tony's actual film. There are a few minor differences almost certainly due to misreading some of the holes in the card deck but most look correct.

5.5 Histogram

The final part of the film is to show what is the value of the mean distance away from the starting point. The solution is to calculate the distances from the endpoints to the origin for each walk and divide them into classes according to their length and construct a histogram showing where the mean distance is.

The histogram is drawn as rows of blobs for each class piled on top of each other. The animation starts with the longest distance class and progresses to the class nearest the origin. The animation takes each blob and moves it from its starting point to its position in the relevant stack of blobs. This concludes the film. The subroutine that generates this part of the film is named POUR as its task is to pour the blobs into the relevant histogram stack.

The histogram can accommodate 4 blobs left to right in each of the stacks. Each stack builds up in rows of four blobs. The next row is 12 units above the previous one. So the set of 10 stacks might finish up looking something like this:

The histogram's base goes from X=485 to 965 in 10 steps of 48 and the base of the first row is Y=896, the one above Y=884 and so on in steps of 12.

A blob situated to the left and above its final position in the stack first moves to the right 16 units per frame until it is just to the left or equal to its final position. The blob then moves down 80 units per frame until it arrives as its position in the stack.

Zones used to pour blobs into the histogram

Once poured, the final positions of the blobs in the histogram are shown below.

Blobs in their final positions in the histogram

It worked pretty well and it was interesting to see that the zone got smaller so that the next zone was always to the left of the histogram so quite a bit of care had gone into its placement.

6. Conclusions

This might be one of the earliest chemistry computer animations. There were quite a few physics and astronomy ones but not too many related to molecules.

The first three random walks are quite straightforward to animate. The major problem is efficiently generating the repeat frames and long holds on an early microfilm recorder. There was a period at the Atlas Computer Laboratory around the time when this film was being generated when the Advance Repeat instruction did not work correctly. The IBM tape decks in the 1960s were not that reliable in moving backwards or forwards a number of blocks often miscalculating the number of blocks to travel. This was one of the reasons why the 16 main tape decks on the Chilton Atlas were pre-addressed Ampex ones.

Moving the 1000 blobs to positions in the histogram was an innovative piece of animation which could easily be understood by the viewer.

APPENDICES

A1. Letter to Tony Pritchett from BBC: 14 November 1967

Dear Tony,

We spoke. I promised I would send you something about the random walk calculation. The essence of the algebra is as follows:-

Diagram 
(0,0) to (x1,y1) [s1 away] to x2,y2 [s2 away from s1] etc

Sketch the first few strides of a random walk. Choose a set of perpendicular axes, x and y, arbitrarily. Using x- and y- coordinates, resolve stride no 1, into components x1 and y1, stride no.2. into x2 and: y2, and so on. The resultant of that walk, R, is:

 
R² = (x1 + x2 +... +xn)² + (y1 + y2 +... +yn)² = N²

The cross terms, such as 2 x1 x2, add up to zero in averaging over many walks, because those terms are as often negative as positive, and they range similarly from O to 2s². Similarly for the y cross terms.

Then average value of R is:

R = sqrt(N) s

The assumption is that each s step is the same distance.

The difference between this and what it is expected these particular pupils will be able to understand is that we do not expect them to take an R.M.S. average but simply an arithmetic mean. In this case, the mathematics gives about 0.8sqrt(N) instead of sqrt(N) (0.8 is approximately sqrt(2)/pi).

If you want to go into the mathematics, almost any book on statistics will take you through the work. (It is tied up with the technique for evaluating π by dropping matches at random on a piece of paper covered with parallel lines uniformly placed at a distance comparable with the length of a match. One counts the number of matches which cross lines.)

In this teaching programme we are merely concerned with giving pupils access to enough results for them to get an order-of-magnitude value for such things as molecular velocities, mean free path, etc. For this particular animation we are treating the thing as a kind of statistical experiment, and what we should aim at doing is to be able to superimpose a circle, centre the starting point for each path, and radius 8 steps, assuming 100 steps for each journey. Thanks to the computer, not to mention yourself, we should have enough results for such a circle to look convincing, i.e. a reasonable cluster of finishing points near the circumference of the circle.

In terms of distances on the screen, I suggest that you arrange the parameters so that 16 steps (the diameter of the circle to be superimposed) comes to about three-fifths of the screen height. Since we shall have the full screen height. corresponding to our screen height, I anticipate that something like 90% of the finishing points will lie on the screen. I don't know whether it is practical from your point of view to cater for points which disappear out of sight and reappear again before finishing their journey, but my guess is that we could afford to lose such molecules without affecting the final picture significantly.

I don't want to dwell too much on the precise nature of the distribution because we are only dealing with sets of equal steps, whereas a real molecule will move in a series of unequal steps, and I would hate to think how much programming time that would consume!

Yours

David Roseveare

Producer, Schools Television

A2. Random Walk Fortran Program

This program is printed out as part of the program execution so we have a confirmation that the set of data cards and the program actually run are identical.

A3. Random Walk Data

Some of the cards were out of order. Hopefully most of these have been corrected. Only some of the cards have print outs of the content across the top so the cards below require, in many cases, to examine the whole configurations on the card to ascertain the contents.

A4. Open University Spring Term: Mean Free Path

The Random Walk film was to be part of the Open University Spring Term Programme concerning Molecular Velocity, Mean Free Path and Molecular Diameter.

Before viewing, pupils should have seen the bromine diffusion experiment as a class demonstration, and should have embarked on some discussion of the main implication, i.e. that although the mean molecular speed is comparable to the speed of sound, the molecules must evidently be crowded for the diffusion in air to be so slow. It might be useful for the class to have performed the dice-throwing experiment as suggested in N.G.IV p,235.

The programme would start by going through the theory relating to the previous programme (or alternatively state the equation PV = ⅓Nmv²). If possible the Zartmann experiment would be shown on film, and pupils would be able to compare their own estimates with Zartmann's result.

The programme might then include a difficult variation of the standard bromine experiment, e.g., diffusing bromine into carbon dioxide rather than into air. Animated film now shows molecules colliding, and an individual molecule is singled out so that we can observe its random movement. The drunkard's walk is illustrated, and a computer-made film is shown in which the molecule is represented by a blob, leaving a record of its path behind it as it moves randomly with a fixed length of path between successive collisions. This is done for, say, a hundred successive steps. We next see (thanks to the computer) the result of several hundred, or perhaps a thousand, sets of a hundred steps, the result being in the form of a scatter diagram showing a concentration about a ring which will be approximately ten steps from the common starting point.

Teachers are now in a position to take the viewers through the remaining arithmetic to arrive at a value for the mean free path.

The Random Walk Revisited

Kate Sullivan, David Duce, Bob Hopgood

1. Introduction