15.1 Some random selection problems (Page 4/6)

Applied probability Page 4 / 6

Bernoulli trials with random execution times or costs

Consider a Bernoulli sequence with probability p of success on any component trial. Let N be the number of the trial on which the first success occurs. Let Y _i be the time (or cost) to execute the i th trial. Then the total time (or cost) from the beginning to the completion of the first success is

T = \sum_{i = 1}^{N} Y_{i} (composite ``demand'' with N - 1 \sim geometric p)

We suppose the Y _i form an iid class, independent of N . Now $N - 1 \sim$ geometric $(p)$ implies

$g_{N} (s) = p s / (1 - q s)$ , so that

M_{T} (s) = g_{N} [M_{Y} (s)] = \frac{p M_{Y} (s)}{1 - q M_{Y} (s)}

There are two useful special cases:

$Y_{i} \sim$ exponential $(λ)$ , so that $M_{Y} (s) = \frac{λ}{λ - s}$ .
$M_{T} (s) = \frac{p λ / (λ - s)}{1 - q λ / (λ - s)} = \frac{p λ}{p λ - s}$
which implies $T \sim$ exponential $(p λ)$ .
$Y_{i} - 1 \sim$ geometric $(p_{0})$ , so that $g_{Y} (s) = \frac{p_{0} s}{1 - q_{0} s}$
$g_{T} (s) = \frac{p p_{0} s / (1 - q_{0} s)}{1 - p p_{0} s / (1 - q_{0} s)} = \frac{p p_{0} s}{1 - (1 - p p_{0}) s}$
so that $T - 1 \sim$ geometric $(p p_{0})$ .

Job interviews

Suppose a prospective employer is interviewing candidates for a job from a pool in which twenty percent are qualified. Interview times (in hours) Y _i are presumed to form an iid class, each exponential (3). Thus, the average interview time is 1/3 hour (twentyminutes). We take the probability for success on any interview to be $p = 0.2$ . What is the probability a satisfactory candidate will be found in four hours or less?What is the probability the maximum interview time will be no greater than 0.5, 0.75, 1, 1.25, 1.5 hours?

SOLUTION

$T \sim$ exponential $(0.2 \cdot 3 = 0.6)$ , so that $P (T \leq 4) = 1 - e^{- 0.6 \cdot 4} = 0.9093$ .

P (W \leq t) = g_{N} [P (Y \leq t)] = \frac{0.2 (1 - e^{- 3 t})}{1 - 0.8 (1 - e^{- 3 t})} = \frac{1 - e^{- 3 t}}{1 + 4 e^{- 3 t}}

MATLAB computations give

t = 0.5:0.25:1.5;
PWt = (1 - exp(-3*t))./(1 + 4*exp(-3*t));disp([t;PWt]')0.5000    0.4105
    0.7500    0.62931.0000    0.7924
    1.2500    0.89251.5000    0.9468

The average interview time is 1/3 hour; with probability 0.63 the maximum is 3/4 hour or less; with probability 0.79 the maximum is one hour or less; etc.

Got questions? Get instant answers now!

In the general case, solving for the distribution of T requires transform theory, and may be handled best by a program such as Maple or Mathematica.

For the case of simple Y _i , we may use approximation procedures based on properties of the geometric series. Since $N - 1 \sim$ geometric $(p)$ ,

g_{N} (s) = \frac{p s}{1 - q s} = p s \sum_{k = 0}^{\infty} {(q s)}^{k} = p s [\sum_{k = 0}^{n} {(q s)}^{k} + \sum_{k = n + 1}^{\infty} {(q s)}^{k}] = p s [\sum_{k = 0}^{n} {(q s)}^{k} + {(q s)}^{n + 1} \sum_{k = 0}^{\infty} {(q s)}^{k}]

= p s [\sum_{k = 0}^{n}, {(q s)}^{k}] + {(q s)}^{n + 1} g_{N} (s) = g_{n} (s) + {(q s)}^{n + 1} g_{N} (s)

Note that $g_{n} (s)$ has the form of the generating function for a simple approximation N _n which matches values and probabilities with N up to $k = n$ . Now

g_{T} (s) = g_{n} [g_{Y} (s)] + {(q s)}^{n + 1} g_{N} [g_{Y} (s)]

The evaluation involves convolution of coefficients which effectively sets $s = 1$ . Since $g_{N} (1) = g_{Y} (1) = 1$ ,

{(q s)}^{n + 1} g_{N} [g_{Y} (s)] for s = 1 reduces to q^{n + 1} = P (N > n)

which is negligible if n is large enough. Suitable n may be determined in each case. With such an n , if the Y _i are nonnegative, integer-valued, we may use the gend procedure on $g_{n} [g_{Y} (s)]$ , where

g_{n} (s) = p s + p q s^{2} + p q^{2} s^{3} + \dots + p q^{n} s^{n + 1}

For the integer-valued case, as in the general case of simple Y _i , we could use mgd. However, gend is usually faster and more efficient for the integer-valued case. Unless q is small, the number of terms needed to approximate g _n is likely to be too great.

Approximating the generating function

Let $p = 0.3$ and Y be uniformly distributed on ${1, 2, \dots, 10}$ . Determine the distribution for

T = \sum_{k = 1}^{N} Y_{k}

SOLUTION

p = 0.3;
q = 1 - p;a = [30 35 40];          % Check for suitable nb = q.^a
b =  1.0e-04 *           % Use n = 400.2254    0.0379    0.0064
n = 40;k = 1:n;
gY = 0.1*[0 ones(1,10)];
gN = p*[0 q.^(k-1)];     % Probabilities, 0<= k<= 40
gendDo not forget zero coefficients for missing powers
Enter gen fn COEFFICIENTS for gN  gNEnter gen fn COEFFICIENTS for gY  gY
Values are in row matrix D; probabilities are in PD.To view the distribution, call for gD.
sum(PD)                % Check sum of probabilitiesans =  1.0000
FD = cumsum(PD);       % Distribution function for Dplot(0:100,FD(1:101))  % See
[link] P50 = (D<=50)*PD'
P50 =  0.9497P30 = (D<=30)*PD'
P30 =  0.8263

Got questions? Get instant answers now!

<< Chapter < Page Page > Chapter >>

Read also:

Get Jobilize Job Search Mobile App in your pocket Now!

100% Free Mobile Applications
Receive real-time job alerts and never miss the right job again

Source: OpenStax, Applied probability. OpenStax CNX. Aug 31, 2009 Download for free at http://cnx.org/content/col10708/1.6

Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Applied probability' conversation and receive update notifications?

Ask

	30 Biology 30 Plant Form and Physiology MCQ By OpenStax Start Quiz
©flickr: Gage	How well do you know Ross Lynch? By Brianna Beck Start Quiz
	2 Understanding Societies 2 By Jessica Collett Start Exam
	5 Psychology MCQ 2010 1 Exam By John Gabrieli Start Exam
©flickr: Francisco	U.S. Civil War Pre-test By Danielle Stephens Start Quiz
	Vocabulary Week 1-3 By Rachel Woolard Start Quiz
	27 AP 27 Reproductive System MCQ By OpenStax Start Quiz
	My OCA Mock By Mike Wolf Start Exam
	28 AP Key Terms 28 Development Inheritance By OpenStax Start Key Terms
	41 Biology 41 Osmotic Regulation and Excretion MCQ By OpenStax Start Quiz