ある数列$a_n$がある。
これがランダムな数列でないことを証明するには規則性があるかどうかを示せばよい。
ではランダムであることを証明するにはどうすればよいか？
規則性がないことを示せばよい。
規則性がないことを示すためには、ありとあらゆる規則性がある数列に一致しないことを示せばよい。
しかし、これは非常に難しい。
「ない」ことを証明するということは、規則性があるすべての数列を知らなければ行えないからだ。
そして、規則性がある数列（※）というのはおそらく無限に等しいくらいあると思われる。
そんな状態で、ひとつひとつそれらの数列と比較して一致していないかを調べるのは事実上不可能であり、ある程度妥協して、多分ランダムかな～。程度の証明くらいしかできないだろう。
というわけで、タイトルの通り、ランダムであることを証明することは難しいという話でした。
※例えば、自然数の平方根であり、かつ正の無理数である数を小さい順に並べてできる数列の小数第1000000000位の数を項に持つ数列$a_n$があるとする。
$a_n$は規則性があるが、それを（何も知らない状態から）示すのは相当困難だろう。