8 ms·

Foundations of probability theory

94 points by websec 11y ago

amelius 11y ago
I have a question that might be related to the topic. I have found that often, when solving problems related to probability theory, it is more convenient to think in terms of combinations than to think in terms of probabilities (perhaps because I'm a programmer). Would it be possible to devise a programming language that allows me to program a filter that selects the desired outcomes out of the complete set of combinations, and to have the compiler automatically deduce a closed-form formula for the probability (without enumeration)? If this is not possible in general, what would the restrictions on this programming language be, to make it work in practice? So for example, given the question what the probability is that, when throwing 4 coins, 2 of which will be heads; I could write a function that generates all possible outcomes "TTTT", "TTTH", etc. And I could write a filter function that returns true for "TTHH", "THTH", "THHT", etc.
- jerf 11y ago
  You might find this interesting: http://blog.plover.com/prog/haskell/probmonad.html http://blog.plover.com/prog/haskell/probmonad.html Doesn't produce "closed-form formula", but, well, those tend to scale to programming-sized tasks poorly anyhow.
- dragandj 11y ago
  This is possible, and in fact probably implemented in some probabilistic programming languages, but I think you are looking at the wrong direction. The point is that even for fairly simple real use cases, the computation complexity is so huge, that all computers in the world couldn't compute it in your lifetime if you don't employ some approximation or optimization and stick to naive algorithms. So, that is what the whole field of machine learning is about: finding some clever ways to deal with random variables in a computationally feasible way...
  - foobar2020 11y ago
    All those probabilistic programming languages will become exponentially faster once we have feasible quantum computers, since BPP \in BQP. We currently use a weaker inclusion, BPP \in PSPACE, as the core execution model.
    - j2kun 11y ago
      Check your facts, because this is simply not true.
- gizmo686 11y ago
  Most introductory books on probability I have seen open with the combinatorical approach you describe. When it is applicable, this approach is very powerfull. However there is essentially nothing novel in combinatorical probability relative to combinatorics, so research and advanced topics in this field are done under the title of combinatorics, instead of probability. Probability becomes a field in its own right once we move beyond the cases where a combinatorical approach will work.
- eruditely 11y ago
  I think that would only work in the discrete case or for simple problems, however something relevant >“Information theory must precede probability theory and not be based on it.” A.N.Kolmogorov, in [Kolmogorov, 19831. and it was a combinatorics paper
- Double_Cast 11y ago
  I think you're looking for Pascal's Triangle. let P = probability of 2 heads given 4 coins let omega = (x + y)^n # probability space let x = 50% # P(heads) let y = 50% # P(tails) let (n, k) = (4, 2) # 4 coins, 2 heads P = (n, k)(x )^2(y )^2 (4, 2)(50%)^2(50%)^2 (6 )(25%) (25%) # (4, 2) = 6; see link (6 )(6.25%) (37.5%) https://en.wikipedia.org/wiki/Pascal%27s_triangle https://en.wikipedia.org/wiki/Pascal%27s_triangle
graycat 11y ago
Looked at the text to be used, Durrett. There's more and with higher quality in any of M. Loeve, J. Neveu, K. Chung, and L. Breiman. For what Tao wrote on his page about determinism or whatever on that page -- just f'get about that. And what he wrote, confusing a sample space and a probability space, just say that he had a bad day that day.
- nkurz 11y ago
  And what he wrote, confusing a sample space and a probability space, just say that he had a bad day that day. Could you expand on this? I'm reading his post now, but from the outside, it seems unlikely that Terry got the concepts completely wrong, and more likely that he's using slightly different definitions for the concepts than you are expecting.
  - graycat 11y ago
    No, he's just being sloppy. That can be a real pain for students trying to learn. But, be warned: A lot of people work with probability, but only a tiny fraction ever had a course in graduate probability. So, eventually have to learn to put up with, and sometimes rewrite, some of what is written that is not very precise. Here are the accepted definitions: Take a non-empty set, usually denoted by Omega, and call it the sample space or the set of trials. Take a collection of subsets of Omega, usually denoted by script F, and call it the set of events. Have at least enough subsets of Omega in the set of events script F so that script F will be a sigma algebra. So, script F has to have as an element the empty set, be closed under relative complements, and be closed under countable unions. We want all that for probability theory. We want countably infinite so that we can discuss, say, the event that a coin never or always comes up heads. We don't want uncountably infinite because it would create a big mess in the theory. Then the ordered pair (Omega, script F) is called a measurable space -- it doesn't have a measure yet but soon will. On that measurable space, define a positive measure P so that P( Omega ) = 1. Then P is a probability measure on the measurable space. A probability space is the triple ( Omega, script F, P ). Intuitively, a measure assigns to each event A in script F a non-negative real number P(A). A signed measure permits negative values. And of course at times want a measure that yields complex numbers. Measure theory is in, say, P. Halmos, Measure Theory. The back of Halmos has a really nice introduction to probability theory, the Kolmogorov three series theorem in stochastic processes, etc. For more in stochastic processes there is, of course, the classic J. Doob, Stochastic Processes. Halmos was a Doob student and then served as an assistant to von Neumann at the Institute for Advanced Study. From that he wrote Halmos, Finite Dimensional Vector Spaces, a finite dimensional introduction to Hilbert space. Later at University of Chicago Halmos worked in mathematical statistics and made the fundamental contribution to sufficient statistics. IIRC, it was at Chicago that Halmos wrote Measure Theory. Great details on measure theory and much more are in, say, H. Royden, Real Analysis and W. Rudin, Real and Complex Analysis. To narrow measure theory to probability theory, use the famous texts by the authors I listed, Loeve, .... Royden and Rudin are terrific prerequisites to Loeve, etc. Commonly the sigma algebra of events script F is the smallest sigma algebra that contains as a subset a topology, that is, a collection of open sets, on the sample space Omega. That's all standard, beginning stuff in graduate probability -- ah, the only kind should bother with anyway!
GregBuchholz 11y ago
I don't know what mathematicians think of it, but I enjoyed "Probability Theory: The Logic of Science". https://www.google.com/#q=probability+the+logic+of+science https://www.google.com/#q=probability+the+logic+of+science
- joseraul 11y ago
  Its take on probability as a way of modelling our brain is refreshing, for instance, the beginning of chapter 1: Suppose some dark night a policeman walks down a street, apparently deserted; but suddenly he hears a burglar alarm, looks across the street, and sees a jewelry store with a broken window. Then a gentleman wearing a mask comes crawling out through the broken window, carrying a bag which turns out to be full of expensive jewelry. The policeman doesn't hesitate at all in deciding that this gentleman is dishonest. But by what reasoning process does he arrive at this conclusion? Let us first take a leisurely look at the general nature of such problems. A moment's thought makes it clear that our policeman's conclusion was not a logical deduction from the evidence; for there may have been a perfectly innocent explanation for everything. It might be, for example, that this gentleman was the owner of the jewelry store and he was coming home from a masquerade party, and didn't have the key with him. But just as he walked by his store a passing truck threw a stone through the window; and he was only protecting his own property. Now while the policeman's reasoning process was not logical deduction, we will grant that it had a certain degree of validity. The evidence did not make the gentleman's dishonesty certain, but it did make it extremely plausible. This is an example of a kind of reasoning in which we haveall become more or less proficient, necessarily, long before studying mathematical theories. We are hardly able to get through one waking hour without facing some situation (e.g. will it rain or won't it?) where we do not have enough information to permit deductive reasoning; but still we must decide immediately what to do.
  - joe_the_user 11y ago
    Ah, but policeman's actual thought process might have actually been purely deductive or purely reflexive, it might only be that the probabilities justify a series of a discreet calculations.
  - 11y ago
deleted 11y ago
[deleted]
tyc2021 11y ago
The fact that Shannon entropy is still relevant in numerous modern mathematics research is amazing. Apart from minor typos that make him a "sloppy mathematician", he is a good educator based on my personal experience taking grad. courses from him. He's not the passionate high school STEM teacher type, but he offers great insights. I think which textbook he used is somewhat secondary. For courses he had taught before, he usually pick a standard text and teach based on the material he wrote in his blog post, including exercises.
- deleted 11y ago
  [deleted]
deleted 11y ago
[deleted]

94 points by websec 11y ago

I have a question that might be related to the topic. I have found that often, when solving problems related to probability theory, it is more convenient to think in terms of combinations than to think in terms of probabilities (perhaps because I'm a programmer). Would it be possible to devise a programming language that allows me to program a filter that selects the desired outcomes out of the complete set of combinations, and to have the compiler automatically deduce a closed-form formula for the probability (without enumeration)? If this is not possible in general, what would the restrictions on this programming language be, to make it work in practice? So for example, given the question what the probability is that, when throwing 4 coins, 2 of which will be heads; I could write a function that generates all possible outcomes "TTTT", "TTTH", etc. And I could write a filter function that returns true for "TTHH", "THTH", "THHT", etc.

jerf 11y ago
You might find this interesting: http://blog.plover.com/prog/haskell/probmonad.html http://blog.plover.com/prog/haskell/probmonad.html Doesn't produce "closed-form formula", but, well, those tend to scale to programming-sized tasks poorly anyhow.
dragandj 11y ago
This is possible, and in fact probably implemented in some probabilistic programming languages, but I think you are looking at the wrong direction. The point is that even for fairly simple real use cases, the computation complexity is so huge, that all computers in the world couldn't compute it in your lifetime if you don't employ some approximation or optimization and stick to naive algorithms. So, that is what the whole field of machine learning is about: finding some clever ways to deal with random variables in a computationally feasible way...
- foobar2020 11y ago
  All those probabilistic programming languages will become exponentially faster once we have feasible quantum computers, since BPP \in BQP. We currently use a weaker inclusion, BPP \in PSPACE, as the core execution model.
  - j2kun 11y ago
    Check your facts, because this is simply not true.
gizmo686 11y ago
Most introductory books on probability I have seen open with the combinatorical approach you describe. When it is applicable, this approach is very powerfull. However there is essentially nothing novel in combinatorical probability relative to combinatorics, so research and advanced topics in this field are done under the title of combinatorics, instead of probability. Probability becomes a field in its own right once we move beyond the cases where a combinatorical approach will work.
eruditely 11y ago
I think that would only work in the discrete case or for simple problems, however something relevant >“Information theory must precede probability theory and not be based on it.” A.N.Kolmogorov, in [Kolmogorov, 19831. and it was a combinatorics paper
Double_Cast 11y ago
I think you're looking for Pascal's Triangle. let P = probability of 2 heads given 4 coins let omega = (x + y)^n # probability space let x = 50% # P(heads) let y = 50% # P(tails) let (n, k) = (4, 2) # 4 coins, 2 heads P = (n, k)(x )^2(y )^2 (4, 2)(50%)^2(50%)^2 (6 )(25%) (25%) # (4, 2) = 6; see link (6 )(6.25%) (37.5%) https://en.wikipedia.org/wiki/Pascal%27s_triangle https://en.wikipedia.org/wiki/Pascal%27s_triangle

graycat 11y ago

Looked at the text to be used, Durrett. There's more and with higher quality in any of M. Loeve, J. Neveu, K. Chung, and L. Breiman. For what Tao wrote on his page about determinism or whatever on that page -- just f'get about that. And what he wrote, confusing a sample space and a probability space, just say that he had a bad day that day.

nkurz 11y ago
And what he wrote, confusing a sample space and a probability space, just say that he had a bad day that day. Could you expand on this? I'm reading his post now, but from the outside, it seems unlikely that Terry got the concepts completely wrong, and more likely that he's using slightly different definitions for the concepts than you are expecting.
- graycat 11y ago
  No, he's just being sloppy. That can be a real pain for students trying to learn. But, be warned: A lot of people work with probability, but only a tiny fraction ever had a course in graduate probability. So, eventually have to learn to put up with, and sometimes rewrite, some of what is written that is not very precise. Here are the accepted definitions: Take a non-empty set, usually denoted by Omega, and call it the sample space or the set of trials. Take a collection of subsets of Omega, usually denoted by script F, and call it the set of events. Have at least enough subsets of Omega in the set of events script F so that script F will be a sigma algebra. So, script F has to have as an element the empty set, be closed under relative complements, and be closed under countable unions. We want all that for probability theory. We want countably infinite so that we can discuss, say, the event that a coin never or always comes up heads. We don't want uncountably infinite because it would create a big mess in the theory. Then the ordered pair (Omega, script F) is called a measurable space -- it doesn't have a measure yet but soon will. On that measurable space, define a positive measure P so that P( Omega ) = 1. Then P is a probability measure on the measurable space. A probability space is the triple ( Omega, script F, P ). Intuitively, a measure assigns to each event A in script F a non-negative real number P(A). A signed measure permits negative values. And of course at times want a measure that yields complex numbers. Measure theory is in, say, P. Halmos, Measure Theory. The back of Halmos has a really nice introduction to probability theory, the Kolmogorov three series theorem in stochastic processes, etc. For more in stochastic processes there is, of course, the classic J. Doob, Stochastic Processes. Halmos was a Doob student and then served as an assistant to von Neumann at the Institute for Advanced Study. From that he wrote Halmos, Finite Dimensional Vector Spaces, a finite dimensional introduction to Hilbert space. Later at University of Chicago Halmos worked in mathematical statistics and made the fundamental contribution to sufficient statistics. IIRC, it was at Chicago that Halmos wrote Measure Theory. Great details on measure theory and much more are in, say, H. Royden, Real Analysis and W. Rudin, Real and Complex Analysis. To narrow measure theory to probability theory, use the famous texts by the authors I listed, Loeve, .... Royden and Rudin are terrific prerequisites to Loeve, etc. Commonly the sigma algebra of events script F is the smallest sigma algebra that contains as a subset a topology, that is, a collection of open sets, on the sample space Omega. That's all standard, beginning stuff in graduate probability -- ah, the only kind should bother with anyway!

GregBuchholz 11y ago

I don't know what mathematicians think of it, but I enjoyed "Probability Theory: The Logic of Science". https://www.google.com/#q=probability+the+logic+of+science https://www.google.com/#q=probability+the+logic+of+science

joseraul 11y ago
Its take on probability as a way of modelling our brain is refreshing, for instance, the beginning of chapter 1: Suppose some dark night a policeman walks down a street, apparently deserted; but suddenly he hears a burglar alarm, looks across the street, and sees a jewelry store with a broken window. Then a gentleman wearing a mask comes crawling out through the broken window, carrying a bag which turns out to be full of expensive jewelry. The policeman doesn't hesitate at all in deciding that this gentleman is dishonest. But by what reasoning process does he arrive at this conclusion? Let us first take a leisurely look at the general nature of such problems. A moment's thought makes it clear that our policeman's conclusion was not a logical deduction from the evidence; for there may have been a perfectly innocent explanation for everything. It might be, for example, that this gentleman was the owner of the jewelry store and he was coming home from a masquerade party, and didn't have the key with him. But just as he walked by his store a passing truck threw a stone through the window; and he was only protecting his own property. Now while the policeman's reasoning process was not logical deduction, we will grant that it had a certain degree of validity. The evidence did not make the gentleman's dishonesty certain, but it did make it extremely plausible. This is an example of a kind of reasoning in which we haveall become more or less proficient, necessarily, long before studying mathematical theories. We are hardly able to get through one waking hour without facing some situation (e.g. will it rain or won't it?) where we do not have enough information to permit deductive reasoning; but still we must decide immediately what to do.
- joe_the_user 11y ago
  Ah, but policeman's actual thought process might have actually been purely deductive or purely reflexive, it might only be that the probabilities justify a series of a discreet calculations.
- 11y ago

deleted 11y ago

[deleted]

tyc2021 11y ago

The fact that Shannon entropy is still relevant in numerous modern mathematics research is amazing. Apart from minor typos that make him a "sloppy mathematician", he is a good educator based on my personal experience taking grad. courses from him. He's not the passionate high school STEM teacher type, but he offers great insights. I think which textbook he used is somewhat secondary. For courses he had taught before, he usually pick a standard text and teach based on the material he wrote in his blog post, including exercises.

deleted 11y ago
[deleted]

deleted 11y ago

[deleted]