random.md

Randomized algorithms and probabilistic data structures

Table of contents

• Probability theory
• Random numbers generation
• Distributions
  • Uniform distribution
  • Normal distribution
    • Marsaglia polar method
• Sampling
  • Selection sampling
  • Reservoir sampling
• Shuffling
  • Fisher–Yates algorithm
• Probabilistic data structures
  • Skip lists
• HyperLogLog

---

Probability theory

🎥

• E.Lawrence. Why use measure theory for probability? Part I, Part II, Part III (2012)

---

Random numbers generation

For cryptographically secure random number generation see Random numbers generation – Cryptographic algorithms and data structures.

🔗

• M.Marini. A class hierarchy for random number generation – C/C++ Users Journal 14 (1996)

⚓

• Xorshift – Wikipedia

---

Distributions

Uniform distribution

• D.Lemire. Nearly divisionless random integer generation on various systems (2019)

⚓

• std::uniform_int_distribution – C++ reference
• std::uniform_real_distribution – C++ reference

Normal distribution

⚓

• std::normal_distribution – C++ reference

Marsaglia polar method

This method is used in some implementations (e.g., in libstdc++ and MSVC STL) of std::normal_distribution.

⚓

• Marsaglia polar method – Wikipedia

---

Sampling

📖

• Sec. 3.4.2: Random sampling and shuffling – D.E.Knuth. The art of computer programming. Vol. 2: Seminumerical algorithms (1997)
• Col. 12: A sample problem – J.Bentley. Programming pearls (1999)

Selection sampling

🔗

• Knuth’s algorithm S – Rosetta Code
• B.Rieck. A technique for selection sampling (sampling without replacement)

📄

• J.S.Vitter. An efficient algorithm for sequential random sampling – ACM Transactions on Mathematical Software 13, 58 (1987)

Reservoir sampling

🔗

• Reservoir sampling – Wikipedia

🎥

• N.Ormrod. Fantastic algorithms and where to find them: Reservoir sampling – CppCon (2017)

---

Shuffling

🔗

• J.Atwood. The danger of naïveté (2007)

📖

• Sec. 3.4.2: Random sampling and shuffling – D.E.Knuth. The art of computer programming. Vol. 2: Seminumerical algorithms (1997)

Fisher–Yates algorithm

🔗

• Fisher–Yates shuffle – Wikipedia
• Knuth shuffle – Rosetta Code

---

Probabilistic data structures

Skip lists

❔

• How does a skip list work? – Software Engineering

🎥

• Randomization: Skip lists – MIT OCW 6.046J/18.410J: Design and analysis of algorithms (2015)

📖

• Sec. 3.4: Skip lists – Drozdek A. Data structures and algorithms in C++ – Cengage Learning (2012)

📄

• W.Pugh. A skip list cookbook – Tech. Rep. UMIACS-TR-89-72.1 (1990)

---

HyperLogLog

🔗

• HyperLogLog – Wikipedia

🎥

• N.Ormrod. Fantastic algorithms and where to find them: HyperLogLog – CppCon (2017)