Sunday, January 06, 2008

Poker: The All-in Flush Draw

Pretend I am TransFish. Now this has got to be one of my favourite poker moments. I hold 2 suited cards (as an example from the picture, AT--short for AceTen) and am heads up against a paired opponent.

Flop comes out 2 suits. The air is thick with anticipation. All is quiet, even as the chatters and shouts and excitement intensify across the table. My face is flushed as I await my flush.

First, the technicalities: What are the odds of me making my flush?

The intuitive answer I gave myself was: 50%.
4 suits. Each suit has 1/4 chance of flopping.
2 cards. Add them up.
Unfortunately, the actual odds of making that flush is much lower than the intuitive 50%.

We have 3 independent scenarios:
2 more cards of my suit + 1 card of my suit and 1 non suit + 1 non-suit and 1 card of my suit =
*Total of 52 cards. 2 are dealt to you, and 3 are dealt on the flop making a total of 5 known cards for you, and 47 unknown cards. Of the 5 known cards, 4 are of the suit of interest. There leave 9 more suits in the 47 unknown cards.

A better, and mathematically similar approach is:


There is a trick called the Rule of 4 (analogous to the Rule of 72):
We have 9 outs. To get the odds of making your outs come true, simply multiply the number of outs by 4, hence 9*4 = 36% (marvellous approximation!)
(out is defined as undealt cards that are favourable to your cause. The more outs the better!)

Now comes the game theory aspect of poker (with absolute zero knowledge of game theory, I substitute it with the rudimentary knowledge of calculating expectations)

Of course, the concept of "giving a free card" is also very crucial here--not for me, but for my opponents. I have yet to make my hand. I am waiting for a "free card"-- either on the turn or the river. Those who have me beat at the flop should make me pay (by betting heavily before the turn) to get the free card. In case, they don't, I will check quietly, but in case they do, I may just go all-in.
(A case of damned if they don't, and damned if they do, why else would I elect this hand to be my favourite poker moment.)

Why so?

Considering all possibilities when you go all-in. There are 3 and only 3 scenarios:
1) you win the pot outright. Everyone else folds ( the probability here varies. Say, each person has a 10% chance of calling)
P(0 people call) = 0.9^6 = 0.53 (assume 6 people are in the game)
P(at least 1 person call) = 0.47.

We can assume the probability of at least one person calling your all-in to be 50%.
Conversely, the probability of winning the hand outright is also 50% (everybody folds to your all-in)

2) you get called, and win. (0.5*35%=0.175)
3) you get called, and lose. (0.5*65%=0.325)

Calculate expectation.
Let PotMoney = P.
Let your current stack = x.
Let n = total number of opponents who call your all-in
We want the expectation E[all-in] to be as high as possible, and the 2 variables helping us are P and n.

Let's calculate how high P should be for a favourable all-in.
For expectation > 0 (for n=1),
This means that as long as P is 30% of your current stack, it is not too foolish to go all-in (note my cautious choice of words). When n > 1, P becomes immaterial. Simply put, the expectation just gets higher as more people call your all-in. And the best part is, you are taking on the same risks for higher expectation. Mostly, the people who are going to call you are the pairs and the trips. Best if they are holding on to a flush draw like you, but have an inferior high card. The poker people call these suckers drawing dead. (Yea, you keep waiting, keep drawing, and oh thank god when you finally made your flush, but you still get beat!)

Factors to consider before making the quantum leap:
1) The number of people playing
2) The pot
3) How much money I have
4) Chances of anyone making a full house
5) I better be holding the Ace or King of that suit, giving me a nuts flush.
6) Stages of the game (Opening?Endgame?)

I favour amassing chips at the beginning stages of the game. With a large stack, I can proceed to bully the table for the rest of the game, which is something I highly recommend to do once just for the experience. Pointing at my short-stacked opponents, I can either:
1) laugh at them
2) ask, "How much have you?", and throw the amount of bet equal to what they have, forcing them to go all-in for every card they play. And then repeat Step 1.

The gist is: for an all-in, your upside is unlimited (you never know how many "by-catch" are caught on the trailing hook), but your downside is limited to your all-in. When the gambling blood in me goes on full boil, calling all-in is something I relish!

Things I learnt from William Feller

1. The trial of 1 coin thrown 1000 times is different from the trial of 1000 coins in one instant. That is, given the results (statistical characteristics) of both experiments, one can deduce if its the former or the latter.

Reason:
The laws governing prolonged series of individual observation (random walk) is entirely different from the laws derived for a whole population (law of large numbers).
Time average does not have bounded expectation and hence DOES NOT obey Law of Large Number (LLN). Instead it has its own set of "arc sine" laws strictly for waiting times.Ensemble average has bounded expectation and hence obey LLN.

It sounds absolutely preposterous. I must admit the math on LLN and CLT (Central Limit Theorem) get a bit too dense for me here, but please read Feller thoroughly before dismissing the idea. Perhaps ensemble average lacks the dimension of time--that's what makes it different.

2. Given a fixed probability average (which is reasonable if we apply Laws of Large Numbers), increased uniformity in each independent Bernoulli trial increases the variances. For example, given a certain quality p of n machines, the output will be the least uniform if all machines are uniformly equal.

Given a probability distribution of Bernoulli trials with variable probability,




To summarise: Set of the wildly fluctuating {0.1, 0.4, 0.7} is good. Set of the more uniform {0.4, 0.4, 0.4} is no good.

Another shocking revelation. I hope the Six Sigma folks are aware of this fact. I would like to venture forth an analogy from thermodynamics: Entropy of a system is at its maximum when the system is isothermally uniform. Similarly, variance of a system is at its maximum when every point within the system is uniform. Makes one think about our intuitive understanding of the word "variance".

What is Entropy? by Erwin Shrödinger

3. All it takes is 23 people to make it more likely that at least 2 of them share the same birthday than otherwise.

I suspect people who share the same birthdays have an instant affinity to each other because of the perceived rarity of such events. But I for sure won't flinch again if another May girl comes along.

4. German bombs felled over London were found to be perfectly random and homogeneous, despite apparent evidences of some areas being more heavily bombed.

Reason: to the untrained eye, randomness appears as regularity or tendency to cluster.

Anyway, that's what the chi-square tests are for--to determine if the pattern we are seeing is indeed an anomalous pattern or a good fit to the Poisson or Normal distributions, which are essentially random.

5. Given a sampling of German planes and their number plates, statisticians guesstimated the total enemy plane productions in World War 2.

Assumption: the number plates were given sequentially.

6. Even if a game is fair, where the expectation of winning (per trial) = entrance fee (per trial), there is nothing in the law of large numbers to prevent you from losing money with a probability of 1. (= sure lose).
(LLN only says your loss is limited to a magnitude less than n).

Assumption: we are dealing with random variables with divergent expectations (eg random walks)

7. We live in a world of no advance knowledge. For example, even the prospect of the sun rising tomorrow is subject to the conditional probability below:

P( sun will rise tomorrow | sun has risen for past observable 1826213 days)
= n+1/n+2 (Law of Succession of Laplace)
= 1826214 / 1826215
= 0.999999

Assume that we have no prior knowledge of the motions of the celestial bodies that causes the phenomenon we call "sunrise".

Wiki on Sunrise Problem

Proof. Bear with me on this hypothetical situation. Imagine there are 20 parallel universes, each created by a supremely bored Creator who, for pure amusement, determine the lifespan of each universe he created by drawing a ball from an urn containing red balls and white balls for each universe.A red ball drawn denotes the survival of the sun for that year. A white ball drawn means the sun must be extinguished by that year. The 1st universe has an urn of 0 red and 19 white balls. The 2nd universe has an urn of 1 red and 18 white balls and so on... Hence, each universe has different likelihood of being extinguished, with the 1st universe most likely to be dead, and the 20th universe least likely (in fact, impossible, since there are 19 red balls, and 0 white balls, are contained in its urn).

Say, human beings live on one of the universes, but they have no idea which universe they belong to. They have thus far survived for 10 years (i.e. 10 red balls have been drawn).

Let total number of balls in each urn be N.
Let total number of universes be N+1.
Let current number of years the Universe has been around be 10.

The probability of 10 red balls drawn = P(A) =
P(10 red balls from Universe 1).P(Universe 1) + P(10 red balls from Universe 2).P(Universe 2) + ...+ P(10 red balls from Universe 20).P(Universe 20)

The probability of the 11th ball being drawn is red = P(B) = 1/12.
Hence, the probability of the 11th ball being drawn is red, given that the 1st 10 balls drawn are red
=P(B|A) = P(AB) / P(A)
=P(B) / P(A) (as P(AB) = P(B)...think about this, they are mathematically equivalent)
=(1/12) / (1/11)
= 11/12
= (n+1) / (n+2) where n = number of successful observations

Note the interesting and immensely useful approximation:
which works as the Riemann rectangles are being approximated (though underestimated) by a continuous curve x^n, much like how the binomial distribution is approximated by the normal curve. The error becomes smaller as n goes to infinity.

Of course Feller warned that such ideas were already discredited, and could very well be labelled pseudo-science. But the mathematical developments of hyperspace have thrown up the distinct possibility of parallel universes co-existing with our own. Maybe ours might just be the one whose sun goes out tomorrow. Anyway, Pink Martini seems to agree:

If tomorrow's sun doesn't shine,
And no creatures stir in the morning time,
If the clouds go still in the sky,
at least I'll have my Clementine.

If tomorrow's moon doesn't show,
And our dreams go lost in the winter snow,
If the flowers wither and die,
at least I'll have my Clementine.

Download clip sung by China Forbes here

Monday, December 31, 2007

New Year Resolutions

...No more Maximators, but I'll have problems with pouring boiling water on ants. It's the only time I get to be a napalm pilot.

Saturday, December 29, 2007

Flight Of The Conchords - Jenny

Bret: Hello.

Jemaine: Hi.

Bret: Hello man sitting in the park.

Jemaine: I just said hi, woman in the park.

Bret: How you doin'?

Jemaine: Mmm'good thanks.

Bret: Your looking good.

Jemaine: Pardon?

Bret: I said you're looking good.

Jemaine: Fair enough.

Bret: 'Jenny

Jemaine: Pardon?

Bret: Jenny

Jemaine: No I am sorry I think you've mistaken me for somebody else

Bret: No it's me, I'm jenny, my name is Jenny

Jemaine: Oh You're'oh' Ha ha ha ha' I thought' oh' what a hilarious misunderstanding.
Nice to meet you Jenny

Bret: We've met before - quite a few times actually.

Jemaine: Yes of course we have. I meant it was nice to meet you that time that I met you. Where was it that we met that time that I met you when I met you?

Bret: At a party.

Jemaine: That's right! Wasn't it one of those boring work parties?

Bret: No.

Jemaine: That's why I said wasn't it. It was the party of a mutual friend. - Was it? - Wasn't it? - Was it? - Wasn't it?

Bret: Yes it was.

Jemaine: Yeah, I thought so. Oh'Bobby's.

Bret: No

Jemaine: Doug's?

Bret: No

Jemaine: D-dog's?

Bret: No

Jemaine: Maxwell's?

Bret: No

Jemaine: Andy's?

Bret: Yes Andy's

Jemaine: Yeah Andy's party, ooh that's right. Ooh, Andy knows how to throw a party, doesn't he Jenny?

Bret: Yeah, I love Andy's parties!

Jemaine: I love Andy's parties. What crazy parties. How is that guy anyway?

Bret: She's good

Jemaine: Ooh that's right, Andy hates it when I forget that.

Bret: We watched a movie.

Jemaine: Yeah'it was something like but not necessarily Schindler's List. We watched it and we wept

Bret: It was Police Academy 4. We went for a walk

Jemaine: On our feet if I remember correctly.

Bret: We walked to the top of the hill and we ate sandwiches.

Jemaine: Oh, We'd just grab a sandwich and put it in our mouths. Oh, that's the only way to have sandwiches. Oh Jenny, tell me do you still walk? Do you still get into sandwiches in a big way?

Bret: Still walk a lot but I am not eating as many sandwiches as back then

Jemaine: Uh'

Bret: Do you remember what we did up there at the top of the hill?

Jemaine: Kind of'

Bret: We were standing at the look out

Jemaine: Oh, I remember exactly what we did at the look out. We just looked out' across the city from our little spot on the hilltop. Oh, It is so pretty from way up there. We talked about how the lights from the buildings and cars seemed like reflections of the stars that shined out so pretty and bright, that night.

Bret: It was daytime.

Jemaine: The daytime of the night.

Bret: Do you remember what you said to me?

Jemaine: Not word for word actually Jenny, but I remember there was some verbs.

Bret: Well you said meet me here in one year. You just needed some time to clear your head, and you seem to have done that.

Jemaine: La la la la la la la la la la la la la.

Bret: We have a child.

Jemaine: Pardon?

Bret: We have a child.

Jemaine: Why didn't you tell me, Jenny? Why didn't you tell me that day when we went to the top of the hill and we made sweet, oh how we made such sweet, sweet sandwiches. Does it have my eyes, my way with words? Does it look like me at all?

Bret: No, not at all 'cause we adopted him. I can't believe you don't remember, it was a very difficult process!

Jemaine: Oh'uh, oh'are you sure that was me Jenny?

Bret: Yes I am pretty sure that it was you, John.

Jemaine: I'm Brian

Bret: Oh my god! I'm so sorry!

Jemaine: Don't worry.

Bret: Now that's terrible.

Jemaine: Oh, don't worry.

Bret: Oh, how embarrassing!

Jemaine: Don't worry Jenny, I'm actually quite relieved. *That kind of thing just happens all the time, I just got one of those faces I suppose

Bret: So does John, ha, he's got one of those faces as well'

Bret and Jemaine: *awkward laugher*



*Note from blogger: I got kicked playfully once while sitting in a public place. Of course I was pleasantly surprised when I turned around and saw this pretty girl with long tresses and big eyes, only to be disappointed that I wasn't the "I" she had meant to kick (playfully I should add). I just got one of those generic faces I suppose.

Flight Of The Conchords...

...are the best thing since Monty Python. Check out all their vids on youtube, and be in awe of their mastery of guitar licks and comedic timing.


Getting serious on social issues...


and having fun with randomness.


The duo, who are obviously very comfortable with the ladies, have a deadly refrain for the perennially clueless(and the nocturnally prematured). Try these lines next time you find yourself tongue-tied for words:
"I want to make love to you, it's the least I can do. In the bedroom, I'm a gentleman, the ladies come before me....but 2 minutes...2 minutes is all you need--cos I'm so intense..."

Wednesday, December 26, 2007

The Snowman

Flying through the moonlit sky and dancing under the Northern Lights are what childhood dreams are made of. The girl in the attic must have been Norwegian girl Cecilia from Through the Looking Glass, Darkly. There are no penguins in the Artic though. And the haunting minor song belies what seems at first to be a Christmas tale full of innocent fun and glee.

Saturday, December 22, 2007

The Normal Bound

*Warning:Post contains pseudo-philosophical ramblings. Read at your own intellectual risk.

Most of us are only too familiar with crushing disappointments, meaningless jobs, indifferent love lives. Trapped in the monotony of everyday life, we make peace with regrets even as they slowly take the place of our dreams. We yearn for something more, and we continue to hope and dream and be disappointed and unhappy in an unyielding cycle. Sages have often hinted at the key to these life problems. "Seek material comforts, and you become enslaved by them.", "A simple life is a contented life", so says the Zen masters. Even Dilbert got into the act with "Tell me what you need, and I'll tell you how to get along without it". They all mean the same thing: Please lower your expectations.

There is even a mathematical construct for this. We are all bounded by the normal curve, and we aren't even aware of it. In math-speak, our hopes are often dashed because we aim at results which lie outside of the standard deviations that our lives are bounded by.

99.7% of [just about everything] are bounded by 3 standard deviations (sigmas) on either side(=6 sigmas in total). Six Sigma isn't the cult or martial arts movement that its fanciful name suggests, but a set of management practices implemented to improve manufacturing yield.

You wish to be a millionaire? Wealth is most likely a zero-sum game...so....
You yearn to be good-looking? Even the biological genes adhere to the normal curve. Just thank your lucky stars you (most of us anyway) are born without major defects.
You hope to have genius level IQ? Sorry to disappoint, but the normal curve doesn't agree.
You pray to be extremely talented? Consult with the normal curve first.
You want to be unique? But you already are...just like everyone else. We live in a wonderful world of predictable uniqueness and conventional individuality.

So what exactly is this normal curve that imprisons us so? Here's a Q-and-A session (with knowledge of high-school statistics assumed) to aid your understanding of your fate.

Q: What is the normal curve?
A: It's a probability distribution that is an approximation to the binomial distribution, which is the distribution of HAVES against HAVE-NOTS, the BLACKS against WHITES...or anything with bipolar outcomes (or Bernoulli trials).

It is also the approximation to a lot of other distributions, including that of sample mean, sample variances, in which case, the Central Limit Theorem applies, but I shall focus only on the special case of the Binomial (De Moivre-Laplace Theorem).

Q: The equation please.

n(x) is the normal equation, and R(x) is its integral or area under the curve with bounds given as -infinity to x.

Q: Why this equation?
A: It could be seen as a conscious sculpturing of what is essentially an exponential curve to a bell-shaped curve. And because if you integrate from -infinity to infinity, you get a probability of 1. Everybody in the world must belong under the umbrella.

But there is a rigorous mathematical proof which is based on the binomial distribution. Using firstly Stirling's Formula to strip away at the binomial coefficients, then approximating (k/n) ~ p and (n-k/n)~ q as n gets large,
(here, we are treating k as the random variable Number of Success, and the law of Large Numbers dictate that the rv goes near the mean), and substituting:
and finally applying Taylor's Formula, one arrives at the beautifully stark Exp[-0.5x^2]. This is a real statistical workhorse found in many applications.

A very clear proof is given in Yakov Sinai's Probability Theory:An Introductory Course.
Google on Sinai

Q: How about the term 1/ root (2pi)?
A: From the constant of Stirling's formula, which in turn is derived from the Wallis product. Wiki on Wallis

Q: The binomial distribution is discrete, varies according to p and n, and comes in different shapes and sizes, so how can it be approximated by the normal curve?
A: Ultimately, they all take on the shape of the bell-curve. The local asymmetries are overshadowed by the general symmetry as n goes larger.

Take for example binomial distribution with n=10, and probability p=0.1, with an obvious skew (they call it right skew, even though the graphs sort of leans left).



If I increase n to 100, the skew disappears--as if by magic. No, it's magic.



Q: How do they make sure that the normal curve, despite coming in all shapes and sizes, have a total area of 1?
A: Realise that area under f(x) = area under hf(hx), where h is scaling factor. It's that simple. Intuitively, for h>1, the height becomes taller, but the width becomes smaller.
For h<1, the height becomes shorter, but the width broadens. The area simply never changes.

In the plot below, the taller plot has h =1, while the flatter plot has h=0.5. The areas under both curves are....you guessed it, 1.



In math-speak,



Letting:



We get:



which is of the form hn(hx).

Q: How do we convert every single normal curve to their standard form?

Substituting:


We re-evaluate the normal integral with a given range k1 to k2 as:


In doing so, we have also scaled the discrete k-axis (of the binomial) to the continuous z-axis. Some ppl call this the z-transform. But this terminology conflicts with the actual z-transform used in signal processing. I stay away from the term.

Q: Is the substitution arbitrary?
A: No. We know the number of success X (random variable of the binomial distribution) has mean and variance.

In general,



We are turning all binomial distros to normals with mean 0 (centred at 0 ) and variance 1.

Q: If it wasn't arbitrary, then how was it derived?
A: I am not aware of any derivation, but the remarkable coincidence (in the fact that this substitution in the proof reduces the binomial to an exponential curve and at the same time, reduces the mean to 0 and variance to 1) seems like a natural phenomenon just waiting to be discovered.

Q: How can one take a discrete scale and turn it into a continuous scale?
A: This is only an approximation. The area under the discrete scales are formed by blocks of rectangles (or Riemann Sums, since everybody loves Riemann), while the continuous area is formed by passing a curve through the centre of the rectangles. The curve will naturally tend to underestimate the true area. To compensate for the error, we enlarge the range of the integral to include the areas at the extreme sides. They call this the continuity correction.



Q: Why do we use the standard normal statistic table?
A: The integration of the statistical workhorse is difficult. There is a fancy term for the integration: Jacobi elliptic integral, when we change the integration from xy-coordinates to polar. Someone came up with the bright idea to tabulate all the possible permutations of the answers into what is known as the Statistical Tables.
Anyway, in those pre-Casio days, they had tables for everything.

Q: What is the name of this theorem again?
A:De Moivre-Laplace Theorem. It first appeared in 1733, published by Abraham de Moivre. At that time, most of humanity was ekeing out a living not much better off than that of the Dark Ages, and yet math was already, compared with* our present world, graduate level stuffs.

*not compared to

Q: How is it related to the Central Limit Theorem?
A: The CLT is the generalisation of the De Moivre-Laplace Theorem. As long as we have the mean and the variance of any one single trial of the distribution (e.g. for binomial distro, a single trial is the Bernoulli Trial, and hence mean = p, and variance=pq), we can approximate them using the transformation below:



Q:What do I get out of the normal curve?
A: What seems at first to be asymmetry in a collection of data is revealed to be a beautiful(if austere)symmetry. The good news is, you can apply this theorem to practically anything, simplifying many otherwise computationally tedious tasks. The bad news is, you are part of it.

Q:How do I get out of the normal curve?
A:Best of luck.

Thursday, December 20, 2007

Things I learnt from Nassim Taleb

(in order of priority)

1. Beware David Hume's black swan.
No amount of observations of white swans can allow the inference that all swans are white, but the observation of a single black swan is sufficient to refute that conclusion.

Chickens pay the ultimate price by haemorrhaging like elephants.

2. Heed Solon's warning: It ain't over till it's over.

3. Learn from Odysseus who stuffed wax in his ears in the Sea of the Sirens:
I am not intelligent enough, nor strong enough, to fight my emotions.

4. Do not get married to yourself. Change your ideas and opinions as often as is necessary.
(In a parallel, Arthur Rubinstein was known as a pianist who changed his musical ideas and thoughts on a whim, much like George Soros and his investment principles.)

5. Children only learn from their own mistakes, no possible warning by others can prevent them from touching the hot stove. Likewise, book knowledge never lasts compared to life's (bitter)experience.

6. Yiddish saying: If I am forced to eat pork, it better be of the best kind.

7. Maths is a way of thinking, (much) more than a way of computing.

8. Your life expectancy increases each year you get older. If national life expectancy is 75, and you are 74, you are NOT LIKELY to die the next year. Remember that 50% of the population have lower than national life expectancy.
Other similar sayings: 50% of the population has lower than average IQ.
If you are not doing more than the average, you are pulling the average down.

9. Survivorship bias:
Imagine 1,000,000 analysts (or monkeys) making completely random predictions on 2 outcomes (market go up/market go down). 1 epoch (whatever length of time you may choose to define) later, only 500,000 analysts get their predictions correct.
Another epoch later, 250 000 analysts remain standing. After 15 epochs, there are still at least 30 analysts (1mil/ 2^15) surviving with 100% records. They are the fools of randomness we worship as Gurus.

10. Gurus usually develop the unfortunate habit of writing books about their random success.

Sunday, November 25, 2007

End of the road for an Addict

It's not often that humour can be extracted from a subject matter as heavy as World War 2, but there you go...

Saturday, November 10, 2007

4D combinations












Ok. You see the number plate flashes by, and the gambler in you immediately wonders how many permutations of 4D can you buy with that 6 digit combinations - 378953.

Easy. It's 6P4 ( order matters here), and then to account for the double occurence of 3, we divide by 2. 6P4 being 360, the answer is 180.

Right? Wrong. Though the actual answer, 192, is close, the thought process is more tedious than is first suspected. What's more, should any of the 12 more numbers which you miss out strike top prize, you will be left cursing your high school math teacher.

Let's examine what happens with 6P4. It's fundamentally similar to 6C4 (where ordering does not count), and then multiply by 4! ways of reordering the 4 numbers you choose.

6C4 = 15. Let's list down all 15 cases.
Since there are 2 occurence of 3, I shall denote them by 3 and 3.

7895
3789
3895
3795
3785
3789
3895
3795
3785
3378
3379
3375
3389
3385
3395

Let's denote the 15 occurences into 3 groups:
Group 1: No occurence of 3.
Only 7895 here.
4C4 x 4! = 1 x 24 = 24 ways

Group 2: 1 occurence of 3.
8 groups here, but since 3 and 3 are similar, we shall deal only with 4 groups.
4 groups, in which there are 4! ways to order each group:
4C3 x 4! = 4 x 24 = 96 ways

*why 4C3? Since 3 is already selected, we have 4 more numbers 7,8,9,5 vying for 3 places.

Group 3: 2 occurence of 3.
6 groups here.
Since the 3 and 3 are similar, it is no longer 4! to order with each group.
(Remember, 3378 and 3378 are exactly similar.) We do 4!/2! = 12 ways.
4C2 x 4!/2! = 6 x 12 = 72 ways.

*Why 4C2? Since 33 is already selected, we have 4 more numbers 7,8,9,5 vying for 2 places.

Total number of ways = 24 + 96 + 72 = 192 ways.


What if now the 6 sets of numbers is changed to 337789?

We have to split our tasks into 9 groups:(think of trinary system 3^2).
Luckily for us, some groups are mathematically impossible.









Total number of ways = 78 ways.

Imagine if you had used 6P4, and then divide by 2(to account for 3 presumably) and then divide by 2 again (to account for 7), ending up with 360/2/2 = 90. With more careful math, you can actually save yourself from buying 12 repeat combinations!

Monday, November 05, 2007

Great Songs that met their Video Match

Celebrating the simplicity of it all...





...or contemplating the fragility of it all.

Friday, November 02, 2007

Binary Model and Inclusion-Exclusion Theory

A dice is rolled t times. What is the probability that all sides appear at least 2 times?

Sounds like a simple question. We have to be cautious though, for "what is the meaning of life?" is too a simple question that has stumped humanity.

First up, we search for an opening to the problem that is at once accessible to us.
Consider this: if all sides were to appear at least 2 times, the smallest value for t has to be 12. One possible set for t=12 would be {1,1,2,2,3,3,4,4,5,5,6,6}. In fact, this is the only set possible.

We see that for t<12, P = 0. And we can calculate the probability for t=12 by means of simple combinatorics:






This approach may not be useful, but the answer comes in handy to allow us to verify whatever complicated equations we may derive later.

(Or we can build from this approach, evaluating 13 throws as having 1 extra throw to distribute among the 6 sides. 6 choose 1 = 6. Hence, ans = 6*P12.
For t=14, we have extra 2 throws to distribute among 6 sides = 2 balls to distribute among 6 urns. 7 choose 5 = 21. But it is not so simple to evaluate now, as the number of ways is not all the same probablity.)

Where do we go from here? Introduce the binary system! And one that is symmetric in event space. Let each bit represent one side of the dice: A1 A2 A3 A4 A5 A6.

Now, how shall we define 1 and 0?
Consider that we want to find probability of "at least 2 times". In other words, we can find 1 - P(0) - P(1). With this in mind, we define bit 1 as occurence of 1 or 0 times, and bit 0 as occurence of 2 and above times, so that we can do something like 1 - P(...).

Now we can construct the Binary Table!













Let us inspect the meaning of each row.






The first row means all the numbers must appear at least 2 times. Hey! This is the case we want to find! Now things becomes apparent. To find the probability of this row, all we have to do is to sum up the probability of the rest of the rows, and do a 1 - P(prob of the rest of all the rows). Note that all the rows of the Binary Table are mutually exclusive.





The second row. It would mean Number 1 appears once or 0 times, and the rest all appear at least 2 times.








The last row. It means that all sides appear at most 1 time, hence giving a maximum of t=6 (or a minumim of 0). As earlier established, t has to be >=12, so the probability of this happening is 0. We shall not consider this case.
So there are a total of 2^6= 64 cases for us to sweat on.
(actually 63, as we discount 111111....)

Let's start evaluating the probability of Row 2. (Row 1 is 000000. There is very little information we can get from that.)






How can we find the probability that the Number 1 appears only once or none WHILE ensuring that the rest appear at least 2 times? Unfortunately it is too difficult.


Imagine t=12.
For 1 to appear 0 times(NONE): we need to find the number of ways to solve A2+A3+A4+A5+A6 = 12...a case of 12 balls distributed among 6 urns.
For 1 to appear 1 time: we need to solve for the number of ways to solve
A2+A3+A4+A5+A6 = 11...

Mind boggling stuff. And that's only for the 1 out of 62 cases we need to establish.

Instead, for that row, I am forced to consider a variation of it:






Here, I introduce a 3rd state x to mean Don't Care. I do not care what happens to the rest of the number as long as Number 1 appears 0 or 1 time in t throws. The probability of the case I just mentioned is actually humanely possible:











Why the term




Because we still need to account for the fact that this appearance of Dice Number 1 can occur at the first throw, or at the second throw,...up till the t throw. For lack of a better term, let's call this the t Loop.

The formula can now be combined:






Now we shall generate the full table, which I shall call the Don't Care Table.













One very important point to note is that the table is a truncated form. I left out the rows xxxx1x, xxx1xx, xx1xxx, x1xxxx, 1xxxxx, whose calculation is similar to the one we did for xxxxx1. Please bear this in mind! Also note that the rows of this table aren't mutually exclusive!

But how does the Don't Care table help when all we want is to sum up all the 62 rows of the Binary table. Ah....Poincare has this figured out. He found that to calculate the probability of the whole table minus the case of 000000 (we cannot include 000000, else the Probabilty is unity), for example, we must do:





As mentioned, the rows are not mutually exclusive. xxxxx1 and its 5 cousins (xxxx1x, xxx1xx,xx1xxx,x1xxxx,1xxxxx) contain all of what we want from the Binary Table...and more. We have some subtraction on our hands.

Consider the last row 111111. This row is exactly the same whether in the Don't Care or Binary Table. It is the simplest element in a recursive algorithm.
Now consider the second last row x111111. It can either be 0111111 or 1111111.
Hence, to get 0111111, all we have to do is to compute x111111 - 111111.
Therein lies the recursive algorithm, which we use to work back all the way to the top.

If you are not convinced, work out the next row 001111 (which is going to be a bit more tedious.) First we evaluate xx1111:
xx1111=001111+011111+101111+111111
Hence, 001111 = xx1111-(011111+111111)-101111
Knowing x111111=011111+111111, the equation becomes 001111 = xx1111-x11111-101111

We now need to break down 101111 into its elements.
We consider 1x1111 = 111111 + 101111
101111 is then equal to 1x1111 - 111111.
Since 1x1111 = x11111 in absolute value, we get 101111 = x11111 - 111111

We get 001111 = xx1111 - x11111 - 101111 = xx1111 - x11111 - x11111 + 111111
= (2C0)xx1111 - (2C1)x11111 + (2C2)111111

Finally, we can set up this equation:
(6C1)000001 + (6C2)000011 + (6C3)000111 + (6C4)001111 + (6C5)011111 + (6C6)111111
= (6C1)xxxxx1 - (6C2)xxxx11 + (6C3)xxx111 - (6C4)xx1111 + (6C5)x11111 - (6C6)111111

This is basically the inclusion-exclusion theory, now cast in a different light with my binary model. Bear in mind that it is EXACTLY of the form:





Let's take a look at the next row.






If you realise here, we are going to introduce another binary system. Take stock for a moment what is happening: A binary system and a t Loop inside another binary system which has been modified to a Don't Care system. That's rhetoric you can ignore.

The internal binary arises from having 2 Numbers now combining to give 00, 01, 10 and 11. The equation is now:







Why the term





The t Loop that was mentioned a while earlier has gotten a bit sticky. When there was only 1 event, now there are 2 events A1 and A2 to account for, resulting in a total of 3 distinct groups to arrange: A1,A2 and the rest (t-2). Rearranging the term, we get:






We now revise the Row 2 equation:





We do the same for all rows, and come to a general ROW equation:




Now comes the defining moment.
We are going to loop through all the rows, executing
xxxxx1 - xxxx11 + xxx111-xx1111+x11111
(ignoring 111111 of course),
which is equal to the summation of the probability of all the rows in the Binary Table except 000000.

Summation of the probability of all the rows in Binary Table except 000000=
Alternating inclusion exclusion of Dun Care Table =





Hence, our answer to the question posed right at the beginning is:






I have not verified the answers yet. Remember at the beginning, we solved for t=12. This is a good start to verify the formula.

Note that the internal binary loop would become Trinary (0,1,2) if the question is rephrased:
A dice is rolled t times. What is the probability that all sides appear at least 3 times?