# Question on random number generator

#### jon hd

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.
Apa, the answer is not correct, because a and b in the pseudo code are not independent, so the result sequence wont meet the requirements of squaring CDF by outputing max of pairs. Basically I was trying to generate a random sequence in a way that max of its pairs generate a random sequence similar to X. The solution meets this condition, but as I said itself's not a white sequence. See whether other can post a solution.

#### pruse

Yeah, I don't yet have a solution for $$F(x)^{\frac{1}{2}}$$. It may be that a solution doesn't exist.

#### MiloRambaldi

Yeah, I don't yet have a solution for $$F(x)^{\frac{1}{2}}$$. It may be that a solution doesn't exist.
I doubt it exists but that is a problem for useless pure mathematicians.

You can get an arbitrarily close approximation, without knowing F(x).

Hint: What is the Fourier expansion of $$x^{\frac12}$$ about 1?

#### pruse

I doubt it exists but that is a problem for useless pure mathematicians.

You can get an arbitrarily close approximation, without knowing F(x).

Hint: What is the Fourier expansion of $$x^{\frac12}$$ about 1?

Useless pure mathematicians, eh?

#### MiloRambaldi

Useless pure mathematicians, eh?
Umm, yes. You think they do something useful?

You're welcome for the solution, btw.

#### pruse

Umm, yes. You think they do something useful?

You're welcome for the solution, btw.

I'm sensing some envy here. My sense is you're poorly endowed and dream of being bigger and badder. But you can't have everything. Sorry about that.

#### MiloRambaldi

I'm sensing some envy here. My sense is you're poorly endowed and dream of being bigger and badder. But you can't have everything. Sorry about that.
??? "Poorly endowed". You're completely ignorant, since you know nothing about me. What are your accomplishments in pure mathematics anyways?

You've also failed to acknowledge my solution, or stay on topic by discussing it further.

#### pruse

??? "Poorly endowed". You're completely ignorant, since you know nothing about me. What are your accomplishments in pure mathematics anyways?

You've also failed to acknowledge my solution, or stay on topic by discussing it further.

Yes, you've got it right, you're quite the quick study, aren't you... only a poorly endowed individual such as yourself would hide behind an alias to insult other people. The fact that you use an alias shows you're uncomfortable being yourself, and you dream of being someone else, someone endowed with more talents. Your solution was not a solution, btw, but I'm sure some people here would like to see you attempt to explain why you think it works.

#### MiloRambaldi

... hide behind an alias...
I'm afraid the irony was lost on you.

pruse said:
Your solution was not a solution, btw, but I'm sure some people here would like to see you attempt to explain why you think it works.
You are implying that my hint of how to solve your (very nice I must say) problem was incorrect. But I assure you it is. I said that you can obtain approximations arbitrarily close to the solution. Formally:

Claim. There is a transformation mapping any real-valued random variable $$X$$ to a sequence $$\{Y_n(X)\}$$ of random variables that converges in distribution to a random variable $$Z$$ with $$F_Z=F_X^{\frac12}$$, i.e. $$F_{Y_n(X)}(x)\to F_X^{\frac12}(x)$$ for all points $$x$$ of continuity of $$F_X$$.

I won't give a formal proof, but I will explain how to construct the sequence. Consider the Taylor expansion of $$x^{\frac12}$$ about~1:
$$x^{\frac12}=1+(x-1)/2-1/8 (x-1)^2+1/16 (x-1)^3-5/128 (x-1)^4+7/256 (x-1)^5+...$$
We want to apply the identity $$F_{-X}(x)=1-F_X(-x)$$, so we make the following rearrangement:
$$1-x^{\frac12}=\frac12(1-x)+\frac18(1-x)^2+\frac1{16}(1-x)^3+\frac{5}{128}(1-x)^4+...(*)$$
Note that the coefficients sum to 1. Given $$X$$, here is how to construct $$Y_4(X)$$ for example: Let $$A$$ be a random variable with
$$P[A=1]=\frac12$$,
$$P[A=2]=\frac18$$,
$$P[A=3]=\frac1{16}$$,
$$P[A=4]=\frac5{128}$$
(everybody has a $$U[0,1)$$ generator, or this can be approximated by coin tossing).
Take $$1+2+3+4=10$$ samples from $$-X$$. Then we can obtain independent $$B_1,B_2,B_3,B_4$$ with cdf's $$1-F_{X}(-x),(1-F_X(-x))^2,(1-F_X(-x))^3,(1-F_X(-x))^4$$, by taking the corresponding maximums, as we saw in previous posts. Define $$Y'_4$$ by
$$Y'_4=B_1$$ if $$A=1$$,
$$Y'_4=B_2$$ if $$A=2$$,
$$Y'_4=B_3$$ if $$A=3$$,
$$Y'_4=B_4$$ if $$A=4$$,
$$Y'_4=0$$ otherwise.
Then the cdf of $$Y'_4$$ is approximately the right-hand side of (*) with $$x:=F_X(-x)$$. Therefore the cdf of $$Y_4=-Y'_4$$ is approximately $$F_X^{\frac12}$$ by (*).

#### pruse

You actually know some non-trivial math; I'm mildly impressed. What I was referring to, though, was not a series of approximations, which isn't hard to come by, but an exact solution. Still, nice job, you've partially redeemed your previous inane comments.

#### MiloRambaldi

You actually know some non-trivial math; I'm mildly impressed. What I was referring to, though, was not a series of approximations, which isn't hard to come by, but an exact solution. Still, nice job, you've partially redeemed your previous inane comments.

You are a poor sport, by trying to minimize my contribution which I made at your request; everyone knows we have been talking about an approximation all along.

You make a claim that series of approximations to distributions are not "hard to come by". Can you point me to any textbook or scientific literature where this is described (I am honestly interested)? Apparently you lack the mathematical depth to properly understand the solution: For example: (1) What if we had expanded about some other number than 1? (2) I was also thinking about: what if we take some other increasing transformation than sqrt(x) of [0,1] to [0,1]? sqrt(x) has special properties, which I did not spell out, that make the above approximation work. x^a is fine, but typically copying this approach will fail.

#### pruse

You are a poor sport, by trying to minimize my contribution which I made at your request; everyone knows we have been talking about an approximation all along.

You make a claim that series of approximations to distributions are not "hard to come by". Can you point me to any textbook or scientific literature where this is described (I am honestly interested)? Apparently you lack the mathematical depth to properly understand the solution: For example: (1) What if we had expanded about some other number than 1? (2) I was also thinking about: what if we take some other increasing transformation than sqrt(x) of [0,1] to [0,1]? sqrt(x) has special properties, which I did not spell out, that make the above approximation work. x^a is fine, but typically copying this approach will fail.

It really does not take "mathematical depth" to understand your solution or to recognize why one should expand about 1, so relax, you sound like a narcissist.

Speaking of being a poor sport, I believe it was you who came in here treating everyone with an air of superiority right off the bat.

#### MiloRambaldi

It really does not take "mathematical depth" to understand your solution or to recognize why one should expand about 1, so relax, you sound like a narcissist.
You are correct that the solution is not that difficult to understand.

The reason I said that you apparently lack mathematical depth is because you claim that approximations of distributions are not hard to come by (presumably you meant the type of approximation we are discussing here). You did not give any references, nor could I find anything (doing a google search) in the literature that entails this approach.

Just to test your understanding: What are sufficient conditions on the transformation (e.g. sqrt(x)) for the method to work?

Speaking of being a poor sport, I believe it was you who came in here treating everyone with an air of superiority right off the bat.

You believe wrong, and you have made many false statements in this threads. Are you a pure mathematician? I had assumed most people here are quants.

#### pruse

You are correct that the solution is not that difficult to understand.

The reason I said that you apparently lack mathematical depth is because you claim that approximations of distributions are not hard to come by (presumably you meant the type of approximation we are discussing here). You did not give any references, nor could I find anything (doing a google search) in the literature that entails this approach.

I was referring to this problem, of course, not approximations of distributions in general. Just staying on topic, that's all.

I know plenty of pure mathematics, but I consider myself a problem solver rather than a mathematician. And yes, I am also a quant. Anyhow, I found it ignorant of you to call pure mathematicians "useless," since clearly a lot of applied mathematics was made possible by the work of pure mathematicians. E.g., Fermat and Pascal set the stage for probability theory.

#### MiloRambaldi

I was referring to this problem, of course, not approximations of distributions in general. Just staying on topic, that's all.

So you were saying that it is easy to find a (arbitrarily close) distribution approximating sqrt(F_X).

I'm no expert on approximating distributions, but I couldn't think of any good alternative solution.

The only thing that comes to mind is approximating F_X empirically, as jon hd originally suggested, and applying numerical methods. However, this can be highly impractical for certain distributions.

#### quotes

I'm afraid the irony was lost on you.

You are implying that my hint of how to solve your (very nice I must say) problem was incorrect. But I assure you it is. I said that you can obtain approximations arbitrarily close to the solution. Formally:

Claim. There is a transformation mapping any real-valued random variable $$X$$ to a sequence $$\{Y_n(X)\}$$ of random variables that converges in distribution to a random variable $$Z$$ with $$F_Z=F_X^{\frac12}$$, i.e. $$F_{Y_n(X)}(x)\to F_X^{\frac12}(x)$$ for all points $$x$$ of continuity of $$F_X$$.

I won't give a formal proof, but I will explain how to construct the sequence. Consider the Taylor expansion of $$x^{\frac12}$$ about~1:
$$x^{\frac12}=1+(x-1)/2-1/8 (x-1)^2+1/16 (x-1)^3-5/128 (x-1)^4+7/256 (x-1)^5+...$$
We want to apply the identity $$F_{-X}(x)=1-F_X(-x)$$, so we make the following rearrangement:
$$1-x^{\frac12}=\frac12(1-x)+\frac18(1-x)^2+\frac1{16}(1-x)^3+\frac{5}{128}(1-x)^4+...(*)$$
Note that the coefficients sum to 1. Given $$X$$, here is how to construct $$Y_4(X)$$ for example: Let $$A$$ be a random variable with
$$P[A=1]=\frac12$$,
$$P[A=2]=\frac18$$,
$$P[A=3]=\frac1{16}$$,
$$P[A=4]=\frac5{128}$$
(everybody has a $$U[0,1)$$ generator, or this can be approximated by coin tossing).
Take $$1+2+3+4=10$$ samples from $$-X$$. Then we can obtain independent $$B_1,B_2,B_3,B_4$$ with cdf's $$1-F_{X}(-x),(1-F_X(-x))^2,(1-F_X(-x))^3,(1-F_X(-x))^4$$, by taking the corresponding maximums, as we saw in previous posts. Define $$Y'_4$$ by
$$Y'_4=B_1$$ if $$A=1$$,
$$Y'_4=B_2$$ if $$A=2$$,
$$Y'_4=B_3$$ if $$A=3$$,
$$Y'_4=B_4$$ if $$A=4$$,
$$Y'_4=0$$ otherwise.
Then the cdf of $$Y'_4$$ is approximately the right-hand side of (*) with $$x:=F_X(-x)$$. Therefore the cdf of $$Y_4=-Y'_4$$ is approximately $$F_X^{\frac12}$$ by (*).
Maybe you are a A student in pure mathematics, but this post has nothing to do with answering the question. pruse has given an excellent answer by pure probability theory, and we all know that. Maybe the way he writes was not so polite, but keep attacking him only tells everyone your envy. Stop being childish, Milo.

#### MiloRambaldi

Maybe you are a A student in pure mathematics, but this post has nothing to do with answering the question. pruse has given an excellent answer by pure probability theory, and we all know that. Maybe the way he writes was not so polite, but keep attacking him only tells everyone your envy. Stop being childish, Milo.
Either you are a complete moron, or you passing judgment without even bothering to follow the postings in this thread.

Replies
0
Views
232
Replies
0
Views
2K
Replies
2
Views
825
Replies
7
Views
1K
Replies
0
Views
2K