Probability theory, independence, interchangeability, Martingales

What Hacker News says

1. NY_EntrepreneurJul 2011
   "Can you please suggest on-line resource to learn great beginning and advanced probability concepts?"

   Yup! The subject at the level you ask is a major topic in applied math but is not very popular in US universities. So, you will not get many good answers. In particular, the 'computer science' community, with 'machine learning' and 'artificial' this, Bayesian that, likely won't have good answers.

   Your "on-line" part is asking a bit much; I can give you references to books but not all on-line. There may be some PDF files on-line, from TeX, that have such material; try some Google searching with the keywords used here.

   The intuitive foundations of probability went back to gambling.

   'Probability' is a field of 'applied' math and as such is well defined:

   About 100 years ago, E. Borel student H. Lebesgue invented 'measure theory' which essentially 'rewrote' classic calculus, especially the part about integration. For the simple cases, what Lebesgue did gets the same numerical values as the classic Riemann integral. The difference is that in theoretical work Lebesgue's integral is much more general and much better 'behaved'.

   But 'measure theory' has to do with, intuitively, 'length', 'area', 'volume' and various generalizations of these. Well, in probability, for probability P and event A, the 'probability' of A is P(A) and is a number in [0,1] and acts much like the 'area' of A. The connection is so close that, in the end, we have to accept that the foundations of probability are measure theory.

   Then

   A. N. Kolmogorov, 'Foundations of the Theory of Probability, Second English Edition', Chelsea Publishing Company, New York, 1956. English translation of the original German '"Grundbegriffe der Wahrscheinlichkeitrechnung,"' 'Ergebnisse Der Mathematik', 1933.

   applied Lebesgue's work to make probability a solid field of math. Since then Kolmogorov's foundations have been nearly the only one taken seriously in any 'modern' or 'advanced' work in probability, stochastic processes, or mathematical statistics.

   A good start on a good text in stochastic processes was:

   J. L. Doob, 'Stochastic Processes', John Wiley and Sons, New York, 1953.

   Doob was long at University of Illinois. One of his students was P. Halmos who was later an assistant to von Neumann at the Institute for Advanced Study and in about 1942 wrote the first version of the still standard:

   Paul R. Halmos, 'Finite-Dimensional Vector Spaces, Second Edition', D. Van Nostrand Company, Inc., Princeton, New Jersey, 1958.

   Later he wrote:

   Paul R. Halmos, 'Measure Theory', D. Van Nostrand Company, Inc., Princeton, NJ, 1950.

   with at the end a NICE introduction to probability and stochastic processes based on measure theory.

   Likely the first rock solid, quite comprehensive, highly polished presentation of 'modern' probability was the first edition of:

   M. Loeve, 'Probability Theory, I and II, 4th Edition', Springer-Verlag, New York, 1977.

   Loeve was long at Berkeley. One of his students did:

   Jacques Neveu, 'Mathematical Foundations of the Calculus of Probability', Holden-Day, San Francisco, 1965.

   and another did:

   Leo Breiman, 'Probability', ISBN 0-89871-296-3, SIAM, Philadelphia, 1992.

   Either of these two can be regarded as a more succinct presentation of the more important material in Loeve. Breiman is the more 'practical' and 'accessible'; Neveu is a crown jewel of elegance and succinctness but not always easy to read.

   Other good presentations of much the same material include:

   Kai Lai Chung, 'A Course in Probability Theory, Second Edition', ISBN 0-12-174650-X, Academic Press, New York, 1974.

   and

   Yuan Shih Chow and Henry Teicher, 'Probability Theory: Independence, Interchangeability, Martingales', ISBN 0-387-90331-3, Springer-Verlag, New York, 1978.

   In total, those texts nail down 'probability' at all four corners and make it a rock solid topic in applied math. Good knowledge of, say, Breiman is a necessary and sufficient condition for knowing 'probability' at a serious level, that is, without being watered down for 'general audiences'.

   For more, proceed with stochastic processes, stochastic optimal control, mathematical statistics, etc.

   For learning probability, minimal prerequisites (more would be helpful) would be abstract algebra, linear algebra, 'analysis', measure theory, and functional analysis.

   For abstract algebra, there are many texts. Sufficient is

   I. N. Herstein, 'Topics in Algebra', Blaisdell, New York, 1964.

   but can consider S. Lang, etc.

   For linear algebra, there are many texts, but the old:

   Paul R. Halmos, 'Finite-Dimensional Vector Spaces, Second Edition', D. Van Nostrand Company, Inc., Princeton, New Jersey, 1958.

   remains a good 'second' text. It is also an introduction to functional analysis.

   The main text for 'analysis' is just:

   Walter Rudin, 'Principles of Mathematical Analysis', McGraw-Hill, New York.

   in whatever is the latest edition.

   Can skip the material on exterior algebra or just get it from the original source, now in English:

   Henri Cartan, 'Differential Forms', ISBN 0-486-45010-4, Dover, Mineola, NY, 2006.

   For measure theory and functional analysis, the standards are:

   H. L. Royden, 'Real Analysis: Second Edition', Macmillan, New York.

   and the first (real) half of:

   Walter Rudin, 'Real and Complex Analysis', ISBN 07-054232-5, McGraw-Hill, New York.

   Actually, Loeve also covers much of this material. Neveu slips in quite a lot.

   Then you will be ready for Breiman, Neveu, Chung, Chow and Teicher, or Loeve.

   You will discover:

   The start of probability theory is a 'probability space'. For that, there are three parts, (1) the 'sample space', (2) the 'events', and (3) the 'probability measure'.

   The 'sample space' is just a set of points; to support any reasonably serious work in probability, the sample space has to be uncountably infinite. In all our work, we do some one 'trial', and that corresponds to some one point in the sample space. The other points in the sample space are what 'might' have been our trial.

   An 'event' is a set of trials. We ask that the collection of all events have some 'closure' properties to make that collection a 'sigma algebra'. So, briefly, the collection of events has as one event the whole sample space and is closed under relative complements and countable unions.

   In terms of measure theory, the sample space and the sigma algebra of events form a 'measurable space'. A 'probability measure' is just a positive measure with total 'mass' 1. Thank you Lebesgue and measure theory.

   On the reals R, we can take the open sets and, then, the Borel sets, that is, the smallest sigma algebra that contains the open sets. A 'random variable' is a function from the probability space to the reals that is 'measurable', that is, the inverse image of a Borel set is an event.

   As an alternative, we can ask that the inverse image of the Lebesgue measurable sets of R be events.

   If X is such a random variable, then its 'expectation' E[X] is just the Lebesgue ('abstract') integral of X over the probability space. For E[X] to exist, we need only that X be measurable and that the integral of both the positive and the negative parts of X not be infinite (we don't want to subtract one infinity from another). E.g., Lebesgue integration is very 'general': All we need is measurability and not subtract one infinity from another.

   By a change of variable, we can also write the expectation as a Lebesgue integral over the real line with respect to the 'distribution' of X on R. Or, X 'induces' a probability measure on R.

   We can discuss convergence of random variables -- in distribution, probability, mean square, and almost surely.

   Then we can define independence for events, sigma algebras, and random variables. E.g., with this approach, if X and Y are independent random variables and f and g are functions, then f(X) and g(Y) are independent random variables. Don't try to prove this the elementary way!

   With independent random variables, we can cover the classic limit theorems -- central limit theorem, weak and strong laws of large numbers, and the law of the iterated logarithm.

   Using the Radon-Nikodym theorem of measure theory, for random variables X and Y we can define their 'conditional expectation' E[Y|X].

   With such 'conditioning' we can discuss Markov processes, martingales, and the martingale convergence theorem.

   We can also move on to ergodic theory and, say, Poincare recurrence (keep stirring the coffee and the cream will separate back, close to where it was when it was poured in).

   Those are the previews of coming attractions.

   Note: This material is not very popular in US universities.

   Show morethread
2. NY_USA_HackerMar 2011
   I looked through Downey's book.

   (A) Definition of Probability.

   As far as I could tell, the book defined probability in only one of two ways:

   (1) Relative frequency assuming finitely many trials (page 13) and

   (2) Bayesian prior intuitive belief (page 52).

   No, here the book is doing readers a disservice.

   (B) Exponential Distribution

   The 'derivation' of the exponential distribution on page 37:

   "I’ll start with the exponential distribution because it is easy to work with. In the real world, exponential distributions come up when we look at a series of events and measure the times between events, which are called inter-arrival times. If the events are equally likely to occur at any time, the distribution of inter-arrival times tends to look like an exponential distribution."

   is a bit too vague.

   (C) Random.

   The book also uses 'random' too frequently, loosely, and unnecessarily. Instead, essentially we can just drop the word 'random' and avoid questions about what 'random' means and if some data is 'truly random'.

   For (A), essentially universally in advanced work, there is only one approach:

   We have a non-empty set of 'trials'. Then an 'event' is a subset of the set of all trials. The set of all trials is an also an event. The set of all events is closed under countable unions and relative complements. In particular, the empty set is an event.

   A 'probability' is a function P from the set of all events to the interval [0,1]. For an event A, P(A) is its probability. The probability of the set of all trials is 1.

   P is 'countably additive': For countably infinitely many pair-wise disjoint events A_i, for i = 1, 2, ..., the probability of the the union of the A_i is the sum of the P(A_i).

   A 'random variable' X is a function from the set of all trials to the real numbers such that for any real number x the set of all trials w such that X(w) <= x is an event. Usually we suppress the notation of the trials and just write the event X <= x. This is our only use of 'random', and we give no more definition of it.

   In practice, essentially any number at all that we observe can be regarded as a random variable. In particular, the number might have been something observed about a person. The statement on page (52) that

   "Anything involving people is pretty much off the table."

   would be a silly foundation for probability.

   For Bayesian and prior beliefs, can regard such a belief as an estimate of a conditional probability where we condition on what we know. E.g., we know a lot about people so that given a person, we can guess that with probability over 99% the person is less than 10 feet tall. This point does not mean that we have a 'Bayesian' foundation for probability. It's better just to drop mention of 'Bayesian'.

   The 'distribution' of a random variable X is the function F_X(x) = P(X <= x).

   Full details are in any of, say,

   Jacques Neveu, 'Mathematical Foundations of the Calculus of Probability', Holden-Day.

   Leo Breiman, 'Probability', ISBN 0-89871-296-3, SIAM.

   M. Loeve, 'Probability Theory, I and II, 4th Edition', Springer-Verlag.

   Kai Lai Chung, 'A Course in Probability Theory, Second Edition', ISBN 0-12-174650-X, Academic Press.

   Yuan Shih Chow and Henry Teicher, 'Probability Theory: Independence, Interchangeability, Martingales', ISBN 0-387-90331-3, Springer-Verlag.

   Essentially what is going on is that we are defining P as a non-negative real 'measure' with 'total mass 1' as in any of:

   Paul R. Halmos, 'Measure Theory', D. Van Nostrand Company, Inc.

   H. L. Royden, 'Real Analysis: Second Edition', Macmillan.

   Walter Rudin, 'Real and Complex Analysis', ISBN 07-054232-5, McGraw-Hill.

   This approach to probability is the one used in essentially all advanced work, e.g.,

   Ioannis Karatzas and Steven E. Shreve, 'Brownian Motion and Stochastic Calculus, Second Edition', ISBN 0-387-97655-8.

   Jean-Rene Barra, 'Mathematical Basis of Statistics', ISBN 0-12-079240-0, Academic Press.

   Early in Neveu can see some ways we get essentially pushed into this foundation for probability.

   With this approach, for a random variable X, we define its expectation E[X] as just its integral with respect to measure P in the sense of measure theory. Then essentially by a routine 'change of variable' we can get E[X] as an integral in terms of the distribution F_X and the measure it defines on the reals.

   With this approach, if, say, for some positive integer n we measure the height of n people, then we say that we have the values of the n random variables

   X_1, X_2, ..., X_n

   and do not say that we have the values of n trials of one random variable X.

   Indeed, with this approach, all our experience, all of the universe, is only one trial.

   Given a set of events, we can define what it means for the set to be 'independent'. And we can proceed similarly for random variables.

   Then we can give a more careful statement of the central limit theorem and also state the law of large numbers. We can also say why we use an average to estimate an expectation, e.g., as in

   Paul R. Halmos, "The Theory of Unbiased Estimation", 'Annals of Mathematical Statistics', Volume 17, Number 1, pages 34-43, 1946.

   On page 12 there is:

   "The mean of this sample is 100 pounds, but if I told you 'The average pumpkin in my garden is 100 pounds,' that would be wrong, or at least misleading. In this example, there is no meaningful average because there is no typical pumpkin."

   No: An 'average' does not have to be 'typical' to be 'meaningful'. The expectation of the weight X of a pumpkin in the garden remains meaningful. And the law of large numbers will still apply.

   For the exponential distribution, there is a good 'qualitative' derivation: If we have arrivals where the inter-arrival times are stationary and independent, then the inter-arrival times are independent and have the same exponential distribution. Good details are early in the chapter on Poisson processes in

   Erhan Cinlar, 'Introduction to Stochastic Processes', ISBN 0-13-498089-1, Prentice-Hall.

   Downey's book places a lot of emphasis on distributions, e.g., Weibull, and descriptions, e.g., skewness. So an implication is, given some data, we should try to find its distribution and various summary properties of it, but usually this is unpromising. It is good to have the concept of a distribution but, given some data, usually not good to try to find its distribution. Instead, we get our results by manipulating the data in ways where we need to know little or nothing about the distribution.

   The strong emphasis on hypothesis testing is curious. There is more in:

   E. L. Lehmann, 'Testing Statistical Hypotheses', John Wiley and Sons.

   E. L. Lehmann, 'Nonparametrics: Statistical Methods Based on Ranks', ISBN 0-8162-4994-6.

   Downey's book mentioned the chi-square distribution: The main point is that if X_1, X_2, ..., X_k are random variables with Gaussian distribution with mean 0 and variance 1, then

   Y = X_1^2 + X_2^2 + ... + X_k^2

   has chi-squared distribution with k degrees of freedom.

   Downey's book mentioned the variance of a finite population; while variance is of high interest, the variance of a finite population is not. What is usually wanted is an estimate of variance, and for that the formula in the book should be dividing by n - 1 instead of n; this change yields an 'unbiased' estimate.

   It would be good for students to get at least an intuitive understanding of the most powerful hypothesis testing via the Neyman-Pearson result: Using an analogy from real estate investing, regard the false alarm rate as money to be spent and spend the money to get the best return on investment buy buying the property with the highest ROI first, then the one with the second highest, etc. Yes, in principal this process leads to a knapsack problem which is NP-complete. Likely the nicest proof of the Neyman-Pearson result is from the Hahn decomposition; this follows from the Radon-Nikodym result with a famous proof by von Neumann in Rudin.

   The mention of 'resampling' is curious: There are cases where we won't have independent random variables but will have 'exchangeable' random variables, and exchangeability can be enough.

   One example is extending nonparametric tests to multidimensional data and using it for anomaly detection in server farms and networks where multidimensional data is ubiquitous, e.g.,

   N. B. Waite, "A Real-Time System-Adapted Anomaly Detector", 'Information Sciences', volume 115, April, 1999, pages 221-259.

   Show morethread