  In this paper, we introduce a sketching algorithm for constructing a tensor
train representation of a probability density from its samples. Our method
deviates from the standard recursive SVD-based procedure for constructing a
tensor train. Instead, we formulate and solve a sequence of small linear
systems for the individual tensor train cores. This approach can avoid the
curse of dimensionality that threatens both the algorithmic and sample
complexities of the recovery problem. Specifically, for Markov models under
natural conditions, we prove that the tensor cores can be recovered with a
sample complexity that scales logarithmically in the dimensionality. Finally,
we illustrate the performance of the method with several numerical experiments.
