Arbitrariness and randomness
Veritasium seems to think that “arbitrariness” is the same as “randomness”. Without true randomness, upon repetition, the guard will gain information on how the renumbering method was chosen, thus decreasing the prisoners’ probability of success.