Tuesday 12 April 2011

Discrete Probability and Probability

So this blog will be about some of my study notes for probability and other things that i need to remember for my exam tomorrow. It will not be as informative for the most part. But it might be able to show you some cool things that math can do.

Binomial Theorem: 

This is helpful for if you want to find the coefficient of a large polynomial really fast. Lets say find the coefficient of

( x + y) ^13 for x^6*y^7. Your probably going to write all of this out which would take forever factoring this equation out. To solve for the coefficient of x^6*y^7. Take a look at the exponent over the factored equation. It is 13. Now look at the exponent over your first variable x. This is 6. So your coefficient for x^6y^7 is the combination of 13 choose 6. Which happens to be 1716.

A combination is usually left in this notation C(13 6).

Pigeon Hole: This is really simple and a great way of solving probability questions. Lets say you have only k boxes(pigeon holes) and n distributable objects. Each object gets on hole. Until there is no more room for an object in a hole, then that object shares a hole with another object. By this principle there must be a box with

roundup( n/k) elements. Where roundup means whatever your answer is round it up. Also known as the roof function.

Example: 

61 people are in a classroom. Show that at least 6 people in the room share a birthday in the same month.

To break this down we know that there are 12 months.

The  by the formula plug in roundup(61/12) we get exactly 6 elements in one hole. So we know that atleast 6 people in the class share the same month for their birthday.

Indistinguishable Permutations:

Count the number of ways you can re arrange the word "dispose"

The answer is 7!.

Now this does not work for repeating characters. Such as in the word "goodbye" .
Where there is two "o".

The answer for this is the number of characters in the word. Divided by the factorial of the number of repeating characters.

The answer is 7!/2!.


Repetition allowed Combinations:

Giving by the formula:

C( n - 1  r , r)

Example: Suppose we have 10 loonies to give out to 5 children.

Our answer is C(5-1+10 , 10) = C(14 10) = 1001 ways.

Card Problems:

1. How many different 5 card hands can you make with a standard deck of cards.

C(52 5) = 2598960 ways.

2. 5 card hand with only spades. We know there is 13 spades in a deck. So for this just remove every other card and choose from your spade deck of 13 cards.

C(13 5)

3. The number of hands with 3 hearts and 2 diamonds. Split your deck into a deck of 13 hearts and 13 diamonds. Remove all spades and clubs. Pick from each deck appropriately 3 hearts and 2 diamonds. Multiple your combinations together.

C(13 3) * C(13 2)

Fruit Basket problem:

You have a basket with oranges and apples. You can only pick 4 fruit from the basket. How many ways can you pick four fruit.

You can just count them out.

Let O = orange and A = apples.

4O , 4A , 3O1A, 2O2A, 1O3A.

As you can see 5 ways.


Money Troubles:

You have a bag of money with different denominations: $1,2,5,10,20,50,100.

You want to how many ways can you pick 5 bills. We know there is 7 different values of bills in the bag. Using a combination that allows repetition we get

C(7-1+5 , 5 ) = C(11 5) = 462 ways.

Discrete Probability

Possibly my more favorite area of probability.

Must know formula :

P(E) = | E | / |S|   Where P(E) = the probability of an experiment. |E| = event, |S| = sample space

Example:

p(of drawing a queen from a standard deck) = |4| / |52| = 1/13. There is only 4 queens in a deck of 52.

Example:
If you roll two dice what is the probability that the sum of them add up to 5.

Show the number of ways to add up to five for visual purpose.

|E| = { 2 , 3} ,{3 , 2} , { 1 , 4 } , { 4 , 1 } = 4 ways.

We know that two standard dice have a possibility of 36 outcomes = 6*6.

So 36 is our sample space and 4 is our event. Therefore the answer is

P(sum of 5) = 4/36

Discrete Card Problems

Your dealt 5 cards from a 52 deck.

1. You want to get at least one ace.For this you have to find the hands with atleast one ace and minus it off the hands with no ace.

|E| = C(52 5 ) - C(48 5) <----removed aces from the deck
---------------------------
|S| = C(52 5)

2. You want to get a 4 of a kind. First we need a kind. Which is C(13 1)
Then we need the rest of the kind C(4 4)
Then we need another card from he remaining cards C( 48 5) 
So times these 3 events together to equal |E| and we know our sample space is C(52 5)

[C(13 1)* C(4 4)* C(48 5)] / C(52 5)

Circuits:

Euler circuit: Contains every edge once. Every vertex must have an even degree for one to exist. Must reach the same vertex. As denoted by a circuit.

Euler Path: Must visit every edge exactly once.

Hamilton Circuit: contains at least every vertex exactly once and returns to original as denoted by a circuit.

Hamilton Path: is just visiting every vertex exactly once.

Sequences and Formulas:

Just ways to determine what type of formula you should use.

Geometric: an = ar^n for n>= 0 
Arithmetic an = nd + a for n>=0
Recursion: usually my favourite.

Example: Find a solution to the sequence.

2,  5, 8 , 11, 14, 17, 20 ......

We can visually see this is incrementing by 3.

My solution for this would be

a0 = 2.
an = a(n-1) + 3 for n>=0.

Test it or yourself.

Composition of Relations:

Basically this has transitive properties.

Example:

A = { x, y, z} ,  B = { 0, 1} , C = { a, b, c, d}

Let R be a subset of  the product of A to B. Let S be a subset of the product of B to C.

R = { (x, 0) , (y , 1)} , S = { (0 , a), ( l, d)}.

The the Composition of S  and R denoted S o R or R o S is

S o R = R o S = { (x , a ) , (y , d)} You may be able to see how this is transitive.

14 comments:

  1. I'm legitimately impressed, i know i'll never be able to do any of this :O

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. Oops, messed up. You actually did have the birthday thing going.

    It is really awesome to find someone else competent in math in the blogger world. Do you do any stochastic modeling for engineering problems?

    ReplyDelete
  4. Thanks man, i'm in stats and this helped me out.

    ReplyDelete
  5. Any chance you can explain Euler's Identity. Always amazed me.

    ReplyDelete
  6. you must be Asian, and go to UCLA, either way, very smart cookie. I wish I could say I understood half of what I read.

    ReplyDelete
  7. And here I was thinking that what I had learned about probability was complex enough!

    ReplyDelete
  8. wow that was really complicated stuff! interesting though :)

    ReplyDelete
  9. Dude, i do probability at GCSE level but i haven't seen it implemented like this before...
    Good luck on the exam! I reckon you'll ace it with this knowledge!

    ReplyDelete
  10. nice, will need to go through it again to really grasp it though

    ReplyDelete
  11. I remember how difficult it was to learn those probabilities. Luckily that's in the past.

    ReplyDelete
  12. lol i just learned this last week in business stat

    ReplyDelete