Title: Counting and Uniform Generation of Worldlines

Speaker: Iris Reinbacher
HKUST

Date: Friday, Feb 16, 2007
Time 11-12PM
Venue: Room 3464, HKUST

  
Abstract:
A worldline is the path of a particle in space-time. The properties of a 
many-particle system are determined by the probability distribution of 
the worldlines of all particles. This distribution can be determined for 
example by Quantum Monte Carlo methods. In this talk algorithms are presented 
to uniformly generate a fixed number of k worldlines on a discrete space time 
lattice when the worldlines are restricted to hop to adjacent sites at a 
predefined set of places. First, all possibilities for k-tuples of worldlines 
are counted, and then this knowledge is used to uniformly generate one of the 
k-tuples.

For two dimensional spacetime, a dynamic programming approach to count 
k worldlines in O(2^k n^{k+1}}is presented. Then, knowing all possibilities, 
it takes only linear time to generate any k-tuple of worldlines, uniformly distributed.

A slight modification of the counting algorithm allows to compute the number of 
worldlines which use a specific number of hops. The presented algorithms also work 
in higher dimensional spacetime without modifications.