  A very computationally-efficient Monte-Carlo algorithm for the calculation of
Dempster-Shafer belief is described. If Bel is the combination using Dempster's
Rule of belief functions Bel, ..., Bel,7, then, for subset b of the frame C),
Bel(b) can be calculated in time linear in 1(31 and m (given that the weight of
conflict is bounded). The algorithm can also be used to improve the complexity
of the Shenoy-Shafer algorithms on Markov trees, and be generalised to
calculate Dempster-Shafer Belief over other logics.
