Randomness is a necessary but not sufficient condition for a game to be considered procedural. A completely random game such as Solitaire or Poker is not usually considered procedural, however Minesweeper is arguably procedurally generated, and on closer examination has many of the elements of procedural content.
Equally, a multi-player game has at least one random element (the opposing player) but multi-player games are generally not considered procedural in nature.
Andrew Doull has suggested that biased randomness is more important than randomness in defining a PCG game, in particular that a key element of PCG games is discovering an underlying set of rules that are partially concealed by random noise.
Sources of Randomness
The most common source of randomness in a PCG game is a pseudorandom number generator. This has the advantage of allowing dynamic-world-generation using random seed and is relatively simple to program once the random number generator is written.
A completely deterministic system can still have at least two sources of randomness. A large percentage of dynamic systems are sufficient chaotic that they are effectively random in the long term. Chaos theory shows that slight variations in initial game conditions can result in wildly varying game states in the long term.
The player can be the other form of entropy in the game. Halo uses a completely deterministic AI system that still appears to behave randomly based on the player actions.
External Links
Randomness - Wikipedia article on Randomness.
Chaos theory - Wikipedia article on Chaos theory.
Randomness: Blight or Bane? - Article on randomness by Greg Costikyan.
Minesweeper vs. Solitaire - Article on Ascii Dreams.
