Thursday, January 17, 2013

Answer to the previous blog

If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.

Suppose there are n lightbulbs, k of them have defects. A technician is allowed to check m lightbulbs and it turns out that exactly l defected ones among those checked.
  1. Given n,k,m,l, what is the probability mass function (PMF) for l? What is the expected value?
  2. Given n,m,l, what is the probability mass function (PMF) for k? What is the expected value?
(Sorry that I have to change the notations, so the presentation is clearer.)
Answer:
  1. Probability is (number of particular outcomes)/(number of all possible outcomes).
    • k≥n: In this case 0≤l≤m. The total number of ways for choosing m bulbs from the n bulbs is $C_m^n$. Number of ways that there are l defected bulbs among m chosen bulbs equals $C_l^kC_{m-l}^{n-K}$. Therefore the conditional probability for $L=l$ given $K=k$ is $$P(L=l|K=k)=\frac{C_l^kC_{m-l}^{n-k}}{C_m^n}.$$ Interestingly, rearranging the terms, we have (what does it mean?) $$P(L=l|K=k)=\frac{C_l^mC_{k-l}^{n-m}}{C_k^n}$$ The expected value equals the sum of (outcome × probability). Therefore $$E[L|K=k]=\sum_{k=0}^m\frac{lC_l^kC_{m-l}^{n-k}}{C_m^n}.$$
    • k≤n: In this case 0≤l≤k. Again $$P(L=l|K=k)=\frac{C_l^kC_{m-l}^{n-k}}{C_m^n}.$$ The expected value is $$E[L|K=k]=\sum_{k=0}^k\frac{lC_l^kC_{m-l}^{n-k}}{C_m^n}.$$
  2. Indeed there is something missing in the question: How is k distributed? Lets assume that it is K~Bin(N,p), that is, each bulb has a probability p to be defected and that $P(K=k)=C_k^np^k(1-p)^{n-k}$. Therefore $$P(K=k|L=l)=\frac{P(Y=K, L=l)}{P(L=l)} =\frac{P(K=k)P(L=l|K=l)}{\sum_{k=l}^nP(K=k)P(L=l|K=k)}$$ and $$E[K|L=1]=\frac{kP(K=k)P(L=l|K=l)}{\sum_{k=l}^nP(K=k)P(L=l|K=k)}.$$

The second question:
Suppose there are n lightbulbs, k of them have defects. A technician is allowed to check m lightbulbs. What is the probability that he can find out all the defected?

Answer: The technician can find all the defected bulbs if either all the defected bulbs or all the normal bulbs are among those checked. Therefore the answer is $$P(\mbox{he finds all})=\begin{cases} \frac{C_{m-k}^{n-k}}{C_m^n} & n-k>m>k \\ \frac{C_{m-k}^{n-k}+C_{m-(n-k)}^k}{C_m^n}& m\ge n-k,k \\ \frac{C_{m-(n-k)}^k}{C_m^n} & k>m>n-k \end{cases}$$

Tuesday, January 15, 2013

A probability question

If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.

Suppose there are N lightbulbs, K of them have defects. A technician is allowed to check n lightbulbs and it turns out that exactly k defected ones among those checked.
  1. Given N,K,n, what is the probability mass function (PMF) for k? What is the expected value?
  2. Given N,n,k, what is the probability mass function (PMF) for K? What is the expected value?

A somewhat similar question is:
Suppose there are N lightbulbs, K of them have defects. A technician is allowed to check n lightbulbs. What is the probability that he can find out all the defected?

Monday, January 7, 2013

Subtraction of Numbers

If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.

Many many years ago, when I first encountered the computer algorithm for subtraction of numbers, I really do not know what happens.
Several days ago, I have read an article saying that the primary school kids, who are okay to do additions, face difficulties in subtractions.
The two problems seems unrelated, but they are really the same problem.
Addition is easy, subtraction is hard, for computers and kids alike!

Lets review how a computer do base 2 addition:

To add two numbers, with fixed length, say (01001101)+(00011101). We need three memory units: N1 to hold a digit for the first number, N2 to hold a digit for the second number, C to hold a carry digit.

Step 1. Load the last digit of the first number to N1, the last digit of the second number to N2, 0 to C. Then do the following operation:
N1N2CResult Digit and new C
0000, 0
0011, 0
0101, 0
0110, 1
1001, 0
1010, 1
1100, 1
1111, 1
(Basically, it means N1+N2+C=(new C, Result Digit).)
In our example, N1=1, N2=1, C=0, so the result is 0 and new C=1.

Step 2. Load the next digit (on the left side) of the first number to N1, the next digit of the second number to N2. Again follow the table above.
In our example, N1=0, N2=0, C=1, so the result is 1 and new C=0.

Step 3-Step 8. Repeat Step 2.
In our example, it is
  • N1=1, N2=1, C=1: result is 0, new C=1
  • N1=1, N2=1, C=1: result is 1, new C=1
  • N1=0, N2=1, C=1: result is 0, new C=1
  • N1=0, N2=0, C=1: result is 1, new C=0
  • N1=1, N2=0, C=0: result is 1, new C=0
  • N1=0, N2=0, C=0: result is 0, new C=0
The final answer, reading all the results backwards, is (01101010)

Looks fancy, but it is just how we do addition. Now, for subtraction.

Lets use the same two numbers: (01001101)-(00011101).

Step 1. Change the second number, switch 0 and 1, so it becomes (11100010).

Add the first number and the new second number: (010001101)+(11100010)=(00101111).

Add the answer by (00000001), and we get the answer (00110000).

Why does it work?
Because we are not doing really the usual addition and subtration, we are doing modulo arithmetic!!!

We say that m=n (mod R) is m-n is divisible by R. If we are doing arithmetic under this equivalence relation, we are doing modulo R arithmetic, or ZR-operations.
For example, in modulo 3 arithmatic, we have
+012
0012
1120
2201
×012
0000
1012
2021
The computer arithmetic is simply doing modulo 28 arithmetic. Therefore
(01001101)-(00011101)
=(001001101)-(000011101)
=(001001101)-(000011101)+(100000000)
=(001001101)-(000011101)+(011111111)+(000000001)
=(001001101)+(011100010)+(000000001)
=(01001101)+(11100010)+(00000001)

It explains the algorithm.

Now I wish to propose a new subtraction algorithm for kids, using the same idea.

Say, we want 19021-8742.

Rewrite the second number as 08742, then switch using 0<->9, 1<->8, 2<->7, 3<->6, 4<->5. The new number is 91257

Add the first number and the new number, ignore the leftmost digit: 19021+91257=10278.

Add 1, the final answer is 10279.

Lets try two more. 24311-13904 and 34052-23016.

24311
-13904
======
24311
+86095
------
10406
+ 1
------
10407
34052
-23016
======
34052
+76983
------
11035
+ 1
------
11036