  We give the first non-trivial fully dynamic probabilistic tree embedding
algorithm for weighted graphs undergoing edge insertions and deletions. We
obtain a trade-off between amortized update time and expected stretch against
an oblivious adversary. At the two extremes of this trade-off, we can maintain
a tree of expected stretch $ O (\log^4 n) $ with update time $ m^{1/2 + o(1)} $
or a tree of expected stretch $ n^{o(1)} $ with update time $ n^{o(1)} $ (for
edge weights polynomial in $ n $). A guarantee of the latter type has so far
only been known for maintaining tree embeddings with average (instead of
expected) stretch [Chechik/Zhang, SODA '20].
  Our main result has direct implications to fully dynamic approximate distance
oracles and fully dynamic buy-at-bulk network design. For dynamic distance
oracles, our result is the first to break the $ O (\sqrt{m}) $ update-time
barrier. For buy-at-bulk network design, a problem which also in the static
setting heavily relies on probabilistic tree embeddings, we give the first
non-trivial dynamic algorithm. As probabilistic tree embeddings are an
important tool in static approximation algorithms, further applications of our
result in dynamic approximation algorithms are conceivable.
  From a technical perspective, we obtain our main result by first designing a
decremental algorithm for probabilistic low-diameter decompositions via a
careful combination of Bartal's ball-growing approach [FOCS '96] with the
pruning framework of Chechik and Zhang [SODA '20]. We then extend this to a
fully dynamic algorithm by enriching a well-known 'decremental to fully
dynamic' reduction with a new bootstrapping idea to recursively employ a fully
dynamic algorithm instead of a static one in this reduction.
