True and pseudo random numbers
True random number generators (T-RNG) observe random physical processes 真随机数发生器（T-RNG）观察随机物理过程：
- often involves quantum effects: radioactive decay, electrical/thermal noise etc. 通常涉及量子效应：放射性衰减，电/热噪声等
- costly and slow 代价高昂，速度慢
- mostly used in cryptography that requires a high level of security 主要用于需要高度安全性的密码学
Pseudo random number generators (P-RNG) are computer software that
伪随机数发生器（P-RNG）是计算机软件：
- produce number sequence that only appears to be random 产生看起来随机的序列
- cheap and fast 便宜又快捷
- can be initialized (seeded) to different states 可以被初始化（播种）到不同的状态
- states can be stored and recovered, convenient for MC 状态可以存储和恢复，方便MC
Pseudo random number generators 伪随机数生成器
- Building good P-RNG requires highly specialized skills:
- must pass rigorous statistical tests 必须通过严格的统计测试
- numerical scientists have devoted their careers to build good P-RNGs
- always use a good P-RNG libarary and never write your own
使用一个好的P-RNG libarary并且永远不要自己写一个 - random() in Excel is implemented incorrectly, don't use it for anything serious
在Excel中的random执行是不正确的，不要严重使用它
Mersenne Twister (MT19937)
The most popular P-RNG:
- often the default P-RNG for MC ：the default choice of Python's
numpy.random.uniform - very long cycle of 2^ 19937 − 1 and execellent statistical properties
- suitable for MC applications, but not good for cryptography
- very fast: ~100M random numbers per second on a modern PC
Non-uniform random numbers
Box-muller
Normal random number is the most important of all:
- most quant Finance models are driven by Brownian motions
- fast and accurate inversion of normal CDF weren't known till recently
Box-muller is a classic method to transform independent uniform RNs to independent normal RNs:
- takes 2 independent uniforms and produce 2 independent normals
把两个独立的 - its polar form is faster and more stable, which is behind Python's
numpy.random.normal - the polar form is a rejection algorithm: the number of output normal RNs is less than the input uniforms
- about 21% of input uniforms are rejected (wasted)
Normal inversion
Numerical inversion of normal CDF is an effective alternative to genrate normal random numbers:
- fast and accurate numerical inversion of the normal CDF were discovered recently
- based on polynomial approximation, accuracy is ~$10^{-9}$
- every uniform RN produce a normal RN output, more convenient than the polar Box-muller
- works well with low discrepency sequences (next lecture)
Normal inversion is often preferred over the Box-muller.
