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
Random number generation for procedural generation is almost always based on algorithms that deterministically produce pseudorandom numbers, rather than being fetched from an truly random external source such as cosmic background radiation or radioactive decay.
There are two primary methods of generating pseudorandom numbers: Random number generators and random hash functions.
- Random number generators (or RNGs) produce a sequence of random numbers. Each random number is using the previous as part of its calculation, so it's not possible to get the Nth random number without first having gotten the first N-1 random numbers as well.
- Random hash functions take an input and produce a random output. The same input always produces the same output with no dependency on previous queries. Not all hash functions are well suited for procedural generation, as they may either not have sufficiently random distribution, or be unnecessarily expensive, but there are some that are very well suited.
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.
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.
Primer on Repeatable Random Numbers - Article on random number generators and random hash functions by Rune Skovbo Johansen.