Test if two normally distributed random variables have the same mean We have two independent random variables which follow normal distributions $X_1\sim \mathcal N(\mu_1,\sigma_1)$, $X_2\sim \mathcal N(\mu_2,\sigma_2)$.
From the context, we have that $\mu_1\leq\mu_2$. It is also reasonable to assume that $\sigma_1=\sigma_2$, or $\sigma_1\geq\sigma_2$.
I want a test/procedure to determine if $\mu_1=\mu_2$. I know it is not possible to make such a test that always returns the correct answer, but I want a test where at least the probability of a false positive or a false negative can be determined, and perhaps reduced by incrementing the number of observed samples of $X_1$ and $X_2$.
Moreover, drawing values from $X_2$ is very time consuming, so we want to minimize the amount of observations of $X_2$ that we use in this test (observing $X_1$ is simple).
Context of the question: I am trying to see if a randomized optimization algorithm makes any difference or not. $X_1$ are the scores of random solutions (easy to generate) while $X_2$ are the scores of solutions outputted by the algorithm (it is expensive to run the algorithm). You want to minimize the number of times that you have to run the algorithm to perform this test (preferably only once, and only if the first sample does not give you enough information, more times).
 A: The test
if (a) $X_1 \sim N(\mu_1, \sigma_1)$ and (b) $X_1 \sim N(\mu_2, \sigma_2)$ and (c) $X_1$ and $X_2$ are independent then if you draw a sample of size $N_1$ from the distribution of $X_1$ and a sample of size $N_2$ from the distribution of $X_2$, then the arithemtic average of the sample from $X_i$ is $\bar{x}_i$ and is distributed $\bar{X}_i \sim N(\mu_i, \frac{\sigma_i}{\sqrt{N_i}})$.  If the variables are independent then $\bar{X}_1-\bar{X}_2 \sim N(\mu_1 - \mu_2, \sqrt{\frac{\sigma_1^2}{N_1}+\frac{\sigma_2^2}{N_2}})$. 
You seem to have some a priori knowledge about the 'truth' namely that $\mu_1 \le \mu_2$ so if you want to find evidence that $\mu_1 < \mu_2$ then (see What follows if we fail to reject the null hypothesis?) your $H_1$ should be $H_1: \mu_1 < \mu_2$ and in order to 'demonstrate' this, one assumes the opposite, but as you say that $\mu_1 \le \mu_2$ the opposite is $H_0: \mu_1 = \mu_2$.  
So you have a one-sided test $H_0: \mu_1 - \mu_2 = 0$ against $H_1: \mu_1 - \mu_2 < 0$. 
By the above, if $H_0$ is true, then $\mu_1-\mu_2=0$ and therefore  $\bar{X}_1-\bar{X}_2 \sim N(0, \sqrt{\frac{\sigma_1^2}{N_1}+\frac{\sigma_2^2}{N_2}})$. With this you can define a left tail, one sided test and using the Neyman-Pearson lemma it can be shown tbe be the unformly most powerfull test.  If you known $\sigma_i$ then you can use the normal distribution to define the critical region in the left tail, if you don't know them then you estimate them from the samples and then you have to define the critical region using the t-distribution. 
To define the test you have to (1) define a significance level $\alpha$ (2) draw a sample of size $N_1$ from $X_1$ and of size $N_2$ from $X_2$, then (3) compute $\bar{x}_i$ for each of these samples and then compute the p-value of $\bar{x}_1 - \bar{x}_2$ knowing that $\bar{X}_1-\bar{X}_2 \sim N(0, \sqrt{\frac{\sigma_1^2}{N_1}+\frac{\sigma_2^2}{N_2}})$. If the obtained p-value is below $\alpha$ then the test concludes that there is evidence in favour of $H_1$.  One can also compute the $\alpha$-quantile of the distribution under $H_0$, : $q_{\alpha}^0$ and $H_0$ will be rejected when $\bar{x}_1-\bar{x}_2 \le q_{\alpha}^0$. 
The probability of a false positive is equal to the significance level $\alpha$ that you choose, the probability of a false negative can only be computed for a given value of $\mu_1 - \mu_2$. 
The sample sizes
If you have such a value for $\mu_1 - \mu_2$ e.g. the difference is -0.05, then you can compute the type II error for this value:
The type II error is the probability that $H_0$ is accepted when it is false, to compute it, let us assume that it is false and that $\mu_1-\mu_2 = -0.05$. In that case $\bar{X}_1-\bar{X}_2 \sim N(-0.05, \sqrt{\frac{\sigma_1^2}{N_1}+\frac{\sigma_2^2}{N_2}})$ (the mean has changed). 
Now we have to compute the probability that $H_0$ is accepted when the latter is true.  This is the probability of observing $q_\alpha^0$ under the above distribution with mean -0.05. 
it will be a function of $N_1$ and $N_2$.  You can then fix a value for $N_2$ (the one that is difficult to sample) and find $N_1$ by fixing a type II error that is acceptable for you. 
