Question on random number generator

[mark_yao]

I came across this question on the internet....

Given a R.V. generator of X, which follows a cdf F(x), how to generate a R.V. that follows F(x)^2?

I can think of two methods, i.e. acceptance/rejection, generator a uniform U, inverse the cdf, but these won't use the given generator.

Thanks!

 

[MiloRambaldi]

You need to read the question properly.

How can you generated anything relevant without the given generator? You are not given F(x).

 

[shivgan joshi]

Can you give more details please

 

[MiloRambaldi]

Can you give more details please

Me?? The OP was claiming he had two methods of solving the problem without using the given generator. I was simply pointing out that he has nothing without the given generator. Yes?

 

[jon hd]

if Fx(x), Qx(x) are the CDF and its inverse function for the random sequence of X[n] then to generate a random sequence Y[n] with CDF equal to squared of the original CDF you need to use this mapping:

Y[n] = Qx(sqrt(Fx(X[n])))

considering CDF is non-decreasing:
Fy(x) = P(Y <= x) = P(X <= Qx(Fx(x)^2) = Fx(x)^2

 

[MiloRambaldi]

if Fx(x), Qx(x) are the CDF and its inverse function for the random sequence of X[n] then to generate a random sequence Y[n] with CDF equal to squared of the original CDF you need to use this mapping:

Y[n] = Qx(sqrt(Fx(X[n])))

considering CDF is non-decreasing:
Fy(x) = P(Y <= x) = P(X <= Qx(Fx(x)^2) = Fx(x)^2

Perhaps it is a difficulty with the English? The point made before was that you are not *given* F(x). Now you are assuming you are given both F(x) and Q(x).

 

[jon hd]

Well knowing Fx also means knowing Qx, doesn't it? without knowing Fx, however, I don't think there will be an accurate solution(let me know if you have one, will be pleased to learn). However you can have a solution that will converge to an accurate one but will be heavily erroneous at the beginning, and that is to keep estimating Fx from X[n] samples as they are generated.

 

[MiloRambaldi]

Well knowing Fx also means knowing Qx, doesn't it?

OK.

without knowing Fx, however, I don't think there will be an accurate solution(let me know if you have one, will be pleased to learn). However you can have a solution that will converge to an accurate one but will be heavily erroneous at the beginning, and that is to keep estimating Fx from X[n] samples as they are generated.

That is an approximate solution, but you can do better and you don't need Fx. Hint: Generators are assumed to produce independent sequences of RV's.

 

[pruse]

Why argue instead of just providing a solution?

\(X\sim F(x)\) means that \(P(X\leq x) = F(x)\). Squaring both sides, we may write \(P(X\leq x)P(Y\leq x) = F(x)^2\), where \(Y\sim F(x)\). Assuming that \(Y\) is independent of \(X\), this means \(P(X\leq x \cap Y\leq x) = F(x)^2\). So we just need to find a statement of the form \(f(X,Y)\leq x\) that's equivalent to \(X\leq x \cap Y\leq x\). That's easy: \(\max(X,Y)\leq x\). So the procedure is simply to use your existing generator to generate pairs \(X,Y\) and take their max as the desired r.v.

 

[MiloRambaldi]

Why argue instead of just providing a solution?

\(X\sim F(x)\) means that \(P(X\leq x) = F(x)\). Squaring both sides, we may write \(P(X\leq x)P(Y\leq x) = F(x)^2\), where \(Y\sim F(x)\). Assuming that \(Y\) is independent of \(X\), this means \(P(X\leq x \cap Y\leq x) = F(x)^2\). So we just need to find a statement of the form \(f(X,Y)\leq x\) that's equivalent to \(X\leq x \cap Y\leq x\). That's easy: \(\max(X,Y)\leq x\). So the procedure is simply to use your existing generator to generate pairs \(X,Y\) and take their max as the desired r.v.

Who was arguing?

No one explicitly requested a solution, so I was encouraging the posters to think it out for themselves.

 

[pruse]

If someone posts a problem here, it's usually because they've thought about it all they can, haven't been able to figure it out, and want a solution.

 

[MiloRambaldi]

If someone posts a problem here, it's usually because they've thought about it all they can, haven't been able to figure it out, and want a solution.

If you look at the original post, he hadn't read the question correctly. (Yes I am arguing with you now )

 

[jon hd]

Thanks for submitting the solution, the sequence of \( Y[n] = max\left ( X[2n], X[2n - 1]\right )\) definitely has the required CDF, but it is not a causal solution. While causality is not required by the question, when the input comes from real-word it is a must, otherwise the solution wont be realisable. I wonder whether there can be a similar but causal solution and still without needing to know CDF function, I first thought of \(Y[n] = max\left ( X\left [ n \right ], X[n-1] \right ) \), this is causal but is no longer white, so not a good alternative.

 

[pruse]

Thanks for submitting the solution, the sequence of \( Y[n] = max\left ( X[2n], X[2n - 1]\right )\) definitely has the required CDF, but it is not a causal solution. While causality is not required by the question, when the input comes from real-word it is a must, otherwise the solution wont be realisable. I wonder whether there can be a similar but causal solution and still without needing to know CDF function, I first thought of \(Y[n] = max\left ( X\left [ n \right ], X[n-1] \right ) \), this is causal but is no longer white, so not a good alternative.

Why do we care about causality?

 

[Apa]

pruse

Nice solution Just wanted to ask a couple of questions. The procedure that you used..does it have any specific name?
Also, the function f(X,Y), will it be a unique function every time?

 

[pruse]

Does it have a specific name? No. Is f(X, Y) unique? That's a good question, I'm actually not sure...

Here's another question... We can easily also do (F(x)^3, F(x)^4, ...) using the same approach. Can we also do (F(x)^{\frac{1}{2}})?

 

[jon hd]

Does it have a specific name? No. Is f(X, Y) unique? That's a good question, I'm actually not sure...

Here's another question... We can easily also do \(F(x)^3, F(x)^4, ...\) using the same approach. Can we also do \(F(x)^{\frac{1}{2}}\)?

Intuitively for \(F(x)^{\frac{1}{2}}\) you can do the inverse of what you introduced for \(F(x)^2\), and it is to generate one rv and output it, then keep generating input until it is not greater than the one you just output, and repeat this cycle. A sudo code like this:

#generate new input
a = rv()
 
#generate new input until it is not greater than a                        
while(True):
    b = rv()
    if(b<=a):
        break
output a
output b

This method has indeterministic and variable computational complexity, and it may stalls your system for unlimited amount of time (the peak not the average). Pruse, do you have a better magic solution for this too?

 

[jon hd]

Why do we care about causality?

You don't need to worry about the causality of your solution for this question and in general when your system is not a real-time system. But if for example you generate some data to be used today based on next months' interest rates, your system might look good in theory, but wont be implementable in practice because you don't have your inputs today.

I repeat my question, is there a causal solution to this problem?

 

[Apa]

jon hd Not able to relate why your pseudo code will generate rv's from \((F(x))^0.5 \), could you give some hint. Also another thing, while solving these problems are we not assuming that given F(x) is a cdf then \((F(x))^2\),\((F(x))^0.5 \) will also be cdf's.

 

[pruse]

jon hd Not able to relate why your pseudo code will generate rv's from \((F(x))^0.5 \), could you give some hint. Also another thing, while solving these problems are we not assuming that given F(x) is a cdf then \((F(x))^2\),\((F(x))^0.5 \) will also be cdf's.

You need to put your exponents between curly braces for them to come out right, if they're more than one character long: F(x)^{0.5}.

The only requirements for a CDF are that it be between 0 and 1, and it go to 0 as you go to -infty and go to 1 as you go to +infty. Since powers of F(x) satisfy these conditions they are valid CDFs.