It would help if there were some definitions for "random" and "pattern-free" in this context. I find it annoying that he several times says that random music is not pattern-free.
1. He never plays the same note twice. (A Costas array is a permutation) In a random piece, the same note can (and probably will) appear more than once.
2. If he plays middle A, then middle B (consecutive notes), he'll never play consecutive notes (e.g. C_0 and D_0) again.
3. If he plays middle A, then something else, then middle B, he'll never play consecutive notes spaced by another note again.
4. If he plays middle A, then two other notes, then middle B, he'll never play consecutive notes spaced by two other notes again.
5. etc.
6. The same applies to pairs of notes two notes apart (e.g. middle A and middle C), three notes apart, etc.
7. Finally, he uses a Golomb ruler for the spacing between notes. I'm note quite sure what he did there, but possibly each spacing is unique. Can someone else explain? At any rate, a Golomb ruler defines unique gaps such that you get every possible gap between some pair of marks on it. (Think of a 4 cm ruler with 0 cm, 1 cm, 2 cm and 4 cm marked on it. You don't need a mark at 3 cm because you can get that from the gap between the 1 cm mark and the 4 cam mark.)
It is true that their definitions are not equivalent, but it seems that he is implying that you cannot generate "pattern-free" music using randomly played notes, and that -depending of the definition of "pattern-free" of course- seems very, very unlikely.
Can't is note quite true, but won't is more like it. Consider 3.14159265358979323 - the first 18 digits of pie. Random digits? Maybe (randomness, as you note, needs to be defined). However, look at triplets: 141, 535, 979, 323. Played as music, people will hear repetitions like that. Or at least, that seems to be the theory; I have no ear for these things to test it. Maybe you can hear them?
Random != no pattern
You might create a tune with no pattern but chances are there will be a pattern of some kind in there.
Exactly. This is why sports fans think that there's such a thing as form. Human beings are very bad at judging randomness - we actually bias towards alternating patterns, which is decidedly non-random.
On the eighth day, God created FORTRAN.