  A central task in many applications is reasoning about processes that change
over continuous time. Continuous-Time Bayesian Networks is a general compact
representation language for multi-component continuous-time processes. However,
exact inference in such processes is exponential in the number of components,
and thus infeasible for most models of interest. Here we develop a novel Gibbs
sampling procedure for multi-component processes. This procedure iteratively
samples a trajectory for one of the components given the remaining ones. We
show how to perform exact sampling that adapts to the natural time scale of the
sampled process. Moreover, we show that this sampling procedure naturally
exploits the structure of the network to reduce the computational cost of each
step. This procedure is the first that can provide asymptotically unbiased
approximation in such processes.
