The minimum probability of error achievable by random codes on the arb
itrarily varying channel (AVC) is investigated. New exponential error
bounds are found and applied to the AVC with and without input and sta
te constraints. Also considered is a simple subclass of random codes,
called randomly modulated codes, in which encoding and decoding operat
ions are separate from code randomization. A universal coding theorem
is proved which shows the existence of randomly modulated codes that a
chieve the same error bounds as ''fully'' random codes for ail AVC's.