Saturday, October 31, 2009

GATE 1999 CS question 1.1 (Probability)

1.1 Suppose the expectation of a random variable X is 5. Which of the following is true?
(a) There is a sample point at which X has a value 5.
(b) There is a sample point at which X has a value greater than 5.
(c) There is a sample point at which X has a value greater than or equal to 5.
(d) None of the above
First of all, what is this ‘expectation of a random variable’ business?
Well, an ‘expectation’ is a sort of sum – it’s  a ‘weighted’ sum. As a formula, it is
E = summation of xi*pi
where xi are the sample points (different values taken) of the random variable, and pi are the probabilities of each value in turn.
Imagine you were a gambler and also happened to know a dice maker. You tell him to make the dice such that numbers 1 to 4 appear with probability 1/12 each, while 5 and 6 appear with probability 1/3 each (verify that this adds up to a total probability of 1). Now, what is the ‘expected value’ of this dice? Well, as I said, expectation is a weighted sum, with the weights being the probabilities. So here, it would be
E = 1*1/12 + 2*1/12 + 3*1/12 + 4*1/12 + 5*1/3 + 6*1/3
E = 4.5
Ha, what is this, the expected value of the dice roll is 4.5? How can a dice roll a non-integer value?
Well, this mathematical expected value isn’t really the expected value of the dice. Yeah, that’s how strange math is. :)
Intuitively, it’s actually a value we try to find such that the difference between the actual value of the random variable and this value is minimum. Now, since we don’t really know the actual value of the random variable beforehand, we keep this value close to the most probable values while not getting too distant from the other values. That is why we got a 4.5 above – it’s a compromise between the high probability of 5 and 6 and the low probabilities of 1,2,3 and 4.
Ok, that’s about the basics of expectation, now let’s dive into this problem. Here, they say that the expectation of a random variable is 5. Well now, let’s think through the options.
Consider (a). Do we really need one of the sample points to be 5 to get an expectation of 5? What about the expectation of an RV (random variable) that takes values 3,4,6,7 with equal probabilities? By now you must be able to calculate and tell that it’s 5. So, (a) is false.
What about (b) then? Well, that appears about right, doesn’t it? A variable which takes only values 1, 2, 3, and 4 can never have an expectation of 5. Even a variable which takes values 4 and 5 with non-zero probabilities for each can’t have an expected value of 5: 4*(something less than 1) + 5*(something less than 1) can never give you 5, only 5*1.0 gives 5. So, is (b) the answer?
But wait, I said 5*1.0 at the last there, can we make the expectation equal to that? Ah, clever idea. What do we need for that? The ‘summation of xi*pi’ should be just 5*1.0 which means there is only one sample point ‘5’ with probability 1.0. In this case, the expectation is of course 5.
So, it's not necessary that there is a sample point greater than 5 - a single sample point at 5 itself also gives that same expectation. 
So, the answer is (c) There is a sample point at which X has a value greater than or equal to 5.

Thursday, April 9, 2009

GATE 2001 CS question 1.1 (Matrix Algebra)

1.1 Consider the following statements:
S1: The sum of two singular n X n matrices may be non-singular.
S2: The sum of two n X n non-singular matrices may be singular.
Which of the following statements is correct?
(a) S1 and S2 are both true. (b) S1 is true, S2 is false.
(c) S1 is false, S2 is true. (d) S1 and S2 are both false.
This is one problem where getting too theoretical can get you stuck. Instead, let's try to come up with simple examples. The one I immediately thought of for S1 was:



11
11

and


1-1
-11

Both these matrices are singular. What does 'singular' mean? It simply means that the determinant of the matrix is zero (if you don't remember how the determinant of a matrix is found, please see this post). Now, what is their matrix sum? It is:


2
0
0
2

Now quick, what is the determinant value of this one? It's 2 X 2 - 0 X 0 = 4. Clearly, this sum is not 0, so the resulting matrix is non-singular. So, we've proved that S1 is true. The second case is still easier. Let's take the matrices


10
01

and


-10
0-1

Now, both of them have a determinant value of 1, and so they are not singular. What's their matrix sum then?


00
00

Wow! That's very clearly a singular matrix - it's determinant can't be anything other than 0. So, two non-singular matrices can also give a singular matrix on addition. This means that S2 is also true.

So, the answer is: (a) S1 and S2 are both true

Monday, March 23, 2009

GATE 2002 CS question 2.16 (Probability)

2.16 Four fair coins are tossed simultaneously. The probability that atleast one head and one tail turn up is
(a) 1/16 (b) 1/8 (c) 7/8 (d) 15/16

This question is somewhat similar to the 1998 GATE paper's 1.1 question. Please read that one if you haven't yet.

Like there, the total number of combinations consisting of {tail, tail, tail, tail}, {tail, tail, tail, tail, head}, ... {head, head, head, head} comes to 2X2X2X2 = 16.

In case you didn't get how, there are two values for the first toss - head or tail. For each of these values, the second toss can give a head or a tail. So now we have 2X2 = 4 combinations. Extend this to 4 tosses and you can see how 16 came up.

Of these 16 combinations, how many satisfy the condition given in the question? To find that, we have to first understand clearly what the question says.

It asks for "the probability that at least one head and one tail turn up". That means in our result set, all the combinations must have at least one head and one tail.

With a little bit of thought, we'll see that there are many more combinations which do have one head and one tail than those which don't have. So, instead of asking what all combinations have that property, let's now try to find which combinations don't have that property.

Let's take some combination out of the pool: say a combination that has one head alone. When we say it has only one head, it immediately means that the others are all tails. So, it has 'atleast' one head and one tail, so it satisfies the condition. Similar to this case of combinations having only one head, any other combinations that have two heads or three heads also have at least one tail, so they also satisfy the condition.

The case of the combinations having four heads is a curious one. Actually, I must have said combination, not combinations, because there is only one: {head, head, head, head}. In this case, there's no 'at least one tail', which means it does not satisfy the condition. So we have one combination where the condition fails.

So, that's it? Out of 16, one doesn't satisfy it, so 15 satisfy it, so the answer is 15/16.

NO! The condition in the question was symmetric - 'at least one head and tail' - which means the answer will also be symmetric. We talked about the all heads combination, what about the all tails one?

Oooh.. Seems we were about to miss something. The all tails combination too fails the condition. Any other combination has a mixture of heads and tails, so will satisfy the condition.

So, the number of combinations that do satisfy the condition is 16 - 2 = 14. To find the probability of the condition being satisfied, divide the number of cases where the condition is satisfied by the total number of cases. Here it is 14/16 = 7/8.

And so, the answer is: (c) 7/8

GATE 2002 CS question 1.14 (Number systems)

1.14 The decimal value of 0.25
(a) is equivalent to the binary value 0.1
(b) is equivalent to the binary value 0.01
(c) is equivalent to the binary value 0.00111...
(d) cannot be represented precisely in binary
This question must take only half a second if you know how to approach it.
The usual way of converting a decimal fraction to a binary one is to multiply it by 2, take the integer part, rinse and repeat.

Well, here we are not going to use that. Instead, we're going to be clever and use the meaning of number systems.
What is the value of 10 binary? It is 1 * 2^1 + 0 * 2^0. That is, we use decreasing powers of 2 as we move right.

Now, what is 0.1 binary? It is 1 * 2^(-1) which is 1/2. Similarly, 0.01 is 1 * 2^(-2) = 1/4 = 0.25.

Hey, haven't we arrived at the answer then? If 0.01 binary is 0.25 decimal, the answer we need is 0.01.

Yes, but there's something more we can learn here: if you manage to write any fractional value as the sum of 1/(powers of 2), you can directly write down its binary value. In some cases this might prove to save a lot of time. For example, if you asked to find the binary value of say 0.375, we see that it can be written as 0.25 + 0.125, so the answer is 0.011.

In this case, no such splitting was necessary. So, the answer to this question is: (b) is equivalent to the binary value 0.01