This course is the only one in the Computer Science Department which explores the use of probability and statistics to obtain efficient solutions of very large, often intractable, problems.
Students are expected to have a good knowledge of calculus and linear algebra, and some basic familiarity with probability, as well as programming. We proceed from first principles. The students will program simple illustrations of the techniques described.
| TOPICS | LECTURES | HOW MANY | |
|---|---|---|---|
| 1. | Sets and Boolean Algebra. | Lecture 1. | 1 |
| Introduction. Propositional Calculus. Truth Tables. Sets. Boolean Operations and Algebra. | |||
| Limiting Operations on Sets. Sigma-Algebras. Generated Sigma-Algebras. | |||
| 2. | Set-Functions, Measures, and Probability. | Lecture 2. | 1 |
| Set-Functions, Additivity. Sub-Additivity. Measures. | |||
| Events. Probability. Probability Spaces. | |||
| 3. | Random Variables and Distributions. | Lectures 3-4. | 2 |
| Topology. Open Sets. Inverse Images and Their Algebra. Inverse Images of Sigma-Algebras. Borel Sets. Lebesgue Sets. Complete Probability Spaces. | |||
| Random Variables (r.v.) Statistical Distributions. Cumulative Distribution Functions (c.d.f.) | |||
| Selected Special Distributions. | |||
| 4. | Conditional Probability and Independence. | Lectures 5-6. | 2 |
| Conditional Probability and Distributions. Bayes' Theorem. Joint Multivariate Distributions. Cartesian Product Spaces. | |||
| Statistical Independence. Independent Random Variables. Bernoulli (Repeated Independent) Trials. | |||
| The Borel-Cantelli Lemmas. | |||
| 5. | Moments and Limiting Distributions. | Lectures 7-8. | 2 |
| The Lebesgue Integral. Simple Functions and Integrable Functions. Mathematical Expectations (Statistical Mean Values). Higher Moments and Central Moments; Variances and Covariances. Chebyshev's Inequality. | |||
| Expectations and Higher Moments of Selected Special Distributions. Limiting Distributions. | |||
| 6. | Laws of Large Numbers. | Lectures 9-10. | 2 |
| Convergence of Sequences of Random Variables. | |||
| Convergence in Probability. The Weak Law of Large Numbers. | |||
| Almost Sure (Probability One) Convergence. The (Kolmogorov) Strong Law of Large Numbers. | |||
| Convergence in Mean, and in Quadratic Mean. | |||
| The Central Limit Theorem. | |||
| 7. | Sample Statistics. | Lecture 11. | 1 |
| The Sample Mean. Sample Variances and Covariances. Efficient Computation Thereof. Regression and Correlation Coefficients. | |||
| 8. | The Monte Carlo Method. | Lectures 12-13. | 2 |
| Introduction and Elementary Definition. History. Range of Applications. | |||
| Primary and Secondary Estimators. Random Generators. Canonical Random Generators. True, Pseudo-, and Quasi-Random Generators. | |||
| Random Sequences in Separable Frechet Spaces. The Levy-Halton Theorems. | |||
| Formal Definitions of Monte Carlo Processes and Monte Carlo Procedures. | |||
| 9. | Variance-Reduction Technique for Evaluating Sums and Integrals. | Lectures 14-16. | 3 |
| Easy Functions. Correlated (Control Variate) Sampling. Importance Sampling. The Comparison Theorem. | |||
| Stratified (Systematic) Sampling. The Problem of Signed Probabilties. Weighted Uniform Sampling. | |||
| Antithetic Variates (Hammersley-Morton, Halton-Handscomb, Laurent Methods). | |||
| Implicit Multicorrelated Sampling (E-Z-H: Ermakov-Zolotukhin-Handscomb Method). Conditional Monte Carlo. | |||
| 10. | Techniques for Solving Linear Equations. | Lectures 17-18. | 2 |
| Algebraic Systems. Infinite Systems. Integral and Differential Equations. Functionals. Inconsistent and Overdetermined Systems. Least-Squares (Gaussian) Solution. Neumann Series Solution. Estimating Eigenvalues. | |||
| General Monte Carlo Approach. Limit Theorems. Random Walks. Single-Term (von Neumann-Ulam) and Series (Wasow-Curtiss) Estimators. Convergence Criteria and Variance Estimates. | |||
| 11. | Sequential Monte Carlo. | Lecture 19. | 1 |
| Three Techniques. Convergence Criteria and Estimates. | |||
| 12. | Applications of Monte Carlo Techniques. | Lecture 20. | 1 |
| Radiation Shielding. Criticality and Chain-Reaction Studies of Nuclear Fission Weapons and Reactors. Intranuclear Cascades. Atomic Wave-Functions and Energy Levels. Thermodynamics of Gas Models; Quantum-Mechanical Systems; Ferromagnets. Long-Chain Polymerization (Self-Avoiding Walk). Simulated Annealing (for PC Board and VLSI Chip Layout, etc.). Chemical Reaction Kinetics. Wiener and Feynman Integrals. Development of Statistical Tests. Cell Population Studies. Combinatorial Problems. Operations Research and System Analysis Problems (Simulation). | |||
| 13. | Random Generators: Statistical Approach. | Lectures 21-22. | 2 |
| General, Canonical, and Discrete Canonical Random Generators. Generation of Arbitrarily Distributed Random Sequences, Using a Canonical Generator. Special Methods: the Direct Method; the Rejection Technique; the Composition Method. | |||
| 14. | Pseudo-Random Generators. | Lectures 23-24. | 2 |
| Middle-Square Method. Multiplicative Congruential (Power-Residue, Multiply!) Method. Linear (Mixed) Congruential Method. Higher-Order Linear Methods. Other Methods. Analysis of Periodicity. Behavior in Multi-Dimensional Space. Statistical Tests. Philosophical Considerations. | |||
| 15. | Quasi-Random Generators; | ||
| Quasi-Monte Carlo Method. | Lectures 25-27. | 3 | |
| QMC Methods Viewed as Quadrature Formulae. Functions of Bounded Variation (in the Sense of Hardy-Krause). Discrepancy. Koksma-Hlawka Inequality. | |||
| Low-Discrepancy Sequences (van der Corput; Halton; Sobol'; Faure) and Point-Sets (Nets) (Roth; Hammersley; Faure). Niederreiter Sequences and Nets. Good Lattice Points. |