Probability & Statistics

Details
Last Updated: Thursday, 18 April 2024 23:50
Published: Thursday, 05 November 2020 21:01
Hits: 1266

Probability & Statistics

These 2 go together. Probability is the basic foundation for statistics. It's basic knowledge is needed in a couple of things that we do in AI and in VLSI.

Basic probability:

https://en.wikipedia.org/wiki/Probability_theory

Probability is a number from 0 to 1 => 0 means 0% probability and 1 means 100% probability. Probability of an event is rep by letter "P" => P(event). Sum or integral of probability of all possible outcomes will always be 1.

Discrete Probability Distribution: This is for events that are countable, i.e throwing a dice, tossing coin, etc.

P(X) = 0.4 => Probability of event "X" happening is 40%.

If we roll a dice, then probability of any number 1 to 6 showing up is 1/6. P(dice=1)=1/6, P(dice=6)=1/6

Continuous Probability Distribution: This is for events that occur in continuous space, i.e temperature of water, etc.

PDF: Probability distribution function: When we have a function which is continuous, then instead of having discrete probability number, we have continuous probability function. This is called pdf. Integral of pdf over all possible outcomes will be 1 (just as in discrete case, the sum was 1)

P(x1<x<x2) = ∫ f(x)dx, where f(X) is the pdf, and integral is taken over limits x1 to x2

Factorial:

Factorial is defined as multiplication of all numbers less than or equal to that number. It's denoted by ! mark. So, 3!=3*2*1. 1!=1. n!=n*(n-1)...*2*1

n! = n*(n-1)!.

We define 0! as 1, as that keeps it consistent with other mathematical formulas used in Permutation and Combination shown below. It seems like 0! should be 0, but keeping it 1 allows it to blend nicely with Permutation formula for non-zero numbers.  We'll see that below.

Permutation and Combination:

The most important concept related to probability is figuring out all outcomes that are asked for a given event and divide it by all possible outcomes. As an ex, if probability of getting a 7 on throwing 2 dice is to be calculated, we can calculate as follows:

Number of ways 7 is possible E(sum=7)= (1,6), (2,5), (3,4), (4,3), (5,2) and (6,1) = 6 ways

Total number of possibilities of any number E(any sum) = 6 possibilities of 1st dice (1..6) * 6 possibilities of 2nd dice (1..6) = 6*6 = 36 ways

So, probability of getting 7 = E(sum=7)/E(sum=anything) = 6/36 = 1/6

Number of

Another general probability question is when we have to choose few things out of a given set of things, and we want to know of all different ways of doing it. This is where Permutation/Combination comes in. There are 2 handy formulas that we can use.

This link has very good explanation with the formula at the end: https://www.mathsisfun.com/combinatorics/combinations-permutations.html

  1. Permutation: Here order matters in arranging (P means Position, easy way to remember). ex is 4 digit gate lock code. It's a unique 4 digit code, so order of number matters (i.e 4756 is different than 4567).
    • Repetition not allowed: Given n things, if we have to choose r things, then total number of permutations possible = n*(n-1)*...*(n-r+1) = n!/(n-r)! where ! represents factorial. It's rep as nPr = n!/(n-r)!
      • ex: If we have to choose 3 balls out of 5 different colored balls, it can be done in 5*4*3=5!/2!=60. If we have to choose 1 ball, then it's 5!/4!=5 (as any colored ball can be chosen in every choice). If we have to choose 5 balls, then we can do it in 5*4*3*2*1=120 ways. So, 5!/(5-5)! = 5!/0!= 120 ways. The only way this could be 120 is if we choose 0! as 1. That's why we see in factorial section that 0!=1. If we have to choose 0 balls, then we can do it in 1 way. So, it's 5!/(5-0)! (as there's nothing to choose, so empty set is chosen which is just one way of choosing). So, 5!/5!=1
    • Repetition allowed: Given n things, if we have to choose r things, then total number of permutations possible = n^r
  2. Combination: Here order doesn't matter in arranging. ex is choose 3 socks out of a bag full of socks of different colors. The order in which you take the socks out doesn't matter, as we are concerned only about what color the socks are (i.e "red green blue" is no different than "blue green red").
    • Repetition not allowed: Given n things, if we have to choose r things, then we saw the total number of permutations possible in the above permutation case: It's nPr = n!/(n-r)!. We can easily see that for each set of "r distinct things", we have r! possible permutations. These all need to be grouped into one possibility, since we don't care about different permutations anymore. We are just interested in each such group of "r distinct things". So, we can divide the result by r! to get all combinations possible. So, number of combinations are = n!/((n-r)!*r!). It's rep as nCr = n!/((n-r)!.r!).
    • Repetition allowed: Given n things, if we have to choose r things where things can be repeated and order doesn't matter, then it's not as straight forward as the permutation case. An ex of this would be choosing 3 scoops from 5 flavors of ice cream, where each scoop can be any flavor. How many such combinations exist. One way to solve it would be divide it in 3 diff cases:
      • case 1: all 3 flavors are same => 5 such combinations possible.
      • case 2: 2 flavors are same. Here for each duplicated flavor, the remaining flavor can be one of 4 remaining ones, so 5 possibilities. But each dual flavor itself can be of 5 types, so total possibilities = 5*4=20
      • case 3: all 3 flavors are different. This is case of "repetition not allowed for combination" which is nCr = 5C3 = 5!/(3!*2!)=10
      • So, total number of combinations possible = 5+20+10=35
      • However, we can solve it other way, suggested in link above. We can put circle for each flavor selected and "x" for each time we move to next flavor. So, "x" serves to separate out diff flavors. In this ex, we 'll have exactly 3 circles and 4 "x". So, basically we are looking for all ways of arranging 3 circles in 7 positions.

Problems: Permutation + Combination

One of the biggest confusions in solving permutation/combination problems is to figure out whether the problem is a permutation problem or a combinatorial one. Many times it's not clear, and sometimes it's a mix of the 2. We'll look at some common problems below.

  1. Permutation of identical things: Let's say we have 2 balls, they may be identical or different. We have 5 slots arranged in a line, in which we need to put these balls, with only one ball going into 1 slot. How many ways can we arrange this?
    • 1st case: similar balls: Let's say the balls are of 2 colors = red and blue. First ball has 5 places to go, while 2nd ball has 4 places to go, so total places is 5*4=20 possibilities. This is simple permutation problem. The 3 slots remain empty, and there's no permutation possible amongst 3 empty slots, as empty slots are identical. Formula is nPr where we are placing r different things in n slots.
    • 2nd case: identical balls: Now let's say the 2 balls are identical. So, now we have to see in how many ways can this pair of 2 balls be arranged. The 1st ball can go in 5 places, just like before. 2nd ball can still go in 4 places, but many of the cases are now repeated, as balls are identical.
      • So, let's solve it other way as shown below.
        • Keeping 1st ball in position 1, we have 4 positions for ball 2. => Total ways = 4 ways
        • Keeping 1st ball in position 2, we have 3 positions for ball 2. => We can't put 2nd ball in position 1, as we already covered that case above. Total ways = 3 ways
        • Keeping 1st ball in position 3, we have 2 positions for ball 2. => We can't put 2nd ball in position 1 or position 2, as we already covered those cases above. Total ways = 2 ways
        • Keeping 1st ball in position 4, we have 1 position for ball 2. => On similar lines as above, other cases are already covered. Total ways = 1 way
        • Keeping 1st ball in position 5, we have no more unique places left for ball 2 to go. So Total = 0 ways.
        • So, In total, we get => 4+3+2+1 = 10 ways for the pair of 2 balls to go.
      • There's one other way to solve it. Since we are choosing 2 balls, and the order of balls doesn't matter (since they are identical), of all the 20 possibilities of permutation that we had with red and blue ball, we have to cut it down since red ad blue are same color now. So, this is a "combination" problem, where the order doesn't matter. So, we can divide 20 by 2! since 2! is the number of ways that this Red+blue balls were permutated amongst each other. So, total number of ways = 10. This way is lot easier to understand.
      • So, our formula for this permutation problem uses combinatorial part too.  In short, when having identical things r1, r2, ... rn, etc out of a total of r things, and having n slots, the formula is:
        • nPr / ((r1!)(r2!)...(rn!)) => We just took the permutation part and divide it by factorial of how many identical things we have in each set.

 

Basic Statistics:

https://en.wikipedia.org/wiki/Mathematical_statistics

Satistics is widely used in AI. There is a channel called "StatQuest" on Youtube that I found very helpful on learning basic statistics:

https://www.youtube.com/channel/UCtYLUTtgS3k1Fg4y5tAhLbw

For any sample X, where x1, x2, ..., xn are the individual samples in X, we define various terms that are very important in stats. Let's review these terms:

  • Mean(X) = 1/n * ∑ X  => Mean or average of any sample is sum of all values divided by number of sample points.
  • Variance(X) =  1/n * ∑ (X-Xmean) ^2 => variance is just measuring how far values are scattered from their mean value, on average. So, if X values are close to each other, Var(X) is small. Std deviation is just square root of Variance, i.e std_deviation(X) = σ(X) = √ Variance(X). So, variance(X) = σ2(X). Std deviation is more helpful in practical scenarios, since it represents variation from mean, and NOT the square of variation from mean.
  • Covariance(X,Y) = 1/n * ∑ ( (X-Xmean) * (Y-Ymean) ) => covariance measures joint variance of X and Y (Y is corresponding value for a given X for a set of n samples). Covariance is largest when X,Y move together, and is negative when they move opposite from each other. Covariance is 0, when there is no relation b/w X and Y (i.e X,Y are scattered all over the place). Covariance measures relationship b/w 2 different data, i.e are they related in some way or are they totally unrelated.

 

Central Limit Theorem (CLT):

It is one of the great results of mathematics. It's used both in Probability and statistics. IIt's not going to be used anywhere in our material, but it's good to know this. It establishes the importance of "Normal Distributiion". Theorem is stated in link below:

https://en.wikipedia.org/wiki/Central_limit_theorem