Next: The Random Number Generator Up: Monte Carlo Techniques Previous: Selection From a Distribution   Contents

## The Veto Algorithm

The radioactive decay' type of problems is very common, in particular in parton showers, but it is also used, e.g. in the multiple interactions description in PYTHIA. In this kind of problems there is one variable , which may be thought of as giving a kind of time axis along which different events are ordered. The probability that something will happen' (a nucleus decay, a parton branch) at time is described by a function , which is non-negative in the range of values to be studied. However, this naïve probability is modified by the additional requirement that something can only happen at time if it did not happen at earlier times . (The original nucleus cannot decay once again if it already did decay; possibly the decay products may decay in their turn, but that is another question.)

The probability that nothing has happened by time is expressed by the function and the differential probability that something happens at time by . The basic equation then is

 (4)

For simplicity, we shall assume that the process starts at time , with .

The above equation can be solved easily if one notes that :

 (5)

and thus
 (6)

With this is nothing but the textbook formulae for radioactive decay. In particular, at small times the correct decay probability, , agrees well with the input one, , since the exponential factor is close to unity there. At larger , the exponential gives a dampening which ensures that the integral of never can exceed unity, even if the integral of does. The exponential can be seen as the probability that nothing happens between the original time 0 and the final time . In the parton-shower language, this corresponds to the so-called Sudakov form factor.

If has a primitive function with a known inverse, it is easy to select values correctly:

 (7)

which has the solution
 (8)

If is not sufficiently nice, one may again try to find a better function , with for all . However to use method 3 with this would not work, since the method would not correctly take into account the effects of the exponential term in . Instead one may use the so-called veto algorithm:

24.
25.
add 1 to and select , i.e. according to , but with the constraint that ,
26.
compare a (new) with the ratio ; if , then return to point 2 for a new try;
27.
otherwise is retained as final answer.

It may not be apparent why this works. Consider, however, the various ways in which one can select a specific time . The probability that the first try works, , i.e. that no intermediate values need be rejected, is given by

 (9)

where the exponential times comes from eq. () applied to , and the ratio is the probability that is accepted. Now consider the case where one intermediate time is rejected and is only accepted in the second step. This gives
 (10)

where the first exponential times gives the probability that is first selected, the square brackets the probability that is subsequently rejected, the following piece the probability that is selected when starting from , and the final factor that is retained. The whole is to be integrated over all possible intermediate times . The exponentials together give an integral over the range from 0 to , just as in , and the factor for the final step being accepted is also the same, so therefore one finds that
 (11)

This generalizes. In one has to consider two intermediate times, , and so
 (12)

The last equality is most easily seen if one also considers the alternative region , where the rôles of and have just been interchanged, and the integral therefore has the same value as in the region considered. Adding the two regions, however, the integrals over and decouple, and become equal. In general, for , the intermediate times can be ordered in different ways. Therefore the total probability to accept , in any step, is
 (13)