Showing posts with label permutations and combinations. Show all posts
Showing posts with label permutations and combinations. Show all posts

Saturday, 20 April 2013

The Problem of Points - Symbols

Christian Kramp invented the usage of the symbol ! to represent factorial.  The idea of $n(n-1)(n-2)..2.1$ as an interesting product which represents all the ways that n unique and completely distinct objects can be permuted dates to at least the 12th century.  To show this is the case imagine the following thought experiment.

Imagine that a man walks into one of the world's most sumptuous brothels.  His reward was to have a sexual encounter with every available woman in the brothel.  He enters a room filled with seven of the most desirable women he has ever seen.  One has jet black hair, is nearly six feet tall and has a full and firm ass.  Two is smaller with short black hair and a wicked twinkle in here eye.  Three is central Asian looking, small perfectly formed breasts.  Four is from south east Asia, an imperturbable and fiercely independent soul.  Five is from central Europe, innocently cheeky.  Six is from the Caribbean  tall and rangy.  He knows that he will fuck them all.  He picks number one, goes with her, comes back, picks number three this time.  Repeats until he is done.  This is a permutation.  A single permutation.  How many ways could he have chosen?  The answer is 6!, which   is 720.  He could have had 720 chronologically different sexual experiences.

Imagine you are him.  Imagine his decision moments.  His first decision was to pick the tall jet black haired girl.  This was a so-called free choice.  A choice of one in six.  Immediately start imagining a total of six parallel worlds.  In each world, he started with one or another of the six girls.  OK.  Focus on his reality again.  In the real world, he now has to chose which one of the five remaining girls to fuck.  Now, in each of the 6 parallel worlds, he'll similarly need to make a 1 in 5 choice.  So for each and every one of the 6 imagined worlds, a further multiplication of 5 occurs.  There are now 6 times  5 or thirty worlds which capture all the possibilities he has to chose from.  Repeat and you will find 720 different worlds.  In making his particular ordering choice,  he in essence picked one of 720 different worlds.

Without knowing the man, his sexual preferences, etc, if we had to guess his selection we could imagine each of the 720 worlds was equally likely to be chosen.  That is, you might say that the likelihood of choosing the fucking order of <tall-dark then short dark then central Asian then SE Asian then central European and finally Caribbean> was $\frac{1}{6!}$. 

Insofar as every object is uniquely distinguishable from every other object, then this idea of permutations is quite core to the most basic choosing activity - their ordering.  Visually you can see this as lining them up in a particular way, touching them in a particular, order, placing them sequentially on a particular chronology.

Imagine you got to know that some kind of selection process has 1,000,000 different distinct possibilities, the final result being a collection of 6 uniquely distinguishable objects.  Well, if you didn't actually care about the ordering your set of possibilities would be reduced down to $\frac{1000000}{6!}$.  Imagine you needed to pick 6 women to come on a journey with you.  Someone informs you that the selection process imposed on you allowed you to pick a particular order-important set of 6 women with equal chances $\frac{1}{1000000}$.  But you know that it doesn't matter to you what order they got picked.  They're coming with you all the same.  In this case, you'd divide your million possibilities by 6!.  Thus $\frac{6!}{1000000}$ is the likelihood of picking those 6 women (or indeed any 6 women).  Here you're using the permutation formula to make order irrelevant.  By knowing the set of choices implied in a strict ordering, you can use that knowledge to throw away the importance of ordering.

Klamp chose the word 'factorial' because it sounded more French than its rivals.



Saturday, 21 May 2011

Four Walls metaphor for probability

Of the great moments in the history of classical probability theory, three stand out.  First comes the idea of a relative frequency, which in essence is a discovery about the stability of certain kinds of measurement outcomes. That relative frequency compared with other relative frequencies, accounting for a disjoint and complete set of possible outcomes.  This idea must have been at least comprehensible, if not actually thought about, since the very first time a human could throw a lump of shit at a wall - the likelihood of it sticking to any brick is proportional to that brick's (relative) wall area.  In other words, even if no-one explicitly had that thought, I can easily imagine that if I suggested to people in prehistoric times to bet on which brick the shit would land, their choices would be partly determined by (all other things being equal) the brick's presenting surface area.



The second great moment in the intellectual history of classical probability is the creation of an artificially regular event space, the so-called equi-probable event space.  


This simplifying adjustment to the idea of a stable and complete set of relative frequencies allows analysts to physically count tiles to work out likelihoods or (proto-)probabilities - it being a ratio of one count over another, larger one.  Each of the $n$ equi-probable tiles has a probability of $\frac{1}{n}$ and of course $\sum_1^n{\frac{1}{n}} =1$


Explicitly counting only gets you so far before you might start making errors.  Imagine immense walls of tens of thousands of mosaic tiles.  As problem complexity increases, counting needs to be industrialised.  Enter the third great idea to become relevant - namely the application of counting and permutation rules as a way of formalising and regularising the process of counting enormous fractional event spaces.  The formulae for these counting power tools are $C_{n,k} = \frac{n!}{k!(n-k)!}$ and $P_{n,k} = \frac{n!}{(n-k)!}$ and the 'cheat sheet' is known as Pascal's triangle.



A fourth moment (not so much of classical probability but of modern decision theory and psychology), is the ongoing sequence of discoveries of the biasses and flaws, the self-deceptions and regularly occurring mistakes humans make in estimating subjective probabilities themselves.  This brings in the work of Kahneman and Tversky and the subject of behavioural finance,  and aims to discover the perceptual and cognitive bias which real humans inject into the mathematically rather more rational classical probabilistic modelling approach which has been achieved by our cultures so far in history.

Two final pleasing elements of the wall metaphor.

One.  The wall has two relevant dimensions, which reminds me of the law of multiplication of outcomes for independent events.  If an experiment has $n_1$ possible outcomes and a second, independent experiment has $n_2$ possible outcomes, then the joint experiment has $n_1 \times n_2$ outcomes.  Just like the length-wise and breadth-wise brick counts of a wall.  This generalises up nicely to many dimensions: $\prod^{k} \frac{1}{n_k}$

Two.  Walls are human constructs which help make buildings, another wonder of human culture.  As both of these technologies evolved, so too did the edifices they enabled become more marvellous.