Principles of probability in one posting

Probability as normalised proportionality

Probabilities are just weights.  Normalised to sum to unity.  No negative weights are possible.  Any time you can assign some number $P(i)$ to a set of $n$ objects/events/occurrences, finite or infinite, such that $\sum_{i=1}^n  P(i)=1$.  It is a world of weights with lower bound 0 and upper bond 1.  Mathematically those probabilities don't have to mean anything.  They don't have to correspond to real world probabilities.  They just need to be a collective set of non-negative numbers which sum to 1.  That's it.  If the set of numbers have that, it is a proper probability.  How best to formally define this?  Make the objects be sets.

Sets are a useful ontology for mathematically approaching normalised proportionality

First, set your universe.  This is the set of all possible elementary (i.e. disjoint) outcomes.  In any experiment, precisely one of these elementary outcomes will occur.  So the probability of an elementary outcome occurring, but where we don't care which, is 1.  We call the superset of all these disjoint elementary outcomes the sample space, often $S$.  If we want to refer to 'impossible' then this corresponds nicely to the probability of the empty set, $P(\{\})=0$, which gives us our floor.

Core axiom of probability - union/addition of disjoint events.

The engine which drives all of the basic theorems of elementary probability theory is in effect a definition of the word disjoint in the context of probability.  

$P(\bigcup_{j=1}^{\infty}A_j) = \sum_{j=1}^{\infty} P(A_j)$.  In other words, if you want to know the combined total probability of a union of disjoint events, go ahead and just sum their individual probabilities.  So, as you can see, if we define an experiment as just the sum total of elementary outcomes (disjoint), then naturally, this full sum will result in 1.  This is the probabilistic version of 'something is bound to happen'.

Already, with this core axiom, together with the floor and ceiling statements - the statements of proportionality, namely $P(\{\})=0$ and $P(S)=1$, we can derive/define the following.  In what follows, our main trick is to see if we can define arbitrary events in ways which are disjoint.  We need to get to that point so that we can be justified in triggering the core axiom.  So we smash, smash, smash sets until we have a collection of homogeneously disjoint sets.  This allows us free reign in applying the core axiom.

Let' see how the two set theory terms, complementarity, $A^c$ and proper subset $\subseteq$ ought to work in probability.

Complementary sets $A$ and $A^c$ are already disjoint, so immediately we know that we can treat $P(A \cup A^c) $ using the core axiom, plus by definition of complementarity, $P(A \cup A^c) =1$.   This gives us $P(A) + P(A^c) =1$ and so $P(A^c) = 1 - P(A)$.    This is often a great problem solving tool since we may find it easier to find the probability of an event's complement than directly of the event itself.  A classic example is the birthday problem.

Now let's work on an inequality. If $A \subseteq B$ then $P(A) \leq P(B)$.  This is our first non-trivial case of 'smash smash smash'.  $A$ is inside $B$, which suggests that we can smash $B$ as the union of $A$ and, ...., something else.  Something disjoint to $A$.  How about $A\cup (B \cap A^c)$.  Now, $P(B)$ becomes $P(A\cup (B \cap A^c))$, and by the power of our core axiom, this is equivalent to $P(A) + P(B \cap A^c)$.  Our floor axiom tells us that no probability can be less than 0, so $P(B \cap A^c) \geq 0)$ and hence $P(B) \geq P(A)$.  This little inequality points in the direction of measure theory.

Knowing how to rank the probabilities of any given set in the probability space is a useful thing to know, but having to power to do addition is even better.  How can we generalise the core axiom to cope with sets which are not guaranteed to be disjoint?  Think of your classic two-sets-with-partial-overlaps Venn diagram.  If we want a robust calculus of probability, we need to crack this too.

In general, we just need to be more careful not to over-count the shared areas.  Here it should be clear that there is a 'smash smash smash' decomposition of the areas in this diagram into pieces which are properly disjoint.  And indeed there is.  Skipping on the details, we arrive at $P(A\cup B) = P(A) + P(B) - P(A \cap B)$.  This two case example of making sure you count each disjoint area precisely once, by adjusting, generalises to: $P(\bigcup_{i=1}^{n} A_i) $ can be represented as $\sum_i P(A_i)  - \sum_{i<j} P(A_i \cap A_j) +  \sum_{i<j<k} P(A_i \cap A_j \cap A_k) - \ldots + (-1)^{n+1}  P(A_1 \cap \ldots  A_n) $.  Think of this as the mathematical equivalent of an election monitor who is trying to ensure that each voter only votes once.

So now we have the addition of any events $A_i$ in the probability space.  Sticking with the voting analogy, we will now drop down from a level of high generality, to one where all elementary outcomes are equally probable.  Imagine an ideal socialist, hyper-democratic world with proportional representation.  As we have seen, we already have the election monitor who endures the technical validity of summation.  But in this political environment, we want each elementary outcome (voter) to cast a vote which is precisely the same weight as all other voters.  We also measure utility in the ruthlessly rational-sounding utilitarian way - namely that we decide on our political actions by asking the people, and counting their votes equally.  In this less general world, simply counting the number of votes for any given event is all we need to do, since all votes are worth the same as each other.  Once we have the counts, we can stop, since we can now create count-based probability distributions.  Here we're in the world of fair dice, well shuffled playing cards, randomly selected samples.  And for those problems, combinatorics helps.

Let's assume there's an experiment with $n$ elementary outcomes and some event $A$ can happen in $p$ of those.  then $P(A)$ can be measured as $p/n$.  

Multiplication rule - chaining experiments

Imagine you could perform an experiment with $n$ outcomes as often as you like, with precisely the same set of outcomes each time.  That is, the second performance of the experiment has no 'memory' of the first result.  Technically this property is called a Markov property.  There would be $n$ outcomes on that second experiment.  In total there would be $n \times n$ outcomes in the meta-experiment which consisted in doing the first, then doing the second.  But your second experiment might be a totally different one, with $m$ outcomes.  Nonetheless there would be $n \times m$ possible outcomes now in the new meta-experiment.

Temporal fungibility

Note that, since multiplication  is commutative, it doesn't much matter if you do experiment '2' before experiment '1' - you still get $n \times m$ outcomes.  A similar effect occurs when you're adding probabilities - since addition is commutative.  This temporal fungibility helps later on with Bayes' theorem.

Four sampling rules follow from the multiplication rule:

1.  Sampling $k$ from $n$ with replacement, selection ordering matters:  $n^k$
2.  Sampling $k$ from $n$ without replacement, selection ordering matters:  $\frac{n!}{(n-k)!}$
3.  Sampling $k$ from $n$ with replacement, selection ordering doesn't matter:  $\binom{n+k-1}{k}$
4.  Sampling $k$ from $n$ without replacement, selection ordering doesn't matter:  $\binom{n}{k}$

Mirror rule for binomial coefficient.  Picking the rejects

When the team captain picks his preferred team, he's also implicitly picking his team of rejects.  Another way of saying this is that Pascal's triangle is symmetrical.  Another way of saying it is that $\binom{n}{k} = \binom{n}{n-k}$.  Again, this is a useful trick to remember in solving combinatoric problems.

L-rule for binomial coefficient

$\sum_{j=k}^n \binom{j}{k}=\binom{n+1}{k+1}$.  Or in pictures, all numbers like the number in yellow are the sum of the set of numbers in blue.  This collection of blue and yellow numbers is approximately like an L tilted.  This provides a useful decomposition or simplification, especially in cases where we have scenarios made up of a sum of binomial coefficients.  Cases like this and the below team captain decomposition relate a sum of binomials which in effect partitions the problem space in an interesting way, with a new binomial partition.  A partition generally is a complete and disjoint subsetting  of the problem space.  Here, we imagine one property in the population is rankable (eg age) with no ties.   So there is a population of $n+1$ in total and we picked this person to be in the selection group.  The partition is as follows:  imagine you pick your selection group; find the oldest in your group, and now start asking a series of questions about where this oldest in your group ranks in the overall population.  He could be the population oldest.  If so, then we define the rest of the group as $\binom{n}{k}$.  Perhaps he's the second oldest in the population.  If he's the second oldest in the population, then, by definition, we can't have picked the oldest from the population to be in our group (since we already found and identified our own oldest in group), so we know we must have $\binom{n-1}{k}$ other ways to satisfy this condition.  Continue along this path and you end up with the L rule.

The greatest.  Binary partitions for binomial coefficient

$\binom{n+1}{k} = \binom{n}{k} + \binom{n}{k-1}$.  The story here is : one of your population has a unique persistent property.  Now you come to chose $k$ from these $n+1$.  This is the same as the partition where your pick contains the prize winner and the other partition, where it doesn't.

Two tribes - Zhu Shijie (sometimes attributed to Vandermonde)

$\binom{m+n}{k} = \sum_{j=0}^k\binom{m}{j}  \binom{n}{k-j}$.  The story: Your entire population is made up of two tribes.  You have known sub-populations of each (ie you know the proportion).  You now pick your $k$.  This is the same as first segregating the populations into 2, then picking some number $j\leq k$ of the first tribe and, using multiplication rule on the second experiment, picking $k-j$ of the second tribe.  You run this for all possible values of $j$.

Lentilky. On tap at the factory, in dwindling supply in your pocket.

Forrest Mars, after telling his dad to "stick his Mars job up his ass" because he didn't get the recognition for the invention of the Milky Way, left for Britain in 1932.  By 1937, during the Spanish civil war, he was touring Spain with George Harris of Rowntree, they saw off-duty soldiers eating Lentilky, Moravian chocolate shaped like little lenses, covered with candy to stop the chocolate from melting. That idea was created by the Kneisl family, who had a factory in Holešov, making the stuff since 1907.  Harris and Mars decided to rip the idea off, and came to a gentleman's agreement to make Smarties in the UK and M&Ms in the USA.  Imagine a tube of Lentilky.  Each tube contains from 45 to 51 chocolate candies, of which there are 8 colours.  So how many possible tubes of Lentilky are there in total.  Ignoring for a moment the practical reality of the factory guaranteeing that you get probably roughly the same number of colours in each shape, let's allow all possibilities.

Step 1 in solving this is recognising it as a combinatorics problem.  Step 2 concentrates on one of the box cardinalities - say the tube with 45 sweets.  Step 3 recognise that this is sampling of $k$ from $n$, with replacement, order unimportant, $\binom{8+45-1}{8}$.  More generally, if the number of sweets is $i$, this is $\binom{8+i-1}{i}$.  That step is particularly non-intuitive, since $n$ is so much smaller a population than $k$, which you can only do in sampling with replacement.  Given they're unordered in the tube, order doesn't matter.  Step 4 applies the mirror rule, so that $\binom{8+i-1}{i} = \binom{i+7}{i} = \binom{i+7}{7}$.  Why do that step? Well, you've simplified the expression. But $i$ ranges from 45 to 51 of course, so there's a summation going on here: $\sum_{i=45}^{51}\binom{i+7}{7}$.  Step 5 simplifies the for range: $\sum_{j=52}^{58}\binom{j}{7}$; Step 6 rearranges to get $\sum_{j=7}^{58}\binom{j}{7} - \sum_{j=7}^{52}\binom{j}{7}$.  Step 7 is to use the L-rule, equating this to $\binom{59}{8} - \binom{53}{8}$.  My R session tells me the answer is 1,331,148,689 or about 1.3 billion.

Subset cardinality as binary encoding 
Consider a set with $n$ members - surely a candidate for one of the most generalised and useful objects in all of mathematics.  Free from any representation, not tied down to a semantics.  Just $n$ objects.  How many subsets of this general set are there?  Transform this question into the following recipe for enumerating all proper subsets.  Imagine a register with $n$ bits.  Each possible value of this register represents precisely one subset by virtue of the first bit being set representing the state that the first object is also in this subset, the second, third likewise.  The total number of values for an $n$ bit register is $2^n$, which is also therefore the cardinality of the number of subsets - including the null set and the original set itself.

Survival of the *est
Abstract example.  Take that set of $2^n$ subsets of the primordial set of $n$ objects.  Which of those has the largest cardinality?  Why the set containing all $n$ elements, of course.  Of course, only because we have this omniscient perspective on the set of all subsets of $n$.  But imagine we have a much more local  and limited capacity, namely that  we can select 2 of those $2^n$ subsets and face them off against each other.  The 'winner' is the largest (or the one which has the highest of any other rankable measure).  Imagine we do that for the whole set of randomly chosen ordered pairs.  We collect each winner and, just like a knockout tournament, we pair the winners off.  We repeat.  At the end, the last set standing is the largest, and it will of course be the set of all $n$ objects.  This knockout tournament is like a partially functional merge sort algorithm.  The full equivalence is when we let all the losers battle it out too.  But back to the tournament.  There are $\binom{n}{2}$ initial pairings, there are $n$ rounds in the competition and there are $2^n -1$ actual matches in the whole tournament.  The CPU of a computer is precisely such a localised, embodied, non-omniscient actor, and that actor needs an algorithm to achieve what a set-theory God can know merely by intuition.  The tournament or natural selection, or markets represent a local-space algorithm which results in a somewhat God-like perspective.

Sequential snap
Again assuming limits to knowledge, let's imagine all $n$ objects in our primordial set have permanently associated integers 1, 2 etc linked with them.  Now, again in a very non-set way, let's create a permutation of those $n$ objects.  With limited knowledge, we will model the probability that when we examine this permutation, object by object, that the object associated with the integer $i$ will be examined at the $i$th examination moment.  The likelihood that you win the game is independent of the value of $n$, rather surprisingly, at $1- \frac{1}{e}$

Probability Preferences: Conjunction and Disjunction are primary, Disjunction more so

Making addition work with sets is the heart of probability theory.  Sure, a probability was really just a way of re-expressing odds, and that had been known about for ages before Cardano.  Odds of n : m means that the event has probability $\frac{n}{n+m}$, which allows you to work out a weighting.  But apart from nailing those numbers down to the range 0 to 1, the primary basic rule of probability can be thought of as specifying the conditions under which disjunction works at its most simple.  That is, it lays out what must be true about A and B to allow you to say that $P(A \cup B) = P(A) + P(B)$.  Set theory, of course, has its own history and life outside of probability theory, but probability theory becomes parasitic on set theory insofar as the general descriptions of events use the language of set theory.  In set theory, events are said to be disjoint when there's no possibility of overlap  The events have their own autonomous standalone identities, so applying the union operator allows for no possibility of double counting.  If you define a number of events $A_i$ and you want to state that there's no overlap anywhere you say they're pairwise disjoint, meaning that each and every pair from that list is disjoint.  We sometimes say the events $A_i$ are mutually exclusive.  What we don't say often enough is that this means they're utterly dependent on each other.  The occurrence of some particular of the $A_i$ disjoint events, say, $A_12$ tells you certainly that all the other events did not happen.  This is complete dependence and it isn't obvious just by looking at the corresponding Venn diagram.  If you have a full house, so to speak of events such that $A_1 \cup A_2 \dots  A_i = S$, the entire sample space of possibility, then you've fully specified a probability model and can say $P(\bigcup_{i=1}^\infty A_i) = \sum_{i=1}^\infty P(A_i)$.  With this single condition, the addition of probabilities is born.  It is a very constrained sort of addition, to be sure, since no matter how many disjoint events in your experiment, even an infinite number of them, your sum of probabilities (all those additions) will never result in a number greater than 1.

Examples of these utterly dependent events.  Rolling a die and getting 'red face up' (with a red-orange-yellow-green-blue-indigo die), tossing a coin and watching it fall heads-up, selecting the six of clubs by picking randomly from a pack of 52 playing cards, rolling a traditional pair or dice and getting a pair of sixes, rolling a die and getting an even (not an odd) number of pips face up.

With dice and coins, notice that it is in spinning them that we rely on their shape to select precisely one of n possibilities.  We initiate the random event and a separate object's physical shape guarantees the one of n result.  With picking a card, we initiate the random event but it is additionally in our act of selecting that we guarantee leaving the remaining 51 cards unturned.  Strictly speaking, the randomising action has already happened with the cards, when they were presumably shuffled thoroughly.  The shuffle, the toss, the flip.  These are the randomising acts.  With the toss and the flip, imagine the viewer closes his eyes on the toss and the flip.  Then he's in the same uncertain state as the person about to pick a card from a shuffled deck.

Notice you can fully specify a probability model with a complete set of pairwise disjoint events even if the events in question aren't elementary - the example above which I gave is of rolling a die and getting odd or even.

If I gave half the playing cards to one person and the other half to another person, perhaps in a different room, then if there was no form of communication possible between them, then we wouldn't have pairwise disjoint events across all 52 cards.  We'd have a pair of 26-card pairwise disjoint events, each of which was independent from the other.  Imagine if I gave one card each to 52 different people, in different countries.  Imagine further that I told them they could turn over their one card whenever they wanted, and as soon as they did so, to press a buzzer which had the effect of disabling the remaining 51 cards so that they could not be turned over.  Ignoring messy practical reality here, then there's no shuffle.  There's no natural sort order which could be applied to the geographical distribution of the people and cards, so no sense of working out whether they were randomly distributed in space.  Still, the buzzer and disabling devices make this a coherent utterly dependent trial.  

This requirement which allows simple addition of probabilities has implications for the randomisation machine - if it is to co-ordinate precisely 1 of n outcomes, then all n outcomes must be co-ordinated or constrained by someone or something.

Conjunction, on the other hand, cannot work in a world of mutually exclusive events.  By definition, there is no overlap anywhere.  So the major set up axiom of probability theory identifies a set of events on which it is impossible to perform intersection (probability multiplication).

In summary, the basic axioms of probability nail it as a real number in the range 0 to 1, and identify a set of events on which natural addition is absolutely possible and natural multiplication is absolutely impossible.  Finally, when you have a set of mutually exclusive, absolutely dependent events which cover all the outcomes of a trial, then the set of events is called a partition of the sample space.

Sucking the pips off

Around any randomisation machine humans build rules which allow you to throw away information.  How do you analyse this mathematically.  Here, somewhat artificially, I'll constrain the analysis to dice.

Imagine one die with no distinguishing marks.  What's the information content?  Yes, 0.  You learn nothing new on  each throw.  Mathematically, the information content is $-\sum{p_i \log_2(p_i)}$.  You can think of this as a single probability $p$  value $1$.

Now re-imagine the pips. This time $I = -6\times{\frac{1}{6} \log_2(\frac{1}{6})} = 2.6$ bits. You can still throw a pipped die and mentally decide to ignore the number which lands face up.  What have you done?  You've created in your head an equivalence class.  You've said to yourself, 'for my own purposes I will assume an outcome which is a combination of all six elementary outcomes'. Given each elementary outcome is independent, you can find the probability of your all-encompassing equivalence class as the sum of the elementary classes.  Let $E_c$ be your all-encompassing equivalence class  and $e_1$, be the elementary outcome of getting a 'one' face up, etc. Then $E_c = e_1 \cup e_2 \cup e_3 \cup e_4 \cup e_5 \cup e_6$ and, by one of the three basic axioms of probability, $P(E_c) = P(\bigcup_{i=1}^6 e_i) = \sum_{i=1}^6 P(e_i) = \frac{1}{6}\times 6$.

So, just by imagining it, you can turn off your randomisation machine.  The same trick can be used to turn your randomisation machine into a coin-flipper, which as you can guess, provides just $1$ bit of information.  Just imagine two elementary outcomes, even numbered pips and odd numbered pips.  So what you have is a randomisation machine which has a maximal amount of information on offer to you.  The rules of your game, your context, determine how you might want to throw some of that information away for the purposes of your game.  You've combined elementary outcomes.  So one die can deliver a uniform distribution of 6 events of probability $\frac{1}{6}$, or a coin flip.  You can see how you could imagine  randomisation machines giving two unbalanced equivalence classes, of probability $\left\{ \frac{1}{6} \frac{5}{6}\right \} I=0.65$ bits and  $\left\{ \frac{1}{3} \frac{2}{3}\right \} I = 0.9$ bits.  You could chose to implement this in a number of different ways.  For example, in the $\left\{ \frac{1}{6} \frac{5}{6}\right \} $ by imagining 'one pip' to be the first of your equivalence classes and 'either 2 or 3 or 4 or 5 or 6 pips' to be your second.  $E_1$ and $E_{2\cup3\cup4\cup5\cup6}$, if you will.  But just as good a job could be achieved by $E_2$ and $E_{1\cup3\cup4\cup5\cup6}$, etc.

Equivalence classes are a mathematically formal way of expressing the idea of treating one or more possibilities as coming to the same thing for your current purposes.  It maps out a geography of interest and that geography is only constrained by the granularity of the maximal information state of your randomisation machine (playing cards, for example, are more fine grained, since you can have $52$ distinct elementary outcomes).

  In the next post, I'll look at how to interpret multiple repeats of the die tossing experiment but I'll end by pointing out that, from an analytical point of view it doesn't matter if you consider multiple repeats as either happening simultaneously (you roll two  differently coloured dice) or serially (you roll the white die and note the result, then roll the blue die and note the result).  As long as you are consistent in which of the two parallel-roll dice you report first.  Since these two dice outcomes are genuinely independent, I'll show you how the informational additivity of independent random events works mathematically too.  This leads in to considerations about becoming indifferent to order or retaining order (combinations and permutations respectively).

This reminds me of the Samuel Beckett sucking stones extract from Molloy.