15.1 Some random selection problems

In the unit on Random Selection , we develop some general theoretical results and computational procedures using MATLAB. In this unit, we extend the treatment to avariety of problems. We establish some useful theoretical results and in some cases use MATLAB procedures, including those in the unit on random selection.

The poisson decomposition

In many problems, the individual demands may be categorized in one of m types. If the random variable T _i is the type of the i th arrival and the class $\{T_i:1\le i\}$ is iid, we have multinomial trials . For $m=2$ we have the Bernoulli or binomial case, in which one type is called a success and the other a failure.

Multinomial trials

We analyze such a sequence of trials as follows. Suppose there are m types, which we number 1 through m . Let $E_{ki}$ be the event that type k occurs on the i th component trial. For each i , the class $\{E_{ki}:1\le k\le m\}$ is a partition, since on each component trial exactly one of the types will occur. The type on the i th trial may be represented by the type random variable

We assume

In a sequence of n trials, we let $N_{kn}$ be the number of occurrences of type k . Then

Now each $N_{kn}\sim$ binomial $(n,p_k)$ . The class $\{N_{kn}:1\le k\le m\}$ cannot be independent, since it sums to n . If the values of $m-1$ of them are known, the value of the other is determined. If $n_1+n_2+\cdots +n_m=n$ , the event

is one of the

ways of arranging n ₁ of the $E_{1i}$ , n ₂ of the $E_{2i},\cdots$ , n _m of the $E_{mi}$ . Each such arrangement has probability $p_1^{n_1}{p}_2^{n_2}\cdots p_m^{n_m}$ , so that

This set of joint probabilities constitutes the multinomial distribution . For $m=2$ , and type 1 a success, this is the binomial distribution with parameter $(n,p_1)$ .

A random number of multinomial trials

We consider, in particular, the case of a random number N of multinomial trials, where $N\sim$ Poisson $\left(\mu \right)$ . Let N _k be the number of results of type k in a random number N of multinomial trials.

Poisson decomposition

Suppose

1. $N\sim$ Poisson $\left(\mu \right)$
2. $\{T_i:1\le i\}$ is iid with $P(T_i=k)=p_k,1\le k\le m$
3. $\{N,T_i:1\le i\}$ is independent

Then

1. Each $N_k\sim$ Poisson $\left(\mu p_k\right)$
2. $\{N_k:1\le k\le m\}$ is independent.

— $\square$

The usefulness of this remarkable result is enhanced by the fact that the sum of independent Poisson random variables is also Poisson, with μ for the sum the sum of the μ _i for the variables added. This is readily established with the aid of the generating function. Before verifying the propositions above,we consider some examples.