Appendix A

Calculating Collision Probabilities

Introduction

A fundamental feature of a simulator modelling moving objects must obviously be how it handles collisions and interactions. And in order to do this, it must first of all determine whether a collision has occurred between a pair of objects.

The normal, and most straightforward way, of handling this problem is to simply simulate the movement of the objects, and calculate mathematically whether they overlap. If they do overlap, a collision has occurred.

Unfortunately, this is not entirely practical at the nanoscale. The difficulty lies in the fact that particles are not moving in straight lines, rather they are following a Brownian motion random-walk that are approximated as a Gaussian probability distribution. The scale of the simulation could be altered to the level where the particles were (effectively) moving in straight lines, but this would involve modelling the objects in picoseconds and picometres, which is unsustainable. Such modelling is already done, and quite widely, but is many orders of magnitude too slow for examining the interactions of large groups of macro-molecules.

The approach taken here is to calculate the odds of the particles colliding, and then to randomly determine whether or not they did collide. Determining the odds of collision turns out to be a challenging task.

Defining the Problem

The problem fundamentally is "With two spheres of given radius, with given standard deviations of movement, at a certain separation distance, what is the probability that they will collide within a specified time interval?".

This can be simplified to some extent. Consider two spheres A and B, with radii R_A and R_B, moving with RMS displacements per cycle of _A and _B , at a separation distance d apart. Firstly, the standard deviations of movement can be combined ⁽¹⁾ to = (_A² + _B²)^½ , so that it is possible to treat one sphere as stationary, while the other sphere moves with RMS displacement .

Secondly, the radii can be adjusted, so that we can treat the problem as that of a single sphere, with a single standard deviation of movement, "colliding" with a point at the given distance. Since, in order to collide, the centres of the two spheres must approach to within R_A + R_B, the problem can be simplified to that of a single sphere, of radius R = R_A + R_B, colliding with a moving point (with radius zero).

This reduces the problem to only three variables; the combined radii R, the combined RMS displacements , and the separation distance d between the sphere surface and the point. If we divide d and R by we can obtain R' and d', scale-independent measures of radii and distance, measured in terms of the standard deviation of displacement.

The problem can now be stated as "What is the probability that a sphere of radius R', will collide with a point at a position d' before time T"?

Analytical solutions

Even with these simplifications though, the problem still remains difficult to solve analytically. To find the collision probability at time T, a number of solutions might be tried:

A naive solution, of integrating the intersection of the Gaussian movement function with the region of (potential) intersection, fails because this would only give the probability of the point being within the bounds of the sphere at the instant t=T. The analytical formulation of this is in any case quite difficult to solve.

A more elaborate analytical solution, that of integrating the Gaussian movement function over time t=0 to t=T, and summing the above formula for the intersection of point and sphere, also fails. This would merely compute what proportion of time, on average, the point would spend inside the sphere. Since this formula does not take account of actual collision, but merely the time spent with the target point inside the sphere, this would be a misleading answer.

It is possible that a true analytical solution could be found by integrating the dependent probability tree (by integrating over time t the function describing "given probability(n) that a collision has not occurred prior to time t, what is the probability of a collision in the next instant"). However the approach seemed sufficiently intractable as to merit a numerical approach.

A numerical solution

For the simulator's purposes it is necessary to know a range of sphere sizes and a range of interaction distances. Firstly the standard deviation of movement, and the time scale, were set to unity. This makes it possible to model all situations, since different time periods simply lead to different standard deviations, and all standard deviations can be reduced to unity by simply scaling the sphere size and interaction distance appropriately.)

With Brownian motion, the moving object tends to meander a great deal on its path, frequently backtracking, and jumping from side to side. An example of the Brownian motion of a particle with a step size of standard deviation 0.1 is shown in figure A.2:

One of the difficulties in simulating a system like this is in deciding what level of detail to use. As shown in figure A.2 above, the motion is quite erratic, especially as each of the small, linear paths represented in the image is actually another small random walk. Figure A.3 shows the same particle's path, but at a resolution of 10,000 steps, each with a distance of 0.01 standard deviations.

As these graphs show, Brownian motion is fractal in nature - the path becomes more and more convoluted as the scale is reduced. In reality, when considering the trajectories of molecules, the paths really do become almost straight lines at the picometer scale (some curvature may caused, especially in liquids, due to inter-molecular forces), but this is well below the level of the simulation. In order to make sure this collision simulation program is accurate enough, a step size must be picked that is small compared to the radius of the spheres being tested.

To simulate the problem domain, a series of tests were run. Since the problem was scalable, everything was measured in arbitrary size units. The standard deviation of the test point's movement was set to be 1 unit, which also sets the basic scale of the simulation - everything can now be measured either in "standard units" or equivalently in multiples of "one standard deviation".

The test was run for spheres sized 0.1 to 10 standard units in radius, and these were tested against interaction distances from 0 to 10 standard units in size. (As expected, and as is shown below, there were negligible interactions past about two standard deviations, or two "standard units", in distance.)

In all, 100,000 iterations (i.e. 100,000 different test points and spheres were used to test each radius and distance combination) for 20 different distances and 40 different sphere sizes. To simulate the "random walk" of the particle, rather than moving in one step of standard deviation 1, each sphere was moved in 10,000 steps of standard deviation .01, for the reasons explained above. This step size was chosen so that the resultant standard deviation of .01 units would be substantially smaller than the smallest radius tested, which was 0.1 units in size.

Despite the large number of individual steps (10,000 steps of standard deviation 0.01 units) the eventual standard deviation is the same (1 unit), and the step size is sufficiently smaller than the smallest radius tested, and thus accurately simulates the random walk nature of the particle's movement. The graphical results are presented below, with distance 1 equalling 1 unit (which is also 1 standard deviation), and sphere radius 1 that is likewise 1 unit (or 1 standard deviation) in size:

As can be seen in figure A.4, the function is, unsurprisingly, concentrated about large spheres and small distances. Slightly clearer are the same figures, presented in figure A.5 as a graph of probability against the log of distance and sphere size.

How these figures are used

These numbers are used in the program whenever two objects come sufficiently close to each other (usually within three movement standard deviations or less) that they might possibly collide within the next time step. The probabilities above, scaled appropriately, are referred to via a lookup table, and a randomiser is used to determine whether a collision did, in fact, occur with the indicated probability.

The use of a lookup table ensures that, although computing the figures initially took some time (on the order of five hours), the speed of the program is unimpaired, since the time for finding the appropriate collision probability in the pre-calculated table is very small, and constant.

Raw Figures

The raw data produced by the collision simulator are presented on the next two pages. The tables give the probability of collision, tabulated against the inter-sphere distances (across the top, measured in combined standard deviations of movement ), and the combined radii of the spheres, (also measured in standard deviations of movement ). (See page A.2 for a fuller explanation of the measurements used.)

Because the figures are derived from a probabilistic simulation, there is some inaccuracy. It must be remembered that each figure represents a trial of only 100,000 tests. This can be seen especially in the smaller numbers (i.e. at greater distances, or for smaller radii).

This can also be seen in the limiting case where the point and the sphere start at zero distance. In this case, it is theoretically certain (P = 1.0) that the point, moving in a Brownian manner, will collide with the sphere. Due to the discrete nature of the simulation though, this is only approximated in the results (see the "Distance Between Spheres" column for distance = 0 overleaf) which range from 0.447 for the smallest sphere with radius 0.0125 , to 0.996 for the largest, at 100 ).

This result for the tiny sphere (0.0125 ) is not surprising, since the "step size" of the Brownian motion was only 0.01 . More accurate figures could be obtained by simply decreasing the step size; however in practice it is unlikely (and undesirable) that simulation objects will be moving, on average, 100 times their size! Conversely, the figures (for this limiting case only) are within 5% of the theoretical limit once the sphere size is within about 1/8 of the RMS movement .

Collision Probabilities 1:

This page covers inter-sphere distances from 0.1 to 1 standard deviations.

Distance Between Spheres

Collision Probabilities 2:

This page covers inter-sphere distances from 1 to 10 standard deviations. (The '1' column is repeated for clarity):

Distance Between Spheres

Conclusion

While an analytic solution would be desirable, in its absence the probabilities of collision of objects have been obtained by simply simulating a sphere and a randomly moving test point many thousands of times.

The results of this simulation have been incorporated into a data file which the modelling program reads when it starts running, allowing it to quickly determine the probability of collision for any pair of objects being simulated.

1. This is a well known lemma; e.g. Bhattacharyya, G.K. & Johnson, R.A, (1977) Statistical Concepts and Methods, John Wiley & Sons, pp 202