OMSCS-SIM课程笔记10-Comparing Systems

这个系列是Gatech OMSCS 仿真和建模课程(ISYE 6644: Simulation and Modeling for Engineering and Science)的同步课程笔记。课程内容涉及计算机模拟在统计分析和建模中的应用，本节介绍利用随机模拟的结果对系统进行对比和评价的方法。

Introduction and Review of Classical Confidence Intervals

置信区间(confidence intervals, CI)是系统评价最常用的方法，因此我们首先来回顾一下CI的概念和性质。

Confidence Intervals for the Mean

假设有一系列独立同分布的正态分布随机变量$\{X_i\}$，我们可以计算它们的样本均值${\overline{X}}_n$和方差$S_X^2$。在此基础上，我们构造统计量$T$：

$$T=\frac{{\overline{X}}_n-\mu }{\sqrt{S_X^2/n}}=\frac{\frac{{\overline{X}}_n-\mu }{\sqrt{{\sigma }^2/n}}}{\sqrt{S_X^2/{\sigma }^2}}$$

可以证明统计量$T$服从参数为$n-1$的$t$分布，$T\sim t(n-1)$。

利用统计量$T$可以得到总体方差${\sigma }^2$未知条件下样本均值的置信区间：

Confidence Intervals Difference Two Means

接下来考虑样本来自两个正态分布的情况。假设$\{X_i\}$来自正态分布$N({\mu }_X,{\sigma }_X^2)$，$\{Y_i\}$来自$N({\mu }_Y,{\sigma }_Y^2)$，根据我们已知的信息可以构造出不同的置信区间。

如果$\{X_i\}$和$\{Y_i\}$有着相同但是未知的方差，可以构造出它们均值差异的置信区间为：

如果$\{X_i\}$和$\{Y_i\}$有着不相同的方差，可以构造出它们均值差异的置信区间为：

Paired CI Difference Two Means

现实中另一种常见的情况是$\{X_i\}$和$\{Y_i\}$自身满足独立同分布，但每一对$(X_i,Y_i)$则存在相互关联。

在这种情况下可以构造出差异$D$的置信区间：

Comparison of Simulated Systems

在随机模拟中数据之间往往不满足独立同分布假设，在这种情况下我们需要一些额外的处理来推导出置信区间。

Confidence Intervals for Mean Differences

利用独立重复试验，我们可以估计两个系统自身的均值和方差：

得到均值和方差后就可以计算两个系统差异的置信区间：

另一种可行的策略是把两个系统的试验看成是一对，然后利用Paired CI Difference的方法来估计置信区间：

Variance Reduction Techniques

Common Random Numbers

在比较不同系统时我们可以通过对仿真过程的控制来减少随机模拟的方差。比如说我们可以将不同系统的随机输入设置为相同的值，这样就可以比较它们在同样条件下的性能。

进一步可以证明这种使用相同随机输入的方法可以减少估计的方差并且能够给出更紧的置信区间。

Antithetic Random Numbers

减少方差的另一种方法是使用对立变量(antithetic random numbers)，它的思想是主动引入负相关的随机变量来减少估计的方差。

以Monte Carlo积分为例，假设待估计的积分为${\int }_1^2\frac{1}{x}dx$，直接进行采样可以得到如下结果：

接下来我们构造这些随机样本的对立变量$1-U_i$重新进行估计，然后对两次估计取均值可以得到一个更准确的积分估计值：

Control Variates

除此之外还可以使用控制变量(control variates)来减少方差。假设我们已知一个与$X$正相关的随机变量$Y$，我们可以利用$Y$来构造一个关于$X$的估计：

$$C=\overline{X}-\beta (Y-\mathbb{E}[Y])$$

可以证明这个新的估计$C$是无偏的，而且有着比$\overline{X}$更小的方差。

Ranking and Selection Methods

很多任务中我们需要从多个系统中挑选出其中最好的那个，此时就需要对这些系统进行排序。

Find the Normal Distribution with the Largest Mean

Introduction

在排序问题中最常见的情况是从k个未知参数的正态分布中选出均值最大的那个分布。

此时我们可以使用无差异区域(indifference zone)的方法进行选择。

Single-Stage Procedures

indifference zone方法中最基本的是single-stage procedure。single-stage procedure非常简单：我们假设k个系统都具有相同的方差，此时只需要根据样本均值进行排序并且选出均值最大的那个系统即可。

single-stage procedure的难点在于计算统计样本均值时所需的样本数。

所需样本数$n$的推导过程比较复杂，这里简单记录如下：

Two-Stage Procedures

Multi-Stage Procedure

Find the Bernoulli with the Largest Success Probability

对于Bernoulli系统，我们希望能够挑选出概率最大的那个。这里同样使用了indifference zone方法进行排序。

Find the Most Probable Multinomial Cell

对于multinomial分布的系统，我们希望了解系统的哪个输出具有最高的概率。这样的问题同样可以使用indifference zone方法。

根据多项分布的性质，我们可以计算产生样本的概率以及基于样本进行选择时结果正确的概率。

在进行选择时同样需要考虑所需的样本数$n$。

Reference

• Comparing Systems