Algorithmic information theory with stochastic algorithms?
One possible direction is looking at the (computational) hardness of distributions. For example, a family of distributions $\{\mathcal{P}_n\}_{n\in\mathbb{N}}$ where $\mathcal{P}_n$ is a distribution over $\{0,1\}^n$ is called polynomialy-samplable (you can substitute here any other type of time/space restriction) if there exists a probabilistic polynomial time algorithm $A$ such that $A(1^n)\sim \mathcal{P}_n$. Your white noise example translates in this case to the uniform distribution being easy (samplable). These notion often arise  in average case complexity, where one cares about the average hardness of computing a function relative to some backgroud distribution over the inputs. A straightforward generalization of this would be to restrict the distance (total variation/KL) between $A(1^n)$ and $\mathcal{P}_n$.
In any case, whenever one is interested in computational hardness, you would probably have to introduce a family of objects rather than talk about the complexity of a specific member.