A probabilistic representation of a string $x \in \{0,1\}^n$ is given by the code of a randomized algorithm that outputs $x$ with high probability [Oliveira, ICALP 2019]. We employ probabilistic representations to establish the first unconditional Coding Theorem in time-bounded Kolmogorov complexity. More precisely, we show that if a distribution ensemble $\mathcal{D}_m$ can be uniformly sampled in time $T(m)$ and generates a string $x \in \{0,1\}^*$ with probability at least $\delta$, then $x$ admits a time-bounded probabilistic representation of complexity $O(\log(1/\delta) + \log (T) + \log(m))$. Under mild assumptions, a representation of this form can be computed from $x$ and the code of the sampler in time polynomial in $n = |x|$.

We derive consequences of this result relevant to the study of data compression, pseudodeterministic algorithms, time hierarchies for sampling distributions, and complexity lower bounds. In particular, we describe an instance-based search-to-decision reduction for Levin's Kt complexity [Levin, Information and Control 1984] and its probabilistic analogue rKt [Oliveira, ICALP 2019]. As a consequence, if a string $x$ admits a succinct time-bounded representation, then a near-optimal representation can be generated from $x$ with high probability in polynomial time. This partially addresses in a time-bounded setting a question from [Levin, Information and Control 1984] on the efficiency of computing an optimal encoding of a string.