Probability and Statistics with Reliability, Queuing, and Computer Science Applications ebook

Table of Contents

Cover

Title Page

Copyright

Preface to the Paperback Edition

Preface to the Second Edition

Preface to the First Edition

Acronyms

About the Companion Website

Chapter 1: Introduction

1.1 Motivation

1.2 Probability Models

1.3 Sample Space

1.4 Events

1.5 Algebra of Events

1.6 Graphical Methods of Representing Events

1.7 Probability Axioms

1.8 Combinatorial Problems

1.9 Conditional Probability

1.10 Independence of Events

1.11 Bayes' Rule

1.12 Bernoulli Trials

References

Chapter 2: Discrete Random Variables

2.1 Introduction

2.2 Random Variables and Their Event Spaces

2.3 The Probability Mass Function

2.4 Distribution Functions

2.5 Special Discrete Distributions

2.6 Analysis of Program MAX

2.7 The Probability Generating Function

2.8 Discrete Random Vectors

2.9 Independent Random Variables

References

Chapter 3: Continuous Random Variables

3.1 Introduction

3.2 The Exponential Distribution

3.3 The Reliability and Failure Rate

3.4 Some Important Distributions

3.5 Functions of a Random Variable

3.6 Jointly Distributed Random Variables

3.7 Order Statistics

3.8 Distribution of Sums

3.9 Functions of Normal Random Variables

References

Chapter 4: Expectation

4.1 Introduction

4.2 Moments

4.3 Expectation Based on Multiple Random Variables

4.4 Transform Methods

4.5 Moments and Transforms of Some Distributions

4.6 Computation of Mean Time to Failure

4.7 Inequalities and Limit Theorems

References

Chapter 5: Conditional Distribution and Expectation

5.1 Introduction

5.2 Mixture Distributions

5.3 Conditional Expectation

5.4 Imperfect Fault Coverage and Reliability

5.5 Random Sums

References

Chapter 6: Stochastic Processes

6.1 Introduction

6.2 Classification of Stochastic Processes

6.3 The Bernoulli Process

6.4 The Poisson Process

6.5 Renewal Processes

6.6 Availability Analysis

6.7 Random Incidence

6.8 Renewal Model of Program Behavior

References

Chapter 7: Discrete-Time Markov Chains

7.1 Introduction

7.2 Computation of n-step Transition Probabilities

7.3 State Classification and Limiting Probabilities

7.4 Distribution of Times Between State Changes

7.5 Markov Modulated Bernoulli Process

7.6 Irreducible Finite Chains with Aperiodic States

7.7 * The

M

/

G

/ 1 Queuing System

7.8 Discrete-Time Birth–Death Processes

7.9 Finite Markov Chains with Absorbing States

References

Chapter 8: Continuous-Time Markov Chains

8.1 Introduction

8.2 The Birth–Death Process

8.3 Other Special Cases of the Birth–Death Model

8.4 Non-Birth–Death Processes

8.5 Markov Chains with Absorbing States

8.6 Solution Techniques

8.7 Automated Generation

References

Chapter 9: Networks of Queues

9.1 Introduction

9.2 Open Queuing Networks

9.3 Closed Queuing Networks

9.4 General Service Distribution and Multiple Job Types

9.5 Non-product-form Networks

9.6 Computing Response Time Distribution

9.7 Summary

References

Chapter 10: Statistical Inference

10.1 Introduction

10.2 Parameter Estimation

10.3 Hypothesis Testing

References

Chapter 11: Regression and Analysis of Variance

11.1 Introduction

11.2 Least-squares Curve Fitting

11.3 The Coefficients of Determination

11.4 Confidence Intervals in Linear Regression

11.5 Trend Detection and Slope Estimation

11.6 Correlation Analysis

11.7 Simple Nonlinear Regression

11.8 Higher-dimensional Least-squares Fit

11.9 Analysis of Variance

References

Appendix A: Bibliography

A.1 Theory

A.2 Applications

Appendix B: Properties of Distributions

Appendix C: Statistical Tables

Appendix D: Laplace Transforms

References

Appendix E: Program Performance Analysis

Author Index

Subject Index

End User License Agreement

Pages

ix

xi

xii

xiii

xiv

xv

xvi

xvii

xix

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

528

529

530

531

532

533

534

535

536

537

538

539

540

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

571

572

573

574

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

647

648

649

650

651

652

653

654

655

656

657

658

659

661

662

663

664

665

666

667

668

669

670

671

672

673

674

675

676

677

678

679

680

681

682

683

684

685

686

687

688

689

690

691

692

693

694

695

696

697

698

699

700

701

702

703

704

705

706

707

708

709

710

711

712

713

714

715

716

717

718

719

720

721

722

723

724

725

726

727

728

729

730

731

732

733

734

735

736

737

738

739

740

741

742

743

744

745

746

747

748

749

750

751

753

754

755

756

757

758

759

760

761

762

763

764

765

766

767

768

769

770

771

772

773

774

775

776

777

778

779

780

781

782

783

784

785

786

787

788

789

790

791

792

793

794

795

796

797

798

799

800

801

802

803

804

805

806

807

808

809

810

811

812

813

814

815

816

817

818

819

820

821

822

823

824

825

826

828

829

830

831

832

833

834

835

837

838

839

840

841

842

843

845

846

847

848

849

850

851

852

853

854

855

856

857

Guide

Cover

Table of Contents

Preface to the Paperback Edition

Begin Reading

List of Illustrations

Chapter 1: Introduction

Figure 1.1 A one-dimensional sample space

Figure 1.2 A two-dimensional sample space

Figure 1.3 A one-dimensional sample space

Figure 1.4 Venn diagram for sample space

S

and events

A

and

B

Figure 1.5 Venn diagram of disjoint events

A

and

B

Figure 1.6 Venn diagram for two intersecting events

A

and

B

Figure 1.7 Venn diagram of

A

and its complement

Figure 1.8 Tree diagram of a sequential sample space

Figure 1.9 A two-dimensional sample space

Figure 1.10 Reliability curve of a parallel redundant system

Figure 1.11 A series–parallel reliability block diagram

Figure 1.12 A communication network with five nodes

Figure 1.13 Fault tree for the communication network

Figure 1.14 A fault tree

Figure 1.P.1 A network of communication channels

Figure 1.P.2 Reliability block diagrams

Figure 1.P.3 Lamp problem

Figure 1.P.4 A modified communication network

Figure 1.15 The theorem of total probability

Figure 1.16 A channel diagram

Figure 1.17 A non-series–parallel system

Figure 1.P.5 Another non-series–parallel system

Figure 1.P.6 A trinary communication channel: channel diagram

Figure 1.18 A CPU queue with time slicing

Figure 1.19 A triple modular redundant system

Figure 1.20 BTS sector/transmitter

Figure 1.21 Reliability block diagram when

2:1 combiner

and

duplexer 1

are up

Figure 1.22 System reliability block diagram

Figure 1.23 A CPU to I/O device queuing scheme

Figure 1.24 (a) Series configuration; (b) parallel configuration; (c) series–parallel configuration

Figure 1.P.7 Comparison of two redundancy schemes

Figure 1.P.8 A fault tree

Chapter 2: Discrete Random Variables

Figure 2.1 Tree diagram of a sequential sample space

Figure 2.2 Event space for three Bernoulli trials

Figure 2.3 Histogram of pmf for Example 2.1

Figure 2.4 Domain and range of

P

,

X

, pmf, and CDF

Figure 2.5 CDF of three Bernoulli trials

Figure 2.6 CDF of Bernoulli random variable

Figure 2.7 Comparing the model pmf with data of Example 2.4

Figure 2.8 Probability of acceptance versus fraction defective

Figure 2.9 Symmetric binomial pmf

Figure 2.11 Negatively skewed binomial pmf

Figure 2.10 Positively skewed binomial pmf

Figure 2.12 Geometric pmf

Figure 2.13 Poisson pmf

Figure 2.14 Discrete uniform distribution

Figure 2.15 CDF of constant random variable

Figure 2.16 Indicator random variable

Figure 2.17 Flowchart of MAX

Figure 2.18 Joint pmf for two-module execution problem

Figure 2.19 I/O queuing at the end of a CPU burst

Figure 2.20 Computing the pmf of the random variable

Figure 2.21 Theorem 2.2

Figure 2.22 Graph for two-module execution problem

Figure 2.P.1 A combinational circuit

Chapter 3: Continuous Random Variables

Figure 3.1 Relation between CDF and pdf

Figure 3.2 CDF of a mixed random variable

Figure 3.3 The CDF of an exponentially distributed random variable

Figure 3.4 Exponential pdf

Figure 3.5 Memoryless property of the exponential distribution ()

Figure 3.6 Failure rate as a function of time

Figure 3.7 Stress as a function of time

Figure 3.8 The pdf of the hypoexponential distribution

Figure 3.9 The CDF of the hypoexponential distribution

Figure 3.10 The failure rate of the hypoexponential distribution

Figure 3.11 The failure rate of the gamma distribution

Figure 3.12 The gamma pdf

Figure 3.13 The CPU service time distribution compared with the hyperexponential distribution.

Figure 3.14 Failure rate of the Weibull distribution with various values of and

Figure 3.15 Failure rate of log-logistic distribution with

Figure 3.16 Normal density with parameters and

Figure 3.17 Failure rate of the normal distribution

Figure 3.18 Normal approximation to the binomial pmf

Figure 3.19 The pdf of a uniform distribution

Figure 3.20 The CDF of a uniform distribution

Figure 3.21 The pdf of a Pareto distribution

Figure 3.22 The CDF of a Pareto distribution

Figure 3.23 The failure rate of a Pareto distribution

Figure 3.24 Defective distribution function

Figure 3.25 Generating a random deviate

Figure 3.26 Properties of joint CDF

Figure 3.27 Reliability of a parallel-redundant system

Figure 3.28 Comparison of TMR and simplex reliabilities

Figure 3.29 Comparison of

k

-out-of-

n

and simplex reliabilities

Figure 3.30 Reliability block diagram for the workstation–file server (WFS) example

Figure 3.31 Transmit and exchange operations of a switching element

Figure 3.32 An SEN

Figure 3.33 A SEN and a SEN+

Figure 3.34 Series–parallel reliability block diagram of SEN+

Figure 3.35 An SEN+

Figure 3.36 Area of integration for the convolution of

X

and

Y

Figure 3.37 The area of integration for Example 3.24

Figure 3.38 Reliabilities of simplex and two-component standby systems

Figure 3.39 Computing capacity as a function of time

Figure 3.40 Hypoexponential as a series of exponential stages

Figure 3.41 Comparison of simplex, TMR, and TMR/simplex reliabilities

Figure 3.42 A module with an online fault detector

Figure 3.43 The order statistics of the exponential distribution

Figure 3.44 Lifetime distribution of a hybrid

k

-out-of-

n

system

Figure 3.45 The area of integration for Example 3.35

Figure 3.46 The area of integration for computing the CDF of

Figure 3.47 Student's

t

pdf and its comparison with standard normal pdf

Chapter 4: Expectation

Figure 4.P.1 An alternative method of computing

Figure 4.1 The pdf of a “concentrated” distribution

Figure 4.2 The pdf of a diffuse distribution

Figure 4.3 Two areas of integration for Example 4.7

Figure 4.4 The variation in the expected life with the degree of (parallel) redundancy (simplex failure rate )

Figure 4.P.2 A system with dependent failures

Chapter 5: Conditional Distribution and Expectation

Figure 5.1 Illustration for

Figure 5.2 The hyperexponential distribution as a set of parallel exponential stages

Figure 5.3 The pdf of a mixture of exponential and Erlang

Figure 5.4 Hazard rate of a mixture of exponential and Erlang

Figure 5.P.1 Flowchart of automatic fault recovery

Figure 5.5 Three phases of fault handling

Figure 5.6 Reliability of two-component standby system with imperfect coverage

Figure 5.7 The unit-step function: CDF of a constant random variable,

Figure 5.8 The stage-type distribution of system lifetime for the system in Example 5.16

Figure 5.9 Tree diagram for Example 5.17

Figure 5.10 Lifetime distribution of a two-component warm standby system with imperfect coverage

Figure 5.11 Coxian stage-type distribution

Figure 5.12 Lifetime distribution of an

n

-component standby redundant system with imperfect coverage

Figure 5.13 Lifetime distribution of hybrid

k

-out-of-

n

system with imperfect coverage

Chapter 6: Stochastic Processes

Figure 6.1 Noise voltages across two resistors

Figure 6.2 A queuing system

Figure 6.3 Typical sample function of a discrete-time, discrete-state process

Figure 6.4 Typical sample function of a continuous-time, discrete-state process

Figure 6.5 Typical sample function of a discrete-time, continuous-state process

Figure 6.6 Typical sample function of a continuous-time, continuous-state process

Figure 6.7 Typical sample function of the telegraph process

Figure 6.8 Autocorrelation function of the telegraph process

Figure 6.9 The tree diagram for WWW request

Figure 6.10 State transitions of the Poisson process

Figure 6.11 Pooling two Poisson streams

Figure 6.12 Superposition of independent Poisson processes

Figure 6.13 Decomposition of a Poisson process

Figure 6.14 A realization of a sequence of failures and repairs

Figure 6.15 A realization of the process corresponding to Figure 6.14

Figure 6.16 Reliability, instantaneous availability, interval availability, and limiting availability as functions of time ( and )

Figure 6.17 Random incidence

Chapter 7: Discrete-Time Markov Chains

Figure 7.1 The state diagram of a two-state Markov chain

Figure 7.2 A channel diagram

Figure 7.3 The state diagram of the two-state Markov chain of Example 7.5

Figure 7.4 The state diagram of a two-state periodic Markov chain

Figure 7.5 The state classification of discrete-time Markov chains

Figure 7.6 The state diagram of a Markov chain with one absorbing state and one transient state

Figure 7.7 A discrete-time Markov model of a program

Figure 7.8 Non-homogeneous DTMC model for software reliability growth

Figure 7.9 A multiprocessor system with multimodule memory

Figure 7.10 A discrete-time queuing network representation of multiprocessor memory interference

Figure 7.11 The state diagram for an example of the memory interference problem

Figure 7.12 Different cache organizations: (a) fully associative; (b) direct-mapped; (c) set-associative

Figure 7.13 Markov chain for the directly mapped cache

Figure 7.14 LRU stack updating procedure

Figure 7.15 The state diagram for the LRU-stack example

Figure 7.16 The state diagram of the DTMC for slotted Aloha

Figure 7.17 an ATM multiplexer

Figure 7.18 DTMC for the queue length of an ATM multiplexer

Figure 7.P.1 The queue with Bernoulli feedback

Figure 7.19 The state diagram of the discrete-time birth-death process

Figure 7.20 The state diagram for Example 7.16

Figure 7.21 Two stacks sharing an area of memory

Figure 7.22 Tree diagram for Example 7.17

Figure 7.23 The state diagram for the two-stacks example

Figure 7.24 A program flow graph

Figure 7.25 A program flow graph

Figure 7.26 A program flow graph with failure state

Figure 7.P.2 Another program flow graph

Chapter 8: Continuous-Time Markov Chains

Figure 8.1 The state diagram of the birth–death process

Figure 8.2 The queuing system

Figure 8.3 Expected number of jobs in system versus traffic intensity

Figure 8.4 Average response time versus traffic intensity

Figure 8.5 The queuing system

Figure 8.6 The state diagram of the queue

Figure 8.7 Queuing schemes: (a) separate queues; (b) common queue

Figure 8.8 Queuing schemes for Example 8.4: (a) separate queues; (b) common queue

Figure 8.9 State diagram of a birth–death process with a finite state space

Figure 8.10 queuing system

Figure 8.11 state diagram

Figure 8.12 Task completion time distribution

Figure 8.13 The cyclic queuing model of a multiprogramming system

Figure 8.14 The state diagram for the cyclic queuing model

Figure 8.15 The CPU utilization as a function of the degree of multiprogramming

Figure 8.P.1 Two CTMCs

Figure 8.16 The state diagram of a finite-population queuing system

Figure 8.17 Service slot availability model

Figure 8.18 A client–server system

Figure 8.19 Average response time as a function of the number of clients

Figure 8.20 CTMC for the wireless handoff model

Figure 8.21 State diagram of the Poisson process

Figure 8.22 Nonhomogeneous Poisson process

Figure 8.23 The state diagram of a death process with a linear death rate

Figure 8.24 The state diagram for Example 8.19

Figure 8.25 CTMC for preventive maintenance model

Figure 8.26 Steady-state availability of the preventive maintenance model with different

Figure 8.27 Two-component system availability model

Figure 8.28 Two-component system with fault detection delay

Figure 8.29 Downtime of two-component system with fault detection delay

Figure 8.30 Two-component availability model with imperfect coverage

Figure 8.31 Downtime due to imperfect coverage

Figure 8.32 Two-component availability model with imperfect coverage and detection delay

Figure 8.33 Downtime due to imperfect coverage and detection delay

Figure 8.34 CTMC availability model for the WFS example

Figure 8.35 CTMC for the 2-node cluster system

Figure 8.36 CTMC model for Web server with cold replication

Figure 8.37 Differentiating between failures of the active and spare units

Figure 8.38 A semi-Markov model

Figure 8.39 Difference in downtime of the SMP model and the approximate CTMC model

Figure 8.40 Top-level model for Example 8.28

Figure 8.41 heterogeneous system

Figure 8.42 The state diagram for the heterogeneous queue

Figure 8.43 The counting process of MMPP with three states

Figure 8.44 State diagram for the queue

Figure 8.45 State diagram for the Erlang loss availability model

Figure 8.46 State diagram for the Erlang loss performance model

Figure 8.47 State diagram for the Erlang loss composite model

Figure 8.48 Total blocking probability in the Erlang loss model

Figure 8.49 State diagram for the multiprocessor availability model

Figure 8.50 Downtime Vs. the number of processors

Figure 8.51 Queuing system for the multiprocessor performance model

Figure 8.52 State diagram for the multiprocessor performance model

Figure 8.53 Total loss probability for a multiprocessor model

Figure 8.54 Markov chain of availability model

Figure 8.56 versus

g

for systems without APS and with APS (top); percentage of unavailability in (bottom)

Figure 8.57 versus

g

for systems without APS and with APS (top); percentage of unavailability in (bottom)

Figure 8.57 and versus

N

b

and

g

for system without APS (top) and with APS (bottom)

Figure 8.58 The state diagram for Example 8.34

Figure 8.59 The state diagram of a duplex system with imperfect coverage

Figure 8.60 The effect of coverage on

Figure 8.61 The NHCTMC model of the duplex system

Figure 8.62 The state diagram of a TMR system with spare and imperfect coverage

Figure 8.63 The stage-type lifetime distribution for the system of Example 8.37

Figure 8.65 CTMC reliability model for the WFS example with repair

Figure 8.66 CTMC reliability model for the WFS example without repair

Figure 8.66 RBD of workstations and file server system

Figure 8.67 CTMC for operational security

Figure 8.68 The state diagram for Example 8.40

Figure 8.69 Architectures of fault-tolerant systems: (a) system S; (b) system D; (c) system DS

Figure 8.70 A CTMC with

m

absorbing states

Figure 8.71 Multiprocessor system reliability model

Figure 8.72 Multiprocessor system reliability model with hard-deadline failures

Figure 8.P.2 A two-unit system with nonzero detection latency

Figure 8.P.3 An aggregated version of Figure 8.P.2

Figure 8.P.4 Stiffler's coverage model

Figure 8.73 Two-state availability model of Example 8.44

Figure 8.74 (a) A noncovergent CTMC; (b) reordered convergent CTMC

Figure 8.75 An example of a Petri net

Figure 8.76 Reachability graph of the Petri net for Example 8.48

Figure 8.77 SPN model of a Poisson process

Figure 8.78 Reachability Graph of the Poisson process

Figure 8.79 SPN model of queue

Figure 8.80 Reachability graph of the SPN model of queue

Figure 8.81 SPN model of queue

Figure 8.82 Reachability graph of the SPN model of queue

Figure 8.83 A GSPN model of queue

Figure 8.84 Extended reachability graph of the GSPN model of

M/E

m

/

1

/n

+ 1 queue

Figure 8.85 CTMC derived from the GSPN model of queue

Figure 8.86 A GSPN model of queue

Figure 8.87 A GSPN model of queue

Figure 8.88 The reachability graph of Example 8.54 ()

Figure 8.89 SRN for the WFS example

Figure 8.90 Reachability graph of Example 8.55

Figure 8.91 SRN for WFS example with imperfect coverage

Figure 8.92 SRN for WFS with complex failure and repair dependency

Figure 8.93 The SRN of wireless loss model

Figure 8.94 The SRN for the producer-consumer system

Figure 8.95 SRN of a multiprocessor model

Chapter 9: Networks of Queues

Figure 9.1 A two-stage tandem network

Figure 9.2 The state diagram for the two-stage tandem network

Figure 9.3 Portion of the state diagram for equation (9.1)

Figure 9.4 (a) An open network with feedback; (b) an “equivalent” network without feedback

Figure 9.5 State diagram for the network in Figure 9.4a

Figure 9.6 The open central server network

Figure 9.P.1 queue with Bernoulli feedback

Figure 9.7 An open central server network with a blocking

Figure 9.8 The (closed) central server model

Figure 9.9 The closed cyclic queuing model

Figure 9.10 State spaces for two-node networks

Figure 9.11 The state diagram for the closed cyclic queuing model

Figure 9.12 Average system throughput versus degree of multiprogramming

Figure 9.13 Demonstration of the thrashing phenomenon

Figure 9.14 Queuing model of Example 9.10

Figure 9.15 Average response time versus number of terminals

Figure 9.16 Queuing model of Example 9.11

Figure 9.17 Average response time versus number of clients

Figure 9.18 Closed queuing network model of Example 9.12

Figure 9.19 Two-phase hyperexponential CPU service time distribution

Figure 9.20 State diagram for the system of Example 9.13

Figure 9.21 The state diagram for the central server network with two job types

Figure 9.22 Equivalent server queuing system

Figure 9.23 The behavior of the average response time as a function of the number of partitions and the arrival rate

Figure 9.24 A terminal-oriented system with a limited number of memory partitions

Figure 9.25 SRN model of terminal-oriented system with limited memory

Figure 9.26 Upper level model

Figure 9.27 Plot of average response time for Example 9.18

Figure 9.28 SRN model of the two-node system with multiple processors

Figure 9.29 CTMC model for the two-node system with multiple processors

Figure 9.P.2 Another terminal-oriented system

Figure 9.30 CTMC for response time distribution approximation of model in Figure 9.4a

Figure 9.31 CTMC for response time distribution approximation of model in Figure 9.4b

Figure 9.32 Response time distribution for networks of Figure 9.4, versions a and b

Figure 9.33 CTMC for response time distribution approximation of model in Example 9.3

Figure 9.34 Response time distribution for Example 9.3.

Figure 9.35 The response time block

Figure 9.36 The response time block

Figure 9.37 The response time block

Figure 9.38 Distributed system queuing network

Figure 9.39 CTMC corresponding to response time distribution

Figure 9.41 Response time distribution of distributed system

Figure 9.40 GSPN model for calculating the response time distribution

Figure 9.42 Central server model of a computer system

Figure 9.43 CTMC model of the CSM for computing the response time distribution

Figure 9.44 CTMC model for computing the steady-state probabilities of the non-tagged customer

Figure 9.45 Response time distribution for different number of customers

Chapter 10: Statistical Inference

Figure 10.1

Figure 10.2 Comparing the standard normal pdf with the pdf of the

t

distribution with 3 degrees of freedom

Figure 10.3

Figure 10.4

Figure 10.5 Weibull estimation

Figure 10.6 90% confidence intervals of error-detection coverage [I—initial (physical fault injection); CPV—checking for protocol violations (simulated fault injection); LCL—lower confidence limit; UCL—upper confidence limit.]

Figure 10.7 Two-state CTMC

Figure 10.8 Number of samples

n

versus lower boundary,

Figure 10.9 Acceptance and rejection regions for a two-sided test

Figure 10.10 Acceptance and rejection regions for a one-sided test

Figure 10.11 Probability of false alarm as a function of test stringency and sample size

n

Figure 10.12 Computing types I and II errors

Figure 10.13 A typical power curve for a two-tailed test

Figure 10.14 A typical power curve for a one-tailed test

Figure 10.15 A nonparametric test

Figure 10.16 The Kolmogorov–Smirnov test for a small sample size

Figure 10.17 The Kolmogorov–Smirnov test for a large sample size

Figure 10.18 Probabilityplot with exponential distribution assumption

Figure 10.19 Probability plot with Weibull distribution assumption

Chapter 11: Regression and Analysis of Variance

Figure 11.1 A scatter diagram showing a linear dependence

Figure 11.2 A scatter diagram showing a nonlinear dependence

Figure 11.3 A scatter diagram showing no specific dependence

Figure 11.4 Least-squares linear fit

Figure 11.5 Nonlinear curve fitting

Appendix D: Laplace Transforms

Figure D.1 Solution of a linear differential equation using Laplace transform procedure

List of Tables

Chapter 1: Introduction

Table 1.1 Sample Points

Chapter 6: Stochastic Processes

Table 6.1 A classification of stochastic processes

Table 6.2 Random-request Availability,

Chapter 8: Continuous-Time Markov Chains

Table 8.1 Measures for the system

Table 8.2 Availability of a standby redundant system

Table 8.3 Availabilities for parallel redundant system

Table 8.4 State indices

Table 8.5 Average response times

Table 8.6 Reward rates for systems without APS

Table 8.7 Reward rates for systems with APS

Table 8.8 Parameters used in numerical study

Table 8.9 Parameters for Example 8.40

Table 8.10 Dependability measures for the three architectures

Table 8.11 Firing rates for transitions in the producer-consumer SRN

Chapter 9: Networks of Queues

Table 9.1 Computation of the Normalization Constant

Table 9.2 Parameters of Example 9.6

Table 9.3 Computation of the Normalization Constant

Table 9.4 Average System Throughput (Jobs Completed per Second)

Table 9.5 Parameters for Example 9.7

Table 9.6 Normalization Constant for Load-dependent Servers

Table 9.7 Results for Example 9.9

Table 9.8 Networks with Product-form Solutions

Table 9.9 Parameters for Example 9.16

Table 9.10

Table 9.11 Parameters of Figure 9.24

Table 9.12 The numbers of states and the numbers of nonzero entries in the

Q

matrix when and

Table 9.13 Comparing the Exact and Approximate Values of Mean Response Time

Chapter 10: Statistical Inference

Table 10.1 Critical Values of

N

(0,1)

Table 10.2 Statistics for the workload variables measured

Table 10.3 Statistics for the workload clusters

Table 10.4 Sojourn time distributions in the workload states

Table 10.5 Comparison of state occupancy probabilities (expressed as percentage)

Table 10.6 Fitting a Poisson model

Chapter 11: Regression and Analysis of Variance

Table 11.1 The failure rate versus temperature

Table 11.2 The failure rate data for a Weibull model

Table 11.3 Observations for one-way analysis of variance

Table 11.4 One-way ANOVA table

Table 11.5 Observations for two-way analysis of variance

Table 11.6 Two-way ANOVA with interaction

Table 11.7 ANOVA Table for Example 11.11

Appendix D: Laplace Transforms

Table D.1 Important transform pairs

Table D.2 Properties of Laplace tansforms

Probability and Statistics with Reliability, Queuing, and Computer Science Applications

Copyright © 2016 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New Jersey Published simultaneously in Canada Hardcover edition originally published as per part of Wiley-Interscience

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permissions.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Names: Trivedi, Kishor S., 1946- author.

Title: Probability and statistics with reliability, queuing, and computer science applications / Kishor S. Trivedi, Duke University, Durham, North Carolina.

Description: Hoboken, NJ : John Wiley & Sons, Inc., [2016] | Includes bibliographical references and index.

Identifiers: LCCN 2016010100 (print) | LCCN 2016013554 (ebook) | ISBN 9781119285427 (pbk. : acid-free paper) | ISBN 9780471460817 (pdf)

Subjects: LCSH: Probabilities--Data processing. | Mathematical statistics-Data processing. | Computer algorithms. | Engineering mathematics. | Reliability Engineering. | Computer Performance. | Queuing Theory. | Fault Tolerant Computing. | Software Reliability.

Classification: LCC QA273.19.E4 T74 2016 (print) | LCC QA273.19.E4 (ebook) |

DDC 519.5-dc23

LC record available at http://lccn.loc.gov/2016010100

Preface to the Paperback Edition

Nearly 15 years have passed since the publication of the second edition of this book by John Wiley. Indian edition (of the first edition this book from 1982), published by Prentice-Hall India, is still in print and doing quite well. Asian edition (of the second edition from 2001) is published by John Wiley Asia. In 2015, a Chinese translation of the second edition has been published. I did not see the need for adding or subtracting significant amount of material to produce a new, third edition of the “bluebook” as it is popularly known. However, I took the opportunity to correct nearly 100 minor errors from the book before supplying the camera ready copy to the publisher. I have added some more terms in the subject index leading to an extra page at the end. Thus, though this is not a new edition, it is a significant new reprint. I like to remind the readers that a complete solution manual is available to instructors as well the power point slides of all chapters. Instructors may also wish to use the SHARPE software package as a pedagogic aid. (See http://sharpe.pratt.duke.edu/ for further details.)

I wish to thank many friends for pointing out and/or help fix the errors—Javier Alonso López, Yonghuan Cao, Xiaolin Chang, Olivia Das, Jie Feng, Marcos A. M. Ferreira, Lance Fiondella, Ravi Iyer, Michael Kwok, Bharat Madan, José M. Martínez, Rivalino Matias, Jr., Kesari Mishra, Yan Qu, Dharmaraja Selvamuthu, Vibhu Sharma, Harish Sukhwani, Alex Thomasian and (late) Ranjith Vasireddy.

Kishor S. Trivedi

Preface to the Second Edition

Nearly 20 years have passed since the publication of the first edition of this book. Its Indian edition is still in print and doing quite well. In this second edition, I have thoroughly revised all the chapters. Many examples and problems are updated, and many new examples and problems have been added. There is a considerable addition of examples on system availability modeling, wireless system performance and availability modeling, software reliability modeling, and system performability modeling. New material on fault trees and stochastic Petri nets, and numerical solution techniques for Markov chains has been added. A section on the computation of response time distribution for Markovian queuing networks has also been added. Chapter 8, on continuous-time Markov chains, has undergone the most change. My research experience and the application of these methods in practice for the past 25 years (at the time of writing) have been distilled in these chapters as much as possible. I hope that the book will be of use as a classroom textbook as well as of use for practicing engineers. Researchers will also find valuable material here. I have tried to avoid adding excessive and very advanced material. Thus, for instance, I have omitted discussion of Markov regenerative processes, fluid stochastic Petri nets, and binary decision diagrams. Other topics that are omitted include material on self-similarity, large deviation theory, and diffusion approximation. The topic of hierarchical and fixed-point iterative models is covered very briefly. Modeling software fault tolerance with various kinds of correlation is also excluded.

I wish to thank many of my current students—Yonghuan Cao, Dong Chen, Dongyan Chen, Christophe Hirel, Lei Li, Yun Liu, Rajiv Poonamalli, Srinivasan Ramani, Kalyan Vaidyanathan, Wei Xie, and Liang Yin; current postdoctoral associates—Dr. Katerina Goseva-Popstojanova, Dr. Yiguang Hong, Dr. Xiaomin Ma, and Dr. Dharmaraja Selvamuthu; former students—Dr. Hoon Choi, Dr. Gianfranco Ciardo, Dr. Ricardo Fricks, Dr. Sachin Garg, Dr. Swapna Gokhale, Wei Li, Xuemei (Judith) Lou, Dr. Tong Luo, Dr. Yue Ma, Dr. Varsha Mainkar, Dr. Manish Malhotra, Anu Mohan, Dr. Jogesh Muppala, Hu Pan, Dr. Anapathur Ramesh, Dr. Robin Sahner, Kartik Sudeep, Dr. Steve Woolet, and Dr. Xinyu (Henry) Zang; former postdoctoral associates—Dr. Hairong Sun and Dr. Bruno Tuffin; and other friends—Prof. Tadashi Dohi, Dr. Zahava Koren, Prof. Igor Kovalenko, Prof. Kang Lee, Dr. Bharat Madan and Prof. Alex Thomasian.

Kishor S. Trivedi

Preface to the First Edition

The aim of this book is to provide an introduction to probability, stochastic processes, and statistics for students of computer science, electrical/computer engineering, reliability engineering, and applied mathematics. The prerequisites are two semesters of calculus, a course on introduction to computer programming, and preferably, a course on computer organization.

I have found that the material in the book can be covered in a two-semester or three-quarter course. However, through a choice of topics, shorter courses can also be organized. I have taught the material in this book to seniors and first-year graduate students but with the text in printed form, it could be given to juniors as well.

With a specific audience in mind, I have attempted to provide examples and problems, with which the student can identify, as motivation for the probability concepts. The majority of applications are drawn from reliability analysis and performance analysis of computer systems and from probabilistic analysis of algorithms. Although there are many good texts on each of these application areas, I felt the need for a text that treats them in a balanced fashion.

Chapters 1–5 provide an introduction to probability theory. These five chapters provide the core for one semester course on introduction to applied probability. Chapters 6–9 deal with stochastic processes and their applications. These four chapters form the core of the second course with a title such as systems modeling. I have included an entire chapter on networks of queues. The last two chapters are on statistical inference and regression, respectively. I have placed the material on sampling distributions in Chapter 3 dealing with continuous random variables. Portions of the chapters on statistics can be taught with the first course and other portions in the second course.

Besides more than 200 worked examples, most sections conclude with a number of exercises. Difficult exercises are indicated by a star. A solution manual for instructors is available from the publisher.

I am indebted to the Department of Computer Science, Duke University and to Merrell Patrick for their encouragement and support during this project. The efficient typing skills of Patricia Land helped make the job of writing the book much easier than it could have been.

Many of my friends, colleagues, and students carefully read several drafts and suggested many changes that improved the readability and the accuracy of this text. Many thanks to Robert Geist, Narayan Bhat, Satish Tripathi, John Meyer, Frank Harrell, Veena Adlakha, and Jack Stiffler for their suggestions. Joey de la Cruz and Nelson Strothers helped in the editing and the typing process very early in the project. The help by the staff of Prentice-Hall in preparation of the book is also appreciated.

I would like to thank my wife Kalpana, and my daughters Kavita and Smita for enduring my preoccupation with this work for so long. The book is dedicated to my parents.

Kishor S. Trivedi

Acronyms

APS

automatic protection switching

ARQ

automatic repeat request

ATM

asynchronous transfer mode

BCC

blocked calls cleared

BDD

binary decision diagram

BER

bit error rate

BR

base radio

BTS

base–transceiver system

CDF

cumulative distribution function

CFR

constant failure rate

CME

conditional mean exceedance

CPU

central processing unit

CRTD

conditional response time distribution

CSM

central server model

CTMC

continuous-time Markov chain

DFR

decreasing failure rate

DTMC

discrete-time Markov chain

ESS

electronic switching system

FCFS

first come, first served

FIFO

first in, first out

FIT

failure in time

FTREE

fault tree

GBN

Go Back N

GMR

general(ized) multiplication rule

GSPN

generalized stochastic Petri net

IBP

interrupted Bernoulli process

IFR

increasing failure rate

I/O

input output

IRM

independent reference model

IS

infinite server

ISP

Internet service provider

LAN

local area network

LCFS

last come, first served

LCFS-PR

LCFS-preemptive resume

LCL

lower confidence limit

LLC

logical link control

LRU

least recently used

LST

Laplace–Stieltjes transform

LT

Laplace transform

MAC

medi(um)(a) access control

MAP

Markovian arrival process

METF

mean effort to (security) failure

MGF

moment generating function

MLE

maximum-likelihood estimator

MMBP

Markov modulated Bernoulli process

MMPP

Markov modulated Poisson process

MRM

Markov reward model

MTBF

mean time between failures

MTTF

mean time to failure

MTTR

mean time to repair

MVA

mean-value analysis

NHCTMC

Nonhomogeneous CTMC

NHPP

Nonhomogeneous Poisson process

NPFQN

Non-product-form queuing network(s)

ODE

ordinary differential equation

PASTA

Poisson arrivals see time averages

PN

Petri net

pdf

probability density function

PFQN

Product-form queuing network(s)

pmf

probability mass function

prs

preemptive resume

prt

preemptive repeat

PS

processor sharing

QoS

quality of service

RBD

reliability block diagram

RG

reliability graph

RR

round robin

SDP

sum of disjoint products

SEN

shuffle exchange network

SHARPE

symbolic hierarchical automated reliability and

performance evaluator

SLTF

shortest latency time first

SMP

semi-Markov process

SOR

successive overrelaxation

SPN

stochastic Petri net

SPNP

stochastic Petri net package

SREPT

software reliability estimation and prediction tool

SRGM

software reliability growth model

SRM

Software reliability model

SRN

stochastic reward net

SRPTF

shortest remaining processing time first

TDMA

time division multiple access

TLP

total loss probability

TMR

triple modular redundancy

UBT

upside-down bathtub

UCL

upper confidence limit

URTD

unconditional response time distribution

VLSI

very large scale integrated (circuits)

WFS

workstation–file server (system)

About the Companion Website

This book is accompanied by a password protected companion website for instructors only.

This website contains:

Course Slides

Solutions Manual

To access the material on the instructor's website simply visit www.wiley.com/go/trivedi/probabilityandstatistics2e and follow the instructions for how to register.

Chapter 1Introduction

1.1 Motivation

Computer scientists and engineers need powerful techniques to analyze algorithms and computer systems. Similarly, networking engineers need methods to analyze the behavior of protocols, routing algorithms, and congestion in networks. Computer systems and networks are subject to failure, and hence methods for their reliability and availability are needed. Many of the tools necessary for these analyses have their foundations in probability theory. For example, in the analysis of algorithm execution times, it is common to draw a distinction between the worst-case and the average-case behavior of an algorithm. The distinction is based on the fact that for certain problems, while an algorithm may require an inordinately long time to solve the least favorable instance of the problem, the average solution time is considerably shorter. When many instances of a problem have to be solved, the probabilistic (or average-case) analysis of the algorithm is likely to be more useful. Such an analysis accounts for the fact that the performance of an algorithm is dependent on the distributions of input data items. Of course, we have to specify the relevant probability distributions before the analysis can be carried out. Thus, for instance, while analyzing a sorting algorithm, a common assumption is that every permutation of the input sequence is equally likely to occur.

Similarly, if the storage is dynamically allocated, a probabilistic analysis of the storage requirement is more appropriate than a worst-case analysis. In a like fashion, a worst-case analysis of the accumulation of roundoff errors in a numerical algorithm tends to be rather pessimistic; a probabilistic analysis, although harder, is more useful.

When we consider the analysis of a Web server serving a large number of users, several types of random phenomena need to be accounted for. First, the arrival pattern of requests is subject to randomness due to a large population of diverse users. Second, the resource requirements of requests will likely fluctuate from request to request as well as during the execution of a single request. Finally, the resources of the Web server are subject to random failures due to environmental conditions and aging phenomena. The theory of stochastic (random) processes is very useful in evaluating various measures of system effectiveness such as throughput, response time, reliability, and availability.

Before an algorithm (or protocol) or a system can be analyzed, various probability distributions have to be specified. Where do the distributions come from? We may collect data during the actual operation of the system (or the algorithm). These measurements can be performed by hardware monitors, software monitors, or both. Such data must be analyzed and compressed to obtain the necessary distributions that drive the analytical models discussed above. Mathematical statistics provides us with techniques for this purpose, such as the design of experiments, hypothesis testing, estimation, analysis of variance, and linear and nonlinear regression.

1.2 Probability Models

Probability theory is concerned with the study of random (or chance) phenomena. Such phenomena are characterized by the fact that their future behavior is not predictable in a deterministic fashion. Nevertheless, such phenomena are usually capable of mathematical descriptions due to certain statistical regularities. This can be accomplished by constructing an idealized probabilistic model of the real-world situation. Such a model consists of a list of all possible outcomes and an assignment of their respective probabilities. The theory of probability then allows us to predict or deduce patterns of future outcomes.

Since a model is an abstraction of the real-world problem, predictions based on the model must be validated against actual measurements collected from the real phenomena. A poor validation may suggest modifications to the original model. The theory of statistics facilitates the process of validation. Statistics is concerned with the inductive process of drawing inferences about the model and its parameters based on the limited information contained in real data.

The role of probability theory is to analyze the behavior of a system or an algorithm assuming the given probability assignments and distributions. The results of this analysis are as good as the underlying assumptions. Statistics helps us in choosing these probability assignments and in the process of validating model assumptions. The behavior of the system (or the algorithm) is observed, and an attempt is made to draw inferences about the underlying unknown distributions of random variables that describe system activity. Methods of statistics, in turn, make heavy use of probability theory.

Consider the problem of predicting the number of request arrivals to a Web server in a fixed time interval (0,t]. A common model of this situation is to assume that the number of arrivals in this period has a particular distribution, such as the Poisson distribution (see Chapter 2). Thus we have replaced a complex physical situation by a simple model with a single unknown parameter, namely, the average arrival rate . With the help of probability theory we can then deduce the pattern of future arrivals. On the other hand, statistical techniques help us estimate the unknown parameter based on actual observations of past arrival patterns. Statistical techniques also allow us to test the validity of the Poisson model.

As another example, consider a fault-tolerant computer system with automatic error recovery capability. Model this situation as follows. The probability of successful recovery is c and probability of an abortive error is . The uncertainty of the physical situation is once again reduced to a simple probability model with a single unknown parameter c. In order to estimate parameter c in this model, we observe N errors out of which n are successfully recovered. A reasonable estimate of c is the relative frequency n/N, since we expect this ratio to converge to c in the limit . Note that this limit is a limit in a probabilistic sense:

Axiomatic approaches to probability allow us to define such limits in a mathematically consistent fashion (e.g., see the law of large numbers in Chapter 4) and hence allow us to use relative frequencies as estimates of probabilities.

1.3 Sample Space

Probability theory is rooted in the real-life situation where a person performs an experiment the outcome of which may not be certain. Such an experiment is called a random experiment. Thus, an experiment may consist of the simple process of noting whether a component is functioning properly or has failed; it may consist of determining the execution time of a program; or it may consist of determining the response time of a server request. The result of any such observations, whether they are simple “yes” or “no” answers, meter readings, or whatever, are called outcomes of the experiment.

Definition Sample Space

The totality of the possible outcomes of a random experiment is called the sample space of the experiment and it will be denoted by the letter S.

We point out that the sample space is not determined completely by the experiment. It is partially determined by the purpose for which the experiment is carried out. If the status of two components is observed, for some purposes it is sufficient to consider only three possible outcomes: two functioning, two malfunctioning, one functioning and one malfunctioning. These three outcomes constitute the sample space S. On the other hand, we might be interested in exactly which of the components has failed, if any has failed. In this case the sample space S must be considered as four possible outcomes where the earlier single outcome of one failed, one functioning is split into two outcomes: first failed, second functioning and first functioning, second failed. Many other sample spaces can be defined if we take into account such things as type of failure and so on.

Frequently, we use a larger sample space than is strictly necessary because it is easier to use; specifically, it is always easier to discard excess information than to recover lost information. For instance, in the preceding illustration, the first sample space might be denoted (where each number indicates how many components are functioning) and the second sample space might be denoted (where 0 = failed, 1 = functioning). Given a selection from S2, we can always add the two components to determine the corresponding choice from S1; but, given a choice from S1 (in particular 1), we cannot necessarily recover the corresponding choice from S2.

It is useful to think of the outcomes of an experiment, the elements of the sample space, as points in a space of one or more dimensions. For example, if an experiment consists of examining the state of a single component, it may be functioning properly (denoted by the number 1), or it may have failed (denoted by the number 0). The sample space is one-dimensional, as shown in Figure 1.1. If a system consists of two components there are four possible outcomes, as shown in the two-dimensional sample space of Figure 1.2. Here each coordinate is 0 or 1 depending on whether the corresponding component is functioning properly or has failed. In general, if a system has n components, there are possible outcomes each of which can be regarded as a point in an n-dimensional sample space. It should be noted that the sample space used here in connection with the observation of the status of components could also serve to describe the results of other experiments; for example, the experiment of observing n successive executions of an if statement, with 1 denoting the execution of the then clause and 0 denoting the execution of the else clause.

Figure 1.1 A one-dimensional sample space

Figure 1.2 A two-dimensional sample space

The geometric configuration that is used to represent the outcomes of an experiment (e.g., Figure 1.2) is not necessarily unique. For example, we could have regarded the outcomes of the experiment of observing the two-component system to be the total number functioning, and the outcomes would be 0,1,2, as depicted in the one-dimensional sample space of Figure 1.3. Note that point 1 in Figure 1.3 corresponds to points (0,1) and (1,0) in Figure 1.2. It is often easier to use sample spaces whose elements cannot be further “subdivided”; that is, the individual elements of a sample space should not represent two or more outcomes that are distinguishable in some fashion. Thus, sample spaces like those of Figures 1.1 and 1.2 should be used in preference to sample spaces like the one in Figure 1.3.

Figure 1.3 A one-dimensional sample space

It is convenient to classify sample spaces according to the number of elements they contain. If the set of all possible outcomes of the experiment is finite, then the associated sample space is a finite sample space. Thus, the sample spaces of Figures 1.1–1.3 are finite sample spaces.