Hacker News Reader

Comment by amelius | Hacker News Reader

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.

View on HN

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...

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.

Check your facts, because this is simply not true.

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.

You might find this interesting: 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.

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

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

Reply on news.ycombinator.com