Swapping

Write a one liner in C/C++ for swapping 2 integers.


Solution:

void swap(int &a, int &b) {
a^=(b^=(a^=b));
}

^ is the bitwise XOR operator. Yeah, it looks like magic... but it's actually not too tough to figure out once you get the gist of the idea. It's tricky, definitely.

Rainy Day

The probability of it raining on Saturday is 60%, on Sunday 30%. What's the range of probability that it doesn't rain over the weekend?


Solution:

Doesn't rain on Saturday: 40%. Let this be event A.
Doesn't rain on Sunday: 70%. Let this be event B.

If the two events are independent: 28%.
Else: P(A & B) = P(A intersect B).
min P(A intersect B): clearly 10%.
max P(A intersect B): clearly 40%.

So the range is 10% to 40%.

Conditional Expectation

X is taken from [0,Pi]. What is E[X | sin X] ?

Solution:

Tests the understanding of conditional expectations.

First off, E[X|sin X] is a function, namely E[X|sin X] is E[X|sin X=y](y).

Figure out the sigma algebra generated by sin X. The interval [0,Pi] is our sample space, so sin X belongs to [0,1]. So sigma(sin X) is gonna be some Borel subset of the complete Borel set on [0, Pi].

The elements of this generated Borel subset are symmetric about Pi/2--for instance, take sin X = 0.5 --> X belongs to {Pi/6, 5*Pi/6}. This is evident, just graph sin X over [0, Pi]. So,

E[X|sin X=Y for any Y] = E[ X belongs to a set that is in the borel sets symmetric around Pi /2 ] = Pi/2.

which is independent of Y, the constant function Pi/2.

Maximizing Variance

X is an r.v. from the interval [0,1]. What's the maximum variance for X?


Solution:

Intuitively, you'll guess it's 1/4--just binomial from {0,1}. The proof:

Instead of looking at the interval [0,1], let's look at the inter [-1/2, 1/2]. This does not change the variance properties. We have Var[X] = E[X^2] - E[X]^2 <= E[X^2] <= 1/4. So the upper bound is 1/4. Can the upper bound be reached? Sure, take bionomial from {-1/2, 1/2}.

Flipping Coins

There's a machine that keeps flipping two unbaised coins at once (i.e. 4 possible outcome per operation). Two guys, A and B. A wins if a (H,H) combination comes up. B wins if two consecutive (H,T) combinations come up (by (H,T) I mean one head and one tail from either of the coins). What's the probability of A winning?



Solution:

This one is tricky is you condition by when the game ends, because the states get mangled up. Easier is to do the following.

Let P(A) be the probability that A wins. Then, we have:

P(A) = 0.25 + 0.5 * (0.25 * 1 + 0.5 * 0 + 0.25 * P(A) ) + 0.25 * P(A)

explanation:

1st term on right: 0.25: Prob of (H,H)
2nd term on right: if either (H,T) or (T,H), which has prob 0.5, A wins if (H,H) (0.25 prob), loses if either (H,T) or (T,H) again (0.5 prob), or the game essentially resets if (T,T), (0.25 prob).
3rd term on right: if (T,T), game essentially restarts, since (T,T) doesn't help B.

Solving for P(A) we get 60%.

Probability

Given n uniform random variables that takes value between 0 and 1, what is the probability that they sum up to less than 1?


Solution:

If you think about it, it's just the volume of the n-dimensional triangle. That volume would be 1/n!, hence the 1/n! is the answer.