UnRisk 7

Forum Navigation:

magazine

FORUMS > Brainteaser Forum < refresh >
Topic Title: Morgan Stanley interview question
Created On Fri May 09, 08 08:08 AM
Topic View:

Pages: [ << 1 2 3 >> Previous Next ]
View thread in raw text format


Justin2000
Junior Member

Posts: 15
Joined: Sep 2006

Thu Jun 05, 08 05:54 AM
User is offline

deleted

Edited: Thu Jun 05, 08 at 05:57 AM by Justin2000
 
Reply
   
Quote
   
Top
   
Bottom
     



srednister
Junior Member

Posts: 18
Joined: Mar 2008

Thu Jun 19, 08 03:58 PM
User is offline


-------------------------------------
z = x with probability \rho
z = y overwise

(x, z) is the answer
-------------------------------------


Yeah, this is a best way.

Edited: Thu Jun 19, 08 at 03:59 PM by srednister
 
Reply
   
Quote
   
Top
   
Bottom
     



sadsack2
Junior Member

Posts: 11
Joined: Dec 2006

Sun May 03, 09 08:08 PM
User is offline

But that method requires generating 3 uniforms. How about simply: generate X and Y uniform 0,1 independently, then let Z = Y + a(X-Y). I.e., 'pull' Y 100a percent of the way towards X. So if a=1/2 and Y<X then you pull Y up half way to X. Then you can check that Z is U(0,1) for all a and corr(X,Z)=a. Pick a=rho.
 
Reply
   
Quote
   
Top
   
Bottom
     



FalsePositive
Member

Posts: 89
Joined: Mar 2009

Mon May 04, 09 11:50 PM
User is offline

No one has mentioned the Cholesky decomposition method which I believe is the standard way of correlating random variables.

Assuming X and Y are independent and identically distributed in the interval [0,1], we can construct a column matrix (X, Y)^T whose covariance matrix is <(X-1/2, Y-1/2)^T (X-1/2, Y-1/2)>=1/12 * 1., where 1. is the 2 by 2 unit matrix.

Now if we want to correlate X and Y with correlation \rho, we introduce the covariance matrix Cov=(1/12, \rho; \rho, 1/12). If we simply find the lower-triangular matrix which satisfies LL^T=Cov and then calculate (x, y):=(X-1/2, Y-1/2) L^T+(1/2, 1/2), the covariance matrix of the column matrix (x, y)^T is

<(x-1/2, y-1/2)^T (x-1/2, y-1/2)>=<L (X-1/2, Y-1/2) (X-1/2, Y-1/2) L^T>= L L^T = Cov.

So now the new variables x and y satisfy <(x-1/2)(y-1/2)>=\rho, hence the correlation. Moreover the mean and variance of x and y are preserved i.e. <x>=<y>=1/2 and <(x-1/2)^2>=<(y-1/2)^2>=1/12, which imply that x and y are uniformly distributed within the same range [0.1].

Please let me know if you see anything wrong about this approach. Also note that X and Y can be arrays of random variables; For symmetry purposes one can also use the diagonalization method, i.e decompose Cov=PDP^{-1} and use PD^{1/2} instead of L, the result will be the same.

-------------------------
Try to learn something about everything and everything about something. - T. H. Huxley

Edited: Wed May 06, 09 at 09:35 AM by FalsePositive
 
Reply
   
Quote
   
Top
   
Bottom
     



zzrays
Junior Member

Posts: 4
Joined: Nov 2007

Wed May 20, 09 11:17 PM
User is offline

Quote

Originally posted by: FalsePositive
No one has mentioned the Cholesky decomposition method which I believe is the standard way of correlating random variables.

Assuming X and Y are independent and identically distributed in the interval [0,1], we can construct a column matrix (X, Y)^T whose covariance matrix is <(X-1/2, Y-1/2)^T (X-1/2, Y-1/2)>=1/12 * 1., where 1. is the 2 by 2 unit matrix.

Now if we want to correlate X and Y with correlation \rho, we introduce the covariance matrix Cov=(1/12, \rho; \rho, 1/12). If we simply find the lower-triangular matrix which satisfies LL^T=Cov and then calculate (x, y):=(X-1/2, Y-1/2) L^T+(1/2, 1/2), the covariance matrix of the column matrix (x, y)^T is

<(x-1/2, y-1/2)^T (x-1/2, y-1/2)>=<L (X-1/2, Y-1/2) (X-1/2, Y-1/2) L^T>= L L^T = Cov.

So now the new variables x and y satisfy <(x-1/2)(y-1/2)>=\rho, hence the correlation. Moreover the mean and variance of x and y are preserved i.e. <x>=<y>=1/2 and <(x-1/2)^2>=<(y-1/2)^2>=1/12, which imply that x and y are uniformly distributed within the same range [0.1].

Please let me know if you see anything wrong about this approach. Also note that X and Y can be arrays of random variables; For symmetry purposes one can also use the diagonalization method, i.e decompose Cov=PDP^{-1} and use PD^{1/2} instead of L, the result will be the same.




seems the way to generate multi-normal distribution with given cov matrix, but the matrix you listed is mixed with correlation matrix and cov matrix.
 
Reply
   
Quote
   
Top
   
Bottom
     



FalsePositive
Member

Posts: 89
Joined: Mar 2009

Fri May 22, 09 01:18 PM
User is offline

Quote

Originally posted by: zzrays
Quote

Originally posted by: FalsePositive
No one has mentioned the Cholesky decomposition method which I believe is the standard way of correlating random variables.

Assuming X and Y are independent and identically distributed in the interval [0,1], we can construct a column matrix (X, Y)^T whose covariance matrix is <(X-1/2, Y-1/2)^T (X-1/2, Y-1/2)>=1/12 * 1., where 1. is the 2 by 2 unit matrix.

Now if we want to correlate X and Y with correlation \rho, we introduce the covariance matrix Cov=(1/12, \rho; \rho, 1/12). If we simply find the lower-triangular matrix which satisfies LL^T=Cov and then calculate (x, y):=(X-1/2, Y-1/2) L^T+(1/2, 1/2), the covariance matrix of the column matrix (x, y)^T is

<(x-1/2, y-1/2)^T (x-1/2, y-1/2)>=<L (X-1/2, Y-1/2) (X-1/2, Y-1/2) L^T>= L L^T = Cov.

So now the new variables x and y satisfy <(x-1/2)(y-1/2)>=\rho, hence the correlation. Moreover the mean and variance of x and y are preserved i.e. <x>=<y>=1/2 and <(x-1/2)^2>=<(y-1/2)^2>=1/12, which imply that x and y are uniformly distributed within the same range [0.1].

Please let me know if you see anything wrong about this approach. Also note that X and Y can be arrays of random variables; For symmetry purposes one can also use the diagonalization method, i.e decompose Cov=PDP^{-1} and use PD^{1/2} instead of L, the result will be the same.




seems the way to generate multi-normal distribution with given cov matrix, but the matrix you listed is mixed with correlation matrix and cov matrix.


Right! In order to induce the correlation coefficient corr(x,y)=\rho, we actually have to decompose the covariance matrix Cov=(1, \rho; \rho, 1), in which case the linear dependence can be approximated as (y-1/2)=\rho(x-1/2)..

The following line should also corrected:

<(x-1/2, y-1/2)^T (x-1/2, y-1/2)>=<L (X-1/2, Y-1/2)^T (X-1/2, Y-1/2) L^T>= 1/12 * L L^T = 1/12 * Cov.

Edit: In this case we should also perhaps start calling the Cov matrix 'correlation matrix'..

-------------------------
Try to learn something about everything and everything about something. - T. H. Huxley

Edited: Mon May 25, 09 at 01:59 AM by FalsePositive
 
Reply
   
Quote
   
Top
   
Bottom
     



quantus
Member

Posts: 28
Joined: Jul 2007

Sat May 23, 09 05:01 PM
User is offline

Quote

Originally posted by: FalsePositive
No one has mentioned the Cholesky decomposition method which I believe is the standard way of correlating random variables.

Assuming X and Y are independent and identically distributed in the interval [0,1], we can construct a column matrix (X, Y)^T whose covariance matrix is <(X-1/2, Y-1/2)^T (X-1/2, Y-1/2)>=1/12 * 1., where 1. is the 2 by 2 unit matrix.
...
Please let me know if you see anything wrong about this approach. Also note that X and Y can be arrays of random variables; For symmetry purposes one can also use the diagonalization method, i.e decompose Cov=PDP^{-1} and use PD^{1/2} instead of L, the result will be the same.

I don't see how your solution makes sure that the result is also uniformly distributed.

The problem here was not to create correlation, but to create correlation while keeping the result uniformly distributed
That is, if X and Y are U[0,1], then (X+Y)/2 is not U[0,1].

Since I just discovered that topic, my solution would be:
Step 1: from i.i.d. U[0,1] create two independent N(0,1)
Step 2: from two independent N(0,1) create two correlated N(..,..) using matrix multiplication (for normals it works!)
Step 3: from two correlated N(..,..) create two correlated U[0,1]

on step 3 it is not clear how to make correlation exactly \rho, but it can be achieved using simulations :-)

Another solution,
z = { x with probability rho, and y otherwise
is more beautiful, but it generates a kind of weird joint distribution (x,z) with infinite mass-points (or even mass-line!)... so I guess it is not a good solution in practice, although it indeed formally satisfies the condition.

 
Reply
   
Quote
   
Top
   
Bottom
     



FalsePositive
Member

Posts: 89
Joined: Mar 2009

Sat May 23, 09 08:47 PM
User is offline

Quote

Originally posted by: quantus
Quote

Originally posted by: FalsePositive
No one has mentioned the Cholesky decomposition method which I believe is the standard way of correlating random variables.

Assuming X and Y are independent and identically distributed in the interval [0,1], we can construct a column matrix (X, Y)^T whose covariance matrix is <(X-1/2, Y-1/2)^T (X-1/2, Y-1/2)>=1/12 * 1., where 1. is the 2 by 2 unit matrix.
...
Please let me know if you see anything wrong about this approach. Also note that X and Y can be arrays of random variables; For symmetry purposes one can also use the diagonalization method, i.e decompose Cov=PDP^{-1} and use PD^{1/2} instead of L, the result will be the same.

I don't see how your solution makes sure that the result is also uniformly distributed.

The problem here was not to create correlation, but to create correlation while keeping the result uniformly distributed
That is, if X and Y are U[0,1], then (X+Y)/2 is not U[0,1].

Since I just discovered that topic, my solution would be:
Step 1: from i.i.d. U[0,1] create two independent N(0,1)
Step 2: from two independent N(0,1) create two correlated N(..,..) using matrix multiplication (for normals it works!)
Step 3: from two correlated N(..,..) create two correlated U[0,1]

on step 3 it is not clear how to make correlation exactly \rho, but it can be achieved using simulations :-)

Another solution,
z = { x with probability rho, and y otherwise
is more beautiful, but it generates a kind of weird joint distribution (x,z) with infinite mass-points (or even mass-line!)... so I guess it is not a good solution in practice, although it indeed formally satisfies the condition.


I believe cm27874 has also proposed your first method. Of course, you can always translate distributions to normal distribution, and then correlate them by Cholesky decomposition and translate them back, however this doesn't seem to be necessary if the decomposition method already preserves the moments of the distribution.

At least for the first four moments I can easily show that mean, variance, skewness and kurtosis of x, y are the same as those of X and Y. To show this, consider the fact that x-1/2=L_11 (X-1/2), y-1/2=L_21 (X-1/2)+L_22 (Y-1/2) and use L_11^2=1, L_21^2+L_22^2=1. In fact, for x it's easy to show that all of its moments are preserved; for y the calculation can be more complicated after fourth moment. So if the distribution moments are preserved the resulting distributions should also be uniform U[0,1]..

-------------------------
Try to learn something about everything and everything about something. - T. H. Huxley

Edited: Sat May 23, 09 at 08:57 PM by FalsePositive
 
Reply
   
Quote
   
Top
   
Bottom
     



quantus
Member

Posts: 28
Joined: Jul 2007

Sun May 24, 09 05:54 PM
User is offline

Quote

Originally posted by: FalsePositive

At least for the first four moments I can easily show that mean, variance, skewness and kurtosis of x, y are the same as those of X and Y. To show this, consider the fact that x-1/2=L_11 (X-1/2), y-1/2=L_21 (X-1/2)+L_22 (Y-1/2) and use L_11^2=1, L_21^2+L_22^2=1. In fact, for x it's easy to show that all of its moments are preserved; for y the calculation can be more complicated after fourth moment. So if the distribution moments are preserved the resulting distributions should also be uniform U[0,1]..

I didn't get that.

Consider the case when L_21 >= 0, L_22 >= 0
if you happen to sample X =0 and Y=0 (these are lowest possible X and Y), then what's the value of y?
You claim that y is U[0,1], then y should be 0, right? (Otherwise, how can you possibly get zero for y?)
Then it immediately means that L_21+L_22 = 1
You specify that L_21^2+L_22^2 = 1, therefore
solving these two we get two solutions: L_21 = 1, L_22 = 0 and L_21=0, L_22=1

Consider the case when L_21 < 0, L_22 >=0
if you happen to sample X =1 and Y=0 (these are maximum possible for X and minimum possible for Y), then what's the value of y?
You claim that y is U[0,1], then y should be 0, right? (Otherwise, how can you possibly get zero for y?)
Then it immediately means that -L_21+L_22 = 1
You specify that L_21^2+L_22^2 = 1, therefore
solving these two we get two solutions: L_21 = -1, L_22 = 0 and L_21=0, L_22=1

and so on other 2 cases exactly same.

Therefore, your suggestion can have only U[0,1] solutions: y = X, y=-X, y = Y or y = -Y.




Edited: Sun May 24, 09 at 06:02 PM by quantus
 
Reply
   
Quote
   
Top
   
Bottom
     



FalsePositive
Member

Posts: 89
Joined: Mar 2009

Mon May 25, 09 01:50 AM
User is offline

Quote

Originally posted by: quantus
Quote

Originally posted by: FalsePositive

At least for the first four moments I can easily show that mean, variance, skewness and kurtosis of x, y are the same as those of X and Y. To show this, consider the fact that x-1/2=L_11 (X-1/2), y-1/2=L_21 (X-1/2)+L_22 (Y-1/2) and use L_11^2=1, L_21^2+L_22^2=1. In fact, for x it's easy to show that all of its moments are preserved; for y the calculation can be more complicated after fourth moment. So if the distribution moments are preserved the resulting distributions should also be uniform U[0,1]..

I didn't get that.

Consider the case when L_21 >= 0, L_22 >= 0
if you happen to sample X =0 and Y=0 (these are lowest possible X and Y), then what's the value of y?
You claim that y is U[0,1], then y should be 0, right? (Otherwise, how can you possibly get zero for y?)



You get zero for y (and x) when (X, Y)^T= L^-1 (0-1/2, 0-1/2)^T+(1/2, 1/2)^T, or when X=(-L_22+L_11*L_22)/(2*L_11*L_22) and Y=(L_21-L_11+L_11*L_22)/(2*L_11*L_22). Try it for example for correlation matrix (1, 0.45; 045, 1), the L matrix is (1, 0; 0.45, 0.893) and L^-1 is (1, 0; -0.504, 1.120), from which you can show that X=0 and Y=0.192 project onto x=0, y=0. Don't understand why you think y=0 can only be obtained from (X=0,Y=0).

-------------------------
Try to learn something about everything and everything about something. - T. H. Huxley

Edited: Mon May 25, 09 at 02:01 AM by FalsePositive
 
Reply
   
Quote
   
Top
   
Bottom
     



quantus
Member

Posts: 28
Joined: Jul 2007

Mon May 25, 09 04:36 AM
User is offline

Quote

Originally posted by: FalsePositive
Try it for example for correlation matrix (1, 0.45; 045, 1), the L matrix is (1, 0; 0.45, 0.893) and L^-1 is (1, 0; -0.504, 1.120), from which you can show that X=0 and Y=0.192 project onto x=0, y=0. Don't understand why you think y=0 can only be obtained from (X=0,Y=0).

Finally we converged to your mistake.
Use the same L and substitute X=0, Y=0.1, you will get a negative y.
It means you have non-zero density for y<0, how can that y be from U[0,1] ?

Just think about what you are trying to do!

You are trying to find a linear combination of X and Y from U[0,1] with coefficients a,b,c such that
Z = a*X + b*Y + c
and Z is also U[0,1].
(all your matrix algebra works out just to this linear combination)

There are only two solutions to that problem: a=1, b=0,c=0 and a=0,b=1,c=0

 
Reply
   
Quote
   
Top
   
Bottom
     



FalsePositive
Member

Posts: 89
Joined: Mar 2009

Mon May 25, 09 04:04 PM
User is offline

Quote

Originally posted by: quantus
Quote

Originally posted by: FalsePositive
Try it for example for correlation matrix (1, 0.45; 045, 1), the L matrix is (1, 0; 0.45, 0.893) and L^-1 is (1, 0; -0.504, 1.120), from which you can show that X=0 and Y=0.192 project onto x=0, y=0. Don't understand why you think y=0 can only be obtained from (X=0,Y=0).

Finally we converged to your mistake.
Use the same L and substitute X=0, Y=0.1, you will get a negative y.
It means you have non-zero density for y<0, how can that y be from U[0,1] ?



Oh, yeah, thanks for pointing to that. So it seems like the transformation doesn't preserve the boundaries, although the first few central moments are unchanged. I can't think of any other solution right now. It seems that we have no choice but to use nonlinear transforms, as has been pointed out by others before. We can probably use some threshold criteria or abs functions in combination with my approach to project the outliers back onto the same interval [0,1]. Or maybe we can transform the random numbers to Gaussian before correlating them, but I don't know how to transform the points back to uniform while keeping their correlation.

-------------------------
Try to learn something about everything and everything about something. - T. H. Huxley

Edited: Mon May 25, 09 at 04:06 PM by FalsePositive
 
Reply
   
Quote
   
Top
   
Bottom
     



wileysw
Senior Member

Posts: 579
Joined: Dec 2006

Wed May 27, 09 04:15 AM
User is offline

there are two other trivial solutions with c=1, a=-1, b=0 (or b=-1, a=0).

as already pointed out, there is no way to preserve the moments either (a general way to see this is to consider the moment generating function E[exp(t*Z)]). or by brute force, you could make Z symmetric with respect to 1/2, i.e., c=(1-a-b)/2, to preserve the mean (which actually preserves all the odd moments). then to preserve the variance and kurtosis, one gets a^2=1, b^2=0 (or a^2=0, b^2=1) - same result as if one wants to preserve the range of [0,1].

one thing seems a little odd to me is that, for two random variables x and z, by only specifying the p.d.f. of each random variable and the correlation, i believe the joint p.d.f. of these two variables cannot be unique, since one could add terms like (x-1/2)*(z-1/2) to the joint p.d.f., etc. (for two normal variables x and y, i could do the same trick: Z=x with prob rho and y otherwise. note they are not jointly normal). so im not quite sure what exactly the point is for this problem.

Edited: Wed May 27, 09 at 04:19 AM by wileysw
 
Reply
   
Quote
   
Top
   
Bottom
     



quantus
Member

Posts: 28
Joined: Jul 2007

Thu May 28, 09 02:56 PM
User is offline

Quote

Originally posted by: wileysw
one thing seems a little odd to me is that, for two random variables x and z, by only specifying the p.d.f. of each random variable and the correlation, i believe the joint p.d.f. of these two variables cannot be unique, since one could add terms like (x-1/2)*(z-1/2) to the joint p.d.f., etc. (for two normal variables x and y, i could do the same trick: Z=x with prob rho and y otherwise. note they are not jointly normal). so im not quite sure what exactly the point is for this problem.

Yes, the resulting answer looks indeed not unique, since we suggested at least 2 different solutions.
For "Z=x with prob rho and y otherwise", joint density will have a whole line of mass-points.
For "i.i.d U[0,1]-> i.i.d N[0,1] -> N[0,rho1] -> correlated U[0,1]", joint density wouldn't have mass points.
So there are two different joint densities, that satisfy the condition.
 
Reply
   
Quote
   
Top
   
Bottom
     



quantus
Member

Posts: 28
Joined: Jul 2007

Thu May 28, 09 02:59 PM
User is offline

Quote

Originally posted by: FalsePositiveOr maybe we can transform the random numbers to Gaussian before correlating them, but I don't know how to transform the points back to uniform while keeping their correlation.

Yeah, this is was the whole point of second solution.
Sum of normals is normal (unlike U[0,1]!! )

To transform it back, use normal cdf.
If Phi(x) is cdf function of N(0,1) and Z is N(0,1) r.v., than Phi(Z) is distributed U[0,1]
 
Reply
   
Quote
   
Top
   
Bottom
     



MatthewM
Senior Member

Posts: 416
Joined: Dec 2007

Sat Jun 13, 09 06:13 AM
User is offline

I'll add my solution to the mix; given a, b indep. and transforming to x, y with correlation rho:

x = a

y = a with prob (rho + 1)/2
y = (1 - a) with prob (1 - rho)/2

So even though the conditional distribution of y given x (or vice versa) is completely messed up (it's discrete) the overall distribution of each is uniform.

Whether or not y goes to a or 1-a is given by b, obviously. If b < (rho + 1)/2 then send y = a. If b >= (rho + 1)/2 then send y = 1-a

Edited: Sat Jun 13, 09 at 06:15 AM by MatthewM
 
Reply
   
Quote
   
Top
   
Bottom
     



repoman
Member

Posts: 123
Joined: Feb 2009

Tue Jan 26, 10 03:05 AM
User is offline

Quote

Originally posted by: MatthewM
I'll add my solution to the mix; given a, b indep. and transforming to x, y with correlation rho:

x = a

y = a with prob (rho + 1)/2
y = (1 - a) with prob (1 - rho)/2

So even though the conditional distribution of y given x (or vice versa) is completely messed up (it's discrete) the overall distribution of each is uniform.

Whether or not y goes to a or 1-a is given by b, obviously. If b < (rho + 1)/2 then send y = a. If b >= (rho + 1)/2 then send y = 1-a


Yes, that is the nicest solution without using a third independent random variable, though wb3517 posted it much earlier in the thread

What I came up with was (assume rho >= 0), given X and Y,

Z_alpha = X if X < alpha,
Z_alpha = (1-alpha)Y + alpha if X > alpha.

Then Z_alpha ~ U[0,1], and Corr(X,Z_alpha) = alpha^3 - 3alpha^2 +3alpha. There exists alpha giving Corr=rho by the MVT.

Obviously not as elegant.
 
Reply
   
Quote
   
Top
   
Bottom
     



raags
Junior Member

Posts: 11
Joined: Aug 2007

Wed Jan 27, 10 03:24 AM
User is offline

Attached is a matlab program which produces correlated uniform random variables. comments??

correlUniform%zip correlUniform%zip  (1 KB)
correlUniform.zip correlUniform.zip  (1 KB)

 
Reply
   
Quote
   
Top
   
Bottom
     



repoman
Member

Posts: 123
Joined: Feb 2009

Wed Jan 27, 10 03:58 AM
User is offline

Quote

Originally posted by: raags
Attached is a matlab program which produces correlated uniform random variables. comments??


I think it would be more helpful to explain the algorithm, rather than provide code.
 
Reply
   
Quote
   
Top
   
Bottom
     



raags
Junior Member

Posts: 11
Joined: Aug 2007

Wed Jan 27, 10 04:29 AM
User is offline

1. take two uniformly distributed random variables: u[0,1] and v[0,1]
2. Norminv(u), Norminv(v)
3. change the linear correlation 'rho' to rank correlation = 2*sin(pi*rho/6) because rank correlation is invariant to transformation
4. using cholesky decomposition produce correlated normal random variables
5. get the uniformly distributed random variables usning normcdf

output of attached program is
correlation coefficient of uniformly distributed random variables:
1.0000 0.0108
0.0108 1.0000

desired correlation:
1.0000 0.7000
0.7000 1.0000

correlation coefficient of uniformly distributed random variables:
1.0000 0.6972
0.6972 1.0000

Mean: (should be 0.5)
0.4922 0.5106

variance: (should be equal to 1/12)
0.0813

0.0837
 
Reply
   
Quote
   
Top
   
Bottom
     

Pages: [ << 1 2 3 >> Previous Next ]
View thread in raw text format
FORUMS > Brainteaser Forum < refresh >

Forum Navigation:

© All material, including contents and design, copyright Wilmott Electronic Media Limited - FuseTalk 4.01 © 1999-2014 FuseTalk Inc. Terms & Conditions