Actually, in many works of probability theory/stochastic process, there is no explicit definition of randomness. Maybe because we think we can deduce the definition easily.


But in Kolmogorov complexity,randomness is defined strictly.


Now, my question is: could we have a formal definition of randomness in probability theory/stochastic process which is consist with our intuition of it in probability theory/stochastic process, and is it identified with one in Kolmogorov complexity?



Randomness defined in Kolmogorov complexity is identified with one in probability theory/stochastic process?
I would say the corresponding quantity for measuring randomness would be a quantity of information content, so typically Shannon entropy rate, i.e.,
$$
H(X)=\lim\_{n\rightarrow \infty}\frac{1}{n}H(X\_1,\ldots,X\_n)
$$
where the expectation for the entropy is taken over the joint pdf $\mathbb{P}(X\_1,\ldots,X\_n)$.


Sequences from a source with low entropy rates are easier to predict, and compress. There are very close links with Kolmogorov complexity and entropy rate as explained in Cover and Thomas' book.


For instance, if $K(X\_1,\ldots,X\_n|n)$ is the conditional Kolmogorov complexity of the random sequence $(X\_1,\ldots,X\_n)$ then
$$
\lim\_{n\rightarrow \infty} E\left[ \frac{1}{n} K(X\_1,\ldots,X\_n|n) \right ]
= H(X),
$$
and if $(X\_1,\ldots,X\_n)$ is i.i.d., unbiased, then for all $n,$
$$
\mathbb{P}\{K(X\_1^n|n)<n-k\} < 2^{-k},
$$
so we can call an infinite string incompressible if
$$
\lim\_{n\rightarrow \infty} \frac{ K(x\_1 x\_2 \cdots x\_n|n)}{n} = 1.
$$


