17
$\begingroup$

I have random variables $X_0,X_1,\dots,X_n$. $X_0$ has a normal distribution with mean $\mu>0$ and variance $1$. The $X_1,\dots,X_n$ rvs are normally distributed with mean $0$ and variance $1$. Everything is mutually independent.

Let $E$ denote the event that $X_0$ is the largest of these, i.e., $X_0 > \max(X_1,\dots,X_n)$. I want to calculate or estimate $\Pr[E]$. I'm looking for an expression for $\Pr[E]$, as a function of $\mu,n$, or a reasonable estimate or approximation for $\Pr[E]$.

In my application, $n$ is fixed ($n=61$) and I want to find the smallest value for $\mu$ that makes $\Pr[E] \ge 0.99$, but I'm curious about the general question as well.

$\endgroup$
3
  • $\begingroup$ How large is $n$? There ought to be some good asymptotic expressions based on large-sample theory. $\endgroup$
    – whuber
    Nov 15, 2012 at 19:59
  • $\begingroup$ @whuber, thanks! I edited the question: in my case $n=61$. Even if $n=61$ isn't large enough to count as large, if there are good asymptotic estimates in the case where $n$ is large, that'd be interesting. $\endgroup$
    – D.W.
    Nov 15, 2012 at 20:18
  • 6
    $\begingroup$ Using numerical integration, $\mu \approx 4.91912496$. $\endgroup$
    – whuber
    Nov 15, 2012 at 20:33

3 Answers 3

19
$\begingroup$

The calculation of such probabilities has been studied extensively by communications engineers under the name $M$-ary orthogonal signaling where the model is that one of $M$ equal-energy equally likely orthogonal signals being transmitted and the receiver attempting to decide which one was transmitted by examining the outputs of $M$ filters matched to the signals. Conditioned on the identity of the transmitted signal, the sample outputs of the matched filters are (conditionally) independent unit-variance normal random variables. The sample output of the filter matched to the signal transmitted is a $N(\mu,1)$ random variable while the outputs of all the other filters are $N(0,1)$ random variables.

The conditional probability of a correct decision (which in the present context is the event $C = \{X_0 > \max_i X_i\}$) conditioned on $X_0 = \alpha$ is $$P(C \mid X_0 = \alpha) = \prod_{i=1}^n P\{X_i < \alpha \mid X_0 = \alpha\} = \left[\Phi(\alpha)\right]^n$$ where $\Phi(\cdot)$ is the cumulative probability distribution of a standard normal random variable, and hence the unconditional probability is $$P(C) = \int_{-\infty}^{\infty}P(C \mid X_0 = \alpha) \phi(\alpha-\mu)\,\mathrm d\alpha = \int_{-\infty}^{\infty}\left[\Phi(\alpha)\right]^n \phi(\alpha-\mu)\,\mathrm d\alpha$$ where $\phi(\cdot)$ is the standard normal density function. There is no closed-form expression for the value of this integral which must be evaluated numerically. Engineers are also interested in the complementary event -- that the decision is in error -- but do not like to compute this as $$P\{X_0 < \max_i X_i\} = P(E) = 1-P(C)$$ because this requires very careful evaluation of the integral for $P(C)$ to an accuracy of many significant digits, and such evaluation is both difficult and time-consuming. Instead, the integral for $1-P(C)$ can be integrated by parts to get $$P\{X_0 < \max_i X_i\} = \int_{-\infty}^{\infty} n \left[\Phi(\alpha)\right]^{n-1}\phi(\alpha) \Phi(\alpha - \mu)\,\mathrm d\alpha.$$ This integral is more easy to evaluate numerically, and its value as a function of $\mu$ is graphed and tabulated (though unfortunately only for $n \leq 20$) in Chapter 5 of Telecommunication Systems Engineering by Lindsey and Simon, Prentice-Hall 1973, Dover Press 1991. Alternatively, engineers use the union bound or Bonferroni inequality $$\begin{align*} P\{X_0 < \max_i X_i\} &= P\left\{(X_0 < X_1)\cup (X_0 < X_2) \cup \cdots \cup (X_0 < X_n)\right\}\\ &\leq \sum_{i=1}^{n}P\{X_0 < X_i\}\\ &= nQ\left(\frac{\mu}{\sqrt{2}}\right) \end{align*}$$ where $Q(x) = 1-\Phi(x)$ is the complementary cumulative normal distribution function.

From the union bound, we see that the desired value $0.01$ for $P\{X_0 < \max_i X_i\}$ is bounded above by $60\cdot Q(\mu/\sqrt{2})$ which bound has value $0.01$ at $\mu = 5.09\ldots$. This is slightly larger than the more exact value $\mu = 4.919\ldots$ obtained by @whuber by numerical integration.

More discussion and details about $M$-ary orthogonal signaling can be found on pp. 161-179 of my lecture notes for a class on communication systems.

$\endgroup$
6
$\begingroup$

A formal answer:

The probability distribution (density) for the maximum of $N$ i.i.d. variates is: $p_N(x)= N p(x) \Phi^{N-1}(x)$ where $p$ is the probability density and $\Phi$ is the cumulative distribution function.

From this you can calculate the probability that $X_0$ is greater than the $N-1$ other ones via $ P(E) = (N-1) \int_{-\infty}^{\infty} \int_y^{\infty} p(x_0) p(y) \Phi^{N-2}(y) dx_0 dy$

You may need to look into various approximations in order to tractably deal with this for your specific application.

$\endgroup$
1
  • 9
    $\begingroup$ +1 Actually, the double integral simplifies into a single integral since $$\int_y^\infty p(x_0)\,\mathrm dx_0 = 1 - \Phi(y-\mu)$$ giving $$P(E) = 1 - (N-1)\int_{-\infty}^\infty \Phi^{N-2}(y)p(y)\Phi(y-\mu)\,\mathrm dy$$ which is the same as in my answer. $\endgroup$ Nov 15, 2012 at 23:35
1
$\begingroup$

We have

$$\begin{align} \mathbb{P}(\mathcal{E}) &= \mathbb{P}(\bigcap_{i=1}^n \{X_0 \ge X_i \}) = \mathbb{P}(\bigcap_{i=1}^n \{X_0 -X_i \ge 0 \}) \end{align}$$

Let us denote $Z_i = X_0 - X_i$ for $i = 1,...,n$ then the vector $(Z_1,...,Z_n)$ of dimension $n$ follows the n-variate normal distribution $\mathcal{N}_n(\Gamma,\Sigma)$ where $\Gamma \in \mathbb{R}^n$ the mean vector and $\Sigma\in \mathbb{R}^{n \times n}$ the covariance matrix. We determine $\Gamma$ and $\Sigma$, we have $$\Gamma_i=\mathbb{E}(Z_i) =0 \hspace{1cm} \forall i=1,...,n$$ $$\Sigma_{ij} = \text{Cov}(Z_i,Z_j) = \left\{ \begin{array}{ll} 2 & \mbox{if } i=j \\ 1 & \mbox{if } i\ne j \\ \end{array} \right. \tag{1} $$

Then, the probability of the event $\mathcal{E}$ can be calculated with a closed-form expression as follows

$$\color{red}{\mathbb{P}(\mathcal{E}) = \Phi_n \left(\mathbf{l}, \mathbf{u};\mathbf{0}_n;\Sigma \right)}$$ with

  • $\Phi_n() $ the multivariate normal probability
  • $\mathbf{0}_n \in \mathbb{R}^n$ vector of $0$
  • $\Sigma$ is defined in $(1)$
  • $\mathbf{l} = \mathbf{0}_n$ the lower vector
  • $\mathbf{u} \in \mathbb{R}^n$ the upper vector with all elements are equal to $+\infty$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.