"15-251 Great Theoretical Ideas in Computer Science"
You mean there really are some? I always thought it was the empty set!
Okay, I followed the URL to see these wondrous ideas!
So, I saw some 'lecture notes' at:
http://server251.theory.cs.cmu.edu/twiki/bin/view/Main/Proba...
and there saw:
"Random Variables
We begin with the notion of a finite probability distribution D, which consists of a finite set S of elements, or samples, where each x in S has a weight, or probability, p(x) in [0,1]."
Sorry, guys. They blew it. That sentence is without a doubt the most mixed up, confused, uninformed, misinformed, just plain wrong mess I've ever seen in what purports to be some important mathematics. We're talking total upchuck here. Don't read that garbage.
(1)
"finite probability distribution"
Likely what he means is a discrete distribution.
(2)
"distribution D, which consists of a finite set S of elements, or samples"
Total nonsense. A "distribution" does NOT consist "of a finite set".
The rest is also nonsense.
He wants to discuss random variables but gets off on distributions far too soon.
Here is a much better way to proceed:
Suppose we perform an experiment and measure some number X. If we do the experiment again, then the number we get for X might be different. We call X a 'real random variable'.
For a real number x, we can consider the probability that X <= x. We write this probability as P(X <= x). We also write as the 'cumulative distribution' of X F_X(x) = P(X <= x). [Note: Here F_X borrows from Knuth's TeX notation for F with a subscript X.]
If X takes on only finitely many values, then we might say that X and its cumulative distribution F_X are 'discrete'.
Here is a still better way to proceed: We have a non-empty set S (usually denoted by capital omega) of 'trials'. Each experiment we perform is one 'trial' and corresponds to some point s in S (usually a trial is denoted by a lower case omega).
Given a subset A of S, we call A an 'event'. We have a probability P defined on events. The 'probability' of an event A is written P(A) and is a number in [0,1].
If in our experiment we observe a number, that number is a real random variable; call it X. Then X is a function from the set of trials S to the set of real numbers R. So, X: S --> R.
Then for a real number x, there is the event
{s | s is in S and X(s) <= x}
with shorthand notation {X <= x}. That is, we usually suppress mention of a trial s.
Then the probability that X <= x is written
F_X(x) = P(X <= x)
and is the 'cumulative distribution' of X.
For more details, we ask that the set of all events includes S and is closed under complements and countable unions. Usually the set of all events is denoted by script upper case F.
And we ask that for disjoints events A(i), i = 1, 2, ..., the probability of the union of the A(i) is the sum of P(A(i)). That is, we ask that P be 'countably additive'.
Suppose X is a real random variable with cumulative distribution F_X, and suppose for some positive integer n and i = 1, 2, ..., n Y(i) is a real random variable. Suppose the set
{Y(i) | i = 1, 2, ..., n}
is independent. And suppose for each i, the cumulative distribution of Y(i) is F_X. Then we can regard
{Y(i) | i = 1, 2, ..., n}
as a 'sample' of size n from cumulative distribution F_X.
Full details are in each of:
M. Loève, 'Probability Theory, I and II, 4th Edition', Springer-Verlag, New York.
Jacques Neveu, 'Mathematical Foundations of the Calculus of Probability', Holden-Day, San Francisco.
Leo Breiman, 'Probability', ISBN 0-89871-296-3, SIAM, Philadelphia.
Kai Lai Chung, 'A Course in Probability Theory, Second Edition', ISBN 0-12-174650-X, Academic Press, New York.
Loève was long at Berkeley, and Neveu and Breiman were among his students. Neveu has long been in Paris, and Breiman has long been at Berkeley. Chung has long been at Stanford. Other experts in such math include Avellaneda at Courant, Bertsekas at MIT, Çinlar at Princeton, Dynkin at Cornell, Karatzas at Columbia, Karr at UNC, Shiryaev at Moscow, Shreve at CMU, Wierman at Johns Hopkins, among others.
This disaster illustrates an important lesson: Computer science is out of gas, that is, doesn't know what to do next. It really has only one promising way out now, and that way is to 'mathematize' the field. So, the progress needs to be essentially applied math. For this progress, computer science needs to know some appropriate math. Basically each person trying to do such work needs a good undergraduate major in pure math together with some selected graduate work in pure and applied math. However, only a tiny fraction of professors of computer science have these prerequisites. Thus their work that needs math is often upchuck as in the example here although usually not quite this bad.
Net, anyone who wants to make progress in computer science should f'get about current academic computer science, study math, and then attack problems in computing as an applied mathematician. Bluntly, the alternative is just upchuck as here. Sorry 'bout that.
Any student trying to learn some topics in math in a computer science department is likely wasting time and money and filling in much needed gaps in his knowledge. To learn math, go to a math department. To learn probability, start with one of the books and/or professors above or equivalents.