Hacker News Reader

Comment by Muzza | Hacker News Reader

> For programmers, the most useful branch of discrete math is probability theory. ... What's probability theory, you ask? Why, it's counting. ...

That paragraph made my left eye twitch a little. Not a big mistake, perhaps, but what he calls probability theory is actually combinatorics. Probability theory is decidedly non-discrete (integration of density functions?) and involves only two integers: 0 and 1. (A joke).

Many people are introduced to combinatorics in the context of probability theory. It (combinatorics) can be used to compute various probabilities, but still. You wouldn't call trigonometry calculus just because a course in calculus might involve the derivative of sine and cosine, so don't confuse probability theory and combinatorics.

View on HN

How is probability theory decidedly non-discrete? As far as I know as long as the number of possible outcomes is discrete (and in CS applications this is the common case) the integration of density functions turns into simple summations and there is a vast body of results and research limited to just this area of probability theory.

Sigh. Maybe "decidedly" was not the correct word. Still, "if you only consider the discrete parts of probability theory, then probability theory is discrete math" is not useful.

Combinatorics deals with discrete structures, the kind encountered in programming, while probability concerns itself with determining the likelihood of a given event. The former is clearly more relevant to general programming.

Probability does use some tools from combinatorics and vice versa, but the two subjects have vastly different goals.

Yes, I understand combinatorics is different from probability theory and yes, he is somewhat mistaken in not distinguishing combinatorics from probability theory, but on the other hand the article is clearly meant to be informal, it isn't a dissertation on the division of (highly overlapping) sciences. Above all else, I find the statement from the critique above that "probability is decidedly non-discrete" wrong much more clearly then any statements from the original posting.

Similarly I find it highly questionable whether combinatorics is "clearly more relevant to general programming". In fact, what is "general programming"? Probability theory pervades all of Computer Science - from probabilistic algorithms (QuickSort), through cryptography, optimization algorithms (genetic algorithms, simulated annealing), networking (information theory, queuing theory), machine learning, the list goes on and on. For business programming, statistics (based on probablity theory) is crucial. Some of those applications include combinatorics, but I find it harder to find such a long list of applications of combinatorics being used without probability theory - it is a more specialized field.

I guess it might have been better to say there's a Venn diagram of "probability" and "discrete structures" and there's plenty of non-overlap in both directions.

But, it's important to appreciate that, even for probabilities on finite or countable sets, you get pulled into continuous math. I don't think we disagree here, but maybe some examples would be worthwhile, just for definiteness.

Expectations (means, variances) of discrete variables will be real-valued. There are continuous processes that are intimately connected to what you thought were purely discrete outcomes (e.g., the relationship between Poisson counts and exponential waiting times). There will be limiting processes of discrete structures that bring in continuous probabilities (the Binomial -> normal limit, and all its generalizations) and provide considerable insight. The Stirling formula, which is key to insight about factorials, comes from calculus.

Finally, generating functions are one of the main tools for solving the discrete summations you mention, and these are continuous, and pull you straight into complex analysis. ("Who changed the subject here? I was just trying to add some binomial coefficients and now we're talking about derivatives of analytic functions at zero?")

Or, as my edition of Concrete Mathematics says (sec 5.4): "We come now to the most important idea in this whole book, the notion of a generating function."

Reply on news.ycombinator.com