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) |

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

(5) |

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) |

(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.
- start with and ;
- 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) |

(10) |

(11) |

(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) |

which is the desired answer.

If the process is to be stopped at some scale , i.e. if one would like to remain with a fraction of events where nothing happens at all, this is easy to include in the veto algorithm: just iterate upwards in at usual, but stop the process if no allowed branching is found before .

Usually is a function also of additional variables . The methods of the preceding section are easy to generalize if one can find a suitable function with . The used in the veto algorithm is the integral of over . Each time a has been selected also an is picked, according to , and the point is accepted with probability .