Great Expectations!

Came across this cool question the other day.

If X and Y are Uniform(0,1) random variables, what is E[X/(X+Y)]?

Direct calculation of the expectation as a double integral turns out to be a bit nasty.

But there is a trick.

X/(X+Y) + Y/(X+Y) = 1

=> E[X/(X+Y)] + E[Y/(X+Y)] = 1

Since X~Y, both the expectations above are equal since they are symmetrical in X and Y.

Thus each equals 1/2.

And we are done!

Corollaries:

Now it is easy to calculate the following (X, Y, Z ~ U(0,1) )


E[X/(X+Y+Z)] = 1/3
E[XY / (XY + YZ + ZX)] = 1/3

and so on!

Question:
Would the results be the same if X, Y, Z were iid but from another distribution?

Proverbial Mathematics or
Mathematical Proverbs

We have lots of proverbs and quotes which are almost like logical implications. For example,

It is always darkest before the dawn

Mathematically, this translates to:

Dawn => darkest just before

which doesn't necessarily mean

darkest => dawn next

as, one would think, the original proverb is supposed to imply :-)

Another pair of quotes we have are:

All that glitters is not gold (NOT(glitter => gold))
Not all that is gold glitters (NOT(gold => glitter))

meaning gold and glitter are completely "independent" :-)

Can you think of some other similar ones?

Here is something a bit non-conformant to this blog.

The other day I came up with the following GMAT-type data sufficiency question:

What is the value of xy ?

(1) x^2 + y^2 = 0

(2) x + y = 5

[You need to determine whether (1) alone is sufficient to find out the value of xy or (2) alone is sufficient, both (1) and (2) are needed, both (1) and (2) are independently sufficient or neither is sufficient.]

Now this is a tricky question.

The 'obvious' approach is to square (2) and substitute (1) to get:

x^2 + y^2 + 2 x y = 25

=> 2 x y = 25

=> xy = 12.5

So you would say that both (1) and (2) are necessary to determine the value of xy. After all, there are two variables and don't you need two equations?

Not in this particular case!

Look closely at (1): x^2 + y^2 = 0. The sum of two squares equal zero. When can this happen? Remember that squares are non-negative. So the only way to add two squares and get zero is if both of them are individually zero, which means both x=0 and y=0! So obviously, xy = 0!

So the correct answer is only (1) alone is sufficient!

So what went wrong in our earlier calculation? Here we assumed that both (1) and (2) are correct. In fact, because of the above reasoning, (1) and (2) together constitute an inconsistent system of equations. (Can you prove it?)

[P.S. Thus, at the expense of increasing the degree and the number of potential roots, any set of simultaneous equations (for real variables) can be converted into a single equation by squaring them and equating the sum to zero.

E.g. if p(x, y, ...) = 0, q(x, y,...)=0, r(x, y,...)=0 are the equations, the single equation would be

p(x,y,...)^2 + q(x, y,...)^2 + r(x, y,...)^2 = 0]

Identity Crisis

From high-school mathematics, we all know the complex cube roots of unity. Now here is a question:

How about cube roots does the identity matrix have?

Now, first of all let me define cube root of a square matrix. C is a cube root of A if C X C X C = A.

Of course, this seems like an obvious definition, but there are sophisticated definitions of what a cube root of a matrix is. For our purposes, let us stick with the simple definition.

And for simplicity, let us consider 2x2 matrices.

Clearly, the Identity Matrix is its own cube root.

But are there any others?

It depends on what all types of entries you allow in the matrix.

Consider the general case of a 2x2 matrix of complex numbers.

Now, I used Mathematica to find the following cube roots. Here is a cube root of (-1)  and c stands for any number.

Can you come up with some more?

(Hints: If A is a cube root of the identity what can you say about its transpose? What about its conjugate? Its inverse, if it exists?)

Climbing Trees and Solving Puzzles

Here are some cool puzzles where thinking using binary trees helps solving them easily.

Puzzle 1:

What is the minimum number of comparisons required to sort three distinct numbers?

Solution:

There are six ways of arranging three numbers and one of these six will have the numbers sorted in the correct order.

The comparisons can be drawn up as a binary tree. Each comparison gives us two possible outcomes. So we need at least n comparisons where 2^n >= 6. It is easy to see that 3 is that n.

(And the straightforward, obvious algorithm shows that indeed 3 comparisons are sufficient.)

Puzzle 2:

There are three switches, all in the off position. One of these is connected to a light bulb upstairs. You have to determine which switch operates the bulb. The catch is that you can go upstairs and check only once. How do you do it?

Solution:

For sure this is an interesting question. Let us see what our tree analysis can tell us about this.

Now there are three possible outputs - switch 1, 2 or 3. The light bulb can be in two states - on or off. That does not give us enough states to point to three outputs. (2^1 = 2 < 3).

Based on our tree analysis, we need at least 2 states to nail down the switch.

So right away you can see that just by checking if the bulb is on or off you are not going to be able to determine the light switch.

So what other state information can the bulb provide? How about time? If the bulb was on for longer versus for a shorter time?

Possible, but you can't really look at a light bulb and say how long it has been on.

But, you can touch it and tell - yes, by how hot it is. (Okay, there are limits to how accurately you can measure the heat and how long interval you can measure. If you leave the bulb on for a long time, it comes into thermal equilibrium and doesn't get any hotter.)

Now you have two states, on/off and hot/cold. And indeed you can find out which switch operates the bulb.

1. Turn on switch 1. Keep for 5 min. Turn off switch 1.
2. Turn on switch 2.

Go upstairs and check.

1. If bulb is on, switch 2 operates it.
2. If bulb is off and hot, switch 1 operates it.
3. If bulb is off and cold, switch 3 operates it.

Now comes the teasers. Can we use a similar algorithm if there were four switches? Theoretically, we have enough number of states to make that determination.

What say?

Puzzle 3:

How many straight cuts are required to cut a cube into 27 smaller cubes, in a 3x3x3 array as in a rubik's cube? A straight cut is defined as a single, simple cut with a knife where the knife edge moves in a straight line. You are allowed to rearrange the pieces between cuts.

Solution:

Each straight cut can create two pieces. So in order to create 27 cubes, we need at least n cuts where 2^n >= 27. So we need at least 5 cuts.

But is 5 sufficient?

We know the "obvious" way of cutting the cubes in 6 cuts - two parallel to each axis.

So we know that the answer is between 5 and 6 cuts.

In order to resolve this, we notice that each cut also exposes two new surfaces.

Consider the innermost cube - it has 6 fresh cut surfaces. And since only straight cuts are allowed, we need 6 cuts to create this cube.

Thus the answer is 6.

How Far Can You Go?

This morning I was ruminating about taking a math class.
And due to whatever reason I started thinking about maximal convex subsets.

What is it, actually?
It is a convex subset of a set that is maximal. That is, if you add any more points to this subset from the parent set, it becomes concave.

Now, it is trivial to say that if a convex set is its own maximal convex subset. And it is trivial to go one more step to say that a convex set has only one maximal convex subset (itself).

How about the converse of this "Theorem"?
If a set has only one maximal convex subset, is the set necessarily convex? Intuitively, the answer seems yes. But how do you prove it?

Now consider a non-convex set. How many maximal convex subsets does it have?

Consider the L-shaped set below:

 
It is easy to see that it has two maximal convex subsets:

But is that all?

Probably not! What about this one?

 

Or even this one?

It seems that there are an infinite number of maximal convex subsets for this L-shaped set.

In fact, any straight line passing through the corner of the L defines a maximal convex subset - the first two were just special cases of this.

Aiming for Perfection

Here is a post after a long time.

The other day I came across list of unsolved problems one of the 'problems' was to study the sequence of square complements. So I thought, let us see how far we can get.

A square complement of a number is any number when multiplied to the original number results in a perfect square. e.g. 3, 12, 27, 48 are all square complements of 12.

The least of such numbers is called the least square complement (LSC) of the number. (Some authors call this just the square complement. For our analysis below, we distinguish between these two.)

Now the sequence of least square complements go like this:

1, 2, 3, 1, 5, 6, 7, 2, 1, 10, 11, 3, 13, 14, 15, 1 etc.

So what? How do we analyze them?

Here are some observations:

1. The least square complement of a perfect square is 1.
2. The least square complement of a number cannot be greater than the number itself. This is because any number is its own square complement.
3. The least square complement of a number has to be square free; i.e. it should not have any divisor that is a perfect square. If this were not the case, we could easily factor out the square part and still get a square complement.
4. The least square complement of a number must be one of its divisors. (Prove it!)
   
5. Therefore, a prime is its own least square complement.
6. Therefore, the sequence of least square complements diverges. As we all know the primes are infinite and since we can find a prime however large, we can find a least square complement however large (itself).

So far so good.

Let us approach this from another direction.

Define SC(n) = {m | m is a square complement of n}

Now an interesting thing to note is that the product of any two members of SC(n) is a perfect square. It is easy to see that "is a square complement of" is an equivalence relation.

Now every integer m belongs to at least one SC(n), in particular to SC(m). So the SCs cover the set of integers. Now are they mutually exclusive?

Let m belong to both SC(s) and SC(t). Let r be another member of SC(s).

Now, m.s = square. m.t = square. r.s = square, by our assumptions. Based on above, r.m is also a square.

Consider m.m r.t = r.m m.t = square. square = square.
So square . r.t = square. Therefore, r.t should also be a square.

So SC(s) = SC(t).

Thus the SCs partition the set of integers.

Can we have a look at them? Most certainly! Here they go:

SC(1) = {1, 4, 9, 16, 25, ... }, set of perfect squares
SC(2) = {2, 8, 18, 32, 50, .....}, twice the perfect squares
SC(3) = {3, 12, 27, 48, 75, ....}, three times the perfect squares
SC(5) = {5, 20, 45, 80, 125, ...}, five times the perfect squares
SC(6) = {6, 24, 54, 96, 150, ...}, six times the perfect squares

Hey, is there a catch? Is SC(n) always n times the perfect squares?

Yes, that is true as long as n is square free.

Here is why.

The fundamental theorem of arithmetic says that each number has a unique factorization. So each number can be represented by an infinite vector of non-negative integers, which correspond to the prime powers in the factorization.

n = (a1, a2, .....)

For example, 24 = (3, 1, 0, 0, ....) = 2^3 * 3

Now a perfect square will have all ai's even.

The least square complement of a number is just the number that makes the ai's even.

LSC(n) = (a1 mod 2, a2 mod 2, ....)

For example, LSC(24) = LSC(3, 1, 0, 0, ...) = (1, 1, 0, 0, ..) = 6.

Let m = (b1, b2, ....) be a square complement of n = (a1, a2, ....). This means that b1+a1 is even, b2 + a2 is even, etc.

Now bi = ai mod 2 + (bi - ai mod 2). You can verify that (bi - ai mod 2) is even since ai + bi is even. So every square complement can be written as a product of the least square complement and a perfect square.

Now all this didn't really address the original question of studying the sequence of least square complements. All we know so far is that the sequence diverges but it grows no faster than n.

Since the primes do not seem to follow a particular pattern, it can be expected that the least square complements also don't since they match at the primes.

How about the average of the least square complements?

I tried to run some simulation in excel and found that the average of the averages seems to be constant. I do not have a proof though.

Any ideas?

Palindromes in a Linked List

The other day I came across the following question:

Write a simple program for a Turing machine that can identify if a string of 0's and 1's on the tape is a palindrome or not.

I was discussing this with my friend who is an electronics engineer and who works with state machines a lot. Soon, our conversation turned into how would one solve the problem if the numbers were in a linked list.

I went home and thought about the problem.

There is the obvious O(n^2) solution:

1. Read the head
2. Go all the way to the tail
3. Compare.
4. Read the second item
5. Go all the way to tail - 1
6. Compare
7. And so on

Obviously, it is constant memory. But is there any way we could do it in O(n)?

Now, one fact that we didn't use is that the values in the linked list are 0's and 1's. Can this be used to our advantage?

I guess we can - if we encode the string into an integer.

So here is the revised algorithm:

1. Find the number of elements in the linked list - O(n)
   
2. Read half the number of elements and find the number (n) represented by the 1's and 0's
   
3. Read the remaining elements and pop the digits from n and compare the values

Now what if the linked list could have any kind of values?