True and pseudo random numbers
True random number generators (T-RNG) observe random physical processes 真隨機(jī)數(shù)發(fā)生器（T-RNG）觀察隨機(jī)物理過(guò)程：
- often involves quantum effects: radioactive decay, electrical/thermal noise etc. 通常涉及量子效應(yīng)：放射性衰減吃型，電/熱噪聲等
- costly and slow 代價(jià)高昂策添，速度慢
- mostly used in cryptography that requires a high level of security 主要用于需要高度安全性的密碼學(xué)
Pseudo random number generators (P-RNG) are computer software that
偽隨機(jī)數(shù)發(fā)生器（P-RNG）是計(jì)算機(jī)軟件：
- produce number sequence that only appears to be random 產(chǎn)生看起來(lái)隨機(jī)的序列
- cheap and fast 便宜又快捷
- can be initialized (seeded) to different states 可以被初始化（播種）到不同的狀態(tài)
- states can be stored and recovered, convenient for MC 狀態(tài)可以存儲(chǔ)和恢復(fù)，方便MC
Pseudo random number generators 偽隨機(jī)數(shù)生成器
- Building good P-RNG requires highly specialized skills:
- must pass rigorous statistical tests 必須通過(guò)嚴(yán)格的統(tǒng)計(jì)測(cè)試
- numerical scientists have devoted their careers to build good P-RNGs
- always use a good P-RNG libarary and never write your own
使用一個(gè)好的P-RNG libarary并且永遠(yuǎn)不要自己寫(xiě)一個(gè) - random() in Excel is implemented incorrectly, don't use it for anything serious
在Excel中的random執(zhí)行是不正確的拥知，不要嚴(yán)重使用它
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
把兩個(gè)獨(dú)立的 - 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.
