Random Reduction

This one I like a lot.

N_1 = 10^100.
N_2 = random number picked from 1 to N_1.
...
N_k = random number picked from 1 to N_(k-1).

For what k do you expect to see N_k = 1?

Solution:

The following is my solution, passing to using continuous probabilities. It's a little long-winded, so maybe there's a better solution, especially during an interview. Let me know!

Basically, we're applying some random number X of uniform distribution k-1 number of times:

N_k = X_1 * X_2 * ... X_(k-1) * N_1

Dealing with products is tough, so the natural thing to do would be to take the log of both sides:

log (N_k) = log (X_1) + ... + log (X_(k-1)) + log (N_1)

which leads to:

- log (N_1) = Sum{i from 1 to k-1} log (X_i)

The X_i's are independent, so the question now becomes:

Find k such that:

(k-1) E[log(X)] <= -log(N_1)

Where the minus signs are seriously annoying.

So what's E[log(X)], X being a uniform distribution from [0,1]? That's an integration exercise, taking the integral of X*logX from 0 to 1, dX...

which yields a value of -1. Surprising, no?

which means you would expect N_1 by a factor of e every time you multiply it by a uniform random variable. So 100/(1/e) = 100e ~= 271.8.

Add 1 to that and you have k = 272.8, or 273 to take the next greatest integer.

There has gotta be a more elegant solution to this!