Generating correlated numbers from independent distributions

I'm trying to simulate this scenario: 10 different algorithms are solving a number of problems. All 10 are run on each problem instance, which means if a particular problem instance is hard, I expect all algorithms to perform quite bad and vice versa.

Now, to simulate this, I created 10 different normal distributions from which I draw random numbers. These numbers represent the algorithms performance for some problem instance; however, since the distributions are independent, I'm not capturing the effect of the problem instance on the drawn numbers. Any idea how I can do this (i.e. correlated the random numbers that are drawn)?

Regards,

-
 Could this relate to Copula? It is uncorrelated distributions, but with dependent structures. I am not sure whether the question is correct, because statistically independent means uncorrelated, but uncorrelation doesn't mean independent. The question maybe another way around. – Fred Feb 6 '12 at 1:10 I don't think I quite follow you – Jawad Feb 6 '12 at 11:26

This sounds like a multi-level or mixed model would be useful. You have two sources of uncertainty: the alorithm and the problem. You can write this as

$$t_{ij}=a_{i}+p_{j}+e_{ij}$$

Where a is algorithm p is problem and e is error or interaction between problem and algorithm and t is you target for the $ij$ problem-algorithm pair. So you generate a problem effect, and a algorithm effect from their distributions (which is assigned by you), and an interaction effect. I would recommend the interaction effect if you have "tailored" algorithm designed for specific problems (eg exploit sparsity).

-
Thanks, the model you suggested exactly fits what I'm looking at. While creating the algorithm effect and problem effect can be easily done by drawing random numbers from the corresponding dists., the interaction effect isn't. Would you suggest a way to do it? – Jawad Feb 6 '12 at 11:13
You would also draw it from a distribution. The purpose of the interaction is to allow the algorithm effect depend on the problem, rather than be constant for all problems. If you're not sure what to use, perhaps using an empirical distribution from a few test runs would be useful. – probabilityislogic Feb 6 '12 at 12:28
I might use an empirical dist. Thanks. – Jawad Feb 6 '12 at 13:35
+1. This appears to be the same as another solution proposed slightly earlier. The two replies together give a good answer. I am upvoting this one because it uses a universal language--mathematical notation--developed for communicating such ideas to people rather than a narrow specialized language (R) intended for instructing computers. The R version is one solution out of many possible (and therefore makes a nice illustration) whereas the mathematical version given here is a general solution which is readily translated to any computing platform. – whuber Feb 6 '12 at 15:41
@whuber, all of that is true. – gung Feb 6 '12 at 23:13

I'm not sure what's "best" here, but a couple of approaches are thinkable. One is to draw a random number representing problem difficulty. (If you wanted, you could have additional values, for example, that index the quality of the algorithm.) Then you sum these values. For instance, in R:

nProbs           = 1000     # the number of problems
nAlgs            =   10     # the number of algorithms
sigma_easiness   =    5     # the SD of the distribution of how easy the problems are

# algorithms differ in quality:
algorithms        = seq(from=-2, to=2, length.out=nAlgs)

prob_easiness     = rnorm(nProbs, mean=0, sd=sigma_difficulty)
values            = rep(prob_difficulty, each=nAlgs) + algorithms
resid_variability = rnorm(nProbs*nAlgs)
performance       = matrix(data=(values+resid_variability), ncol=10, byrow=T)

> mean(abs(cor(performance)))
[1] 0.9636438


More complex versions can also be done (say, with the variability of the algorithms differing, or some algorithms performing better or worse depending on problem difficulty, etc.).

Sidestepping all this, if you just want to generate correlated data from a multivariate normal distribution, the function mvrnorm from the MASS library in R will do that for you.

-