Suppose f(n) produces a random natural number in [1, n] with uniform distribution.

Find P(f(f(n)) = x)

Given you're asking this question I"m going to assume you have some basic knowledge of probability / notation used therein. LMK if you spot errors / have questions.

Let X ~ U(1,n) ##X is a random variable that is uniformly distributed across the integers [1,n]
Let Y | X = x ~ U(1,x).

Then, the density of Y (which tells you P(Y = y) = P(f(f(n)) = y)), (note I'm using y here while u used x but the exact symbol doesn't matter) is easily found using law of total probability:

P(Y = y) = \sum_{i=1}^n P(Y = y | X = x) P(X = x) ##law of total probability, note I'm using latex parlance to write the sums which may not register on jsp
= \sum_{i=1}^n (1/x) * (1/n) ##since the random variables above have uniform distributions
= (1/n) \sum_{i=1}^n (1/x)

I'm sort of confident the above answer is correct. However, it's a bit weird since \sum_{i=1}^n (1/x) doesn't have a closed form solution. You could write P(Y = y) = H_n/n where n is the nth harmonic number and that would be "correct". You could also leave it as is and that would be correct as well (assuming I didn't do something wrong). This expression is close to log(n)/n as well so that could be a nice approximation. Could be wrong so double check / think about this. Does the above density sum to 1?

Please gib fg

This post was edited by ogsarticuno on Jan 8 2019 03:09pm

since P(Y = y | X = i) = 0 as soon as i < y.

Does it seem better like that ?

Also it's possible to replace your 'y' by the original 'x' :

P(Y = x) = \sum_{i=1}^n P(Y = x | X = i) P(X = i)
= \sum_{i=x}^n (1/i) * (1/n)
= (1/n) \sum_{i=x}^n (1/i)

And indeed, it sums to 1 (ouf !) :

Let S = sum_{x = 1}^{+infinity} P(Y = x).

S = sum_{x = 1}^n P(Y = x) since P(Y = x) = 0 as soon as x > n
S = sum_{x=1}^n (1/n) sum_{i=x}^n (1/i)
S = sum_{i=1}^n sum_{x=1}^i 1/(ni)
S = sum_{i=1}^n i/(ni)
S = sum_{i=1}^n (1/n)
S = n * (1/n)
S = 1

my brain .....

yeah this is what i got except offset a little

fun problem



This post was edited by otay on Jan 8 2019 11:58pm

im a bit rusty, so i struggled to follow along tbh

Your answer is correct. And it's exactly the same as above : in your final sum, just let k = n - i
When i is an integer from [0,n-x], then k belongs to [x,n] and your sum looks like :
(1/n) sum_{k=x}^n (1/k)

Did you write the text above yourself ? Then you have a beautiful writing !

yeah, thats what i meant



well thanks