Skip to main content
main-content

Über dieses Buch

This new edition includes the latest advances and developments in computational probability involving A Probability Programming Language (APPL). The book examines and presents, in a systematic manner, computational probability methods that encompass data structures and algorithms. The developed techniques address problems that require exact probability calculations, many of which have been considered intractable in the past. The book addresses the plight of the probabilist by providing algorithms to perform calculations associated with random variables.
Computational Probability: Algorithms and Applications in the Mathematical Sciences, 2nd Edition begins with an introductory chapter that contains short examples involving the elementary use of APPL. Chapter 2 reviews the Maple data structures and functions necessary to implement APPL. This is followed by a discussion of the development of the data structures and algorithms (Chapters 3–6 for continuous random variables and Chapters 7–9 for discrete random variables) used in APPL. The book concludes with Chapters 10–15 introducing a sampling of various applications in the mathematical sciences. This book should appeal to researchers in the mathematical sciences with an interest in applied probability and instructors using the book for a special topics course in computational probability taught in a mathematics, statistics, operations research, management science, or industrial engineering department.

Inhaltsverzeichnis

Frontmatter

Introduction

Frontmatter

1. Computational Probability

Abstract
The purpose of this chapter is to lure you into reading the rest of the monograph. We present four examples of probability questions that would be unpleasant to solve by hand, but are solvable with computational probability using APPL (A Probability Programming Language). We define the field of computational probability as the development of data structures and algorithms to automate the derivation of existing and new results in probability and statistics. Section 12.3, for example, contains the derivation of the distribution of a well-known test statistic that requires 99,500 carefully crafted integrations.
John H. Drew, Diane L. Evans, Andrew G. Glen, Lawrence M. Leemis

2. Maple for APPL

Abstract
Maple is a computer algebra system and programming language that can be used for numerical computations, solving equations, manipulating symbolic expressions, plotting, and programming, just to name a few of the basics. APPL is, simply, a set of supplementary Maple commands and procedures that augments the existing computer algebra system. In effect, APPL takes the capabilities of Maple and turns it into a computer algebra system for computational probability. This chapter contains guidelines for using Maple, and discusses the Maple commands that are used in APPL programming. After reading this chapter, an APPL user will have the knowledge necessary to modify the APPL code to meet his or her particular needs. We will start with a discussion of basic numeric computation, then advance to defining variables, symbolic computations, functions, data types, solving equations, calculus and graphing. Then we will discuss the programming features of Maple that facilitate building the APPL language: loops, conditions, and procedures.
John H. Drew, Diane L. Evans, Andrew G. Glen, Lawrence M. Leemis

Algorithms for Continuous Random Variables

Frontmatter

3. Data Structures and Simple Algorithms

Abstract
This chapter and the three that follow it concern continuous random variables. We have chosen to present continuous random variables first because they are defined with a somewhat simpler data structure than that for discrete random variables. The development described here gives a probabilist the ability to automate the instantiation and processing of continuous random variables—key elements of computational probability.
John H. Drew, Diane L. Evans, Andrew G. Glen, Lawrence M. Leemis

4. Transformations of Random Variables

Abstract
This chapter presents a generalized version of the univariate change-of-variable technique for transforming continuous random variables. Extending a theorem from Casella and Berger [16] for many–to–1 transformations, we consider more general univariate transformations. Specifically, the transformation can range from 1–to–1 to many–to–1 on various subsets of the support of the random variable of interest. We also present an implementation of the theorem in APPL and present four examples.
John H. Drew, Diane L. Evans, Andrew G. Glen, Lawrence M. Leemis

5. Bivariate Transformations of Random Variables

Abstract
This chapter extends the work in the previous chapter in order to automate the bivariate change-of-variables technique for bivariate continuous random variables with arbitrary distributions. The algorithm from the previous chapter for univariate change-of-variables was originally devised by Glen et al. [37]. The bivariate transformation procedure presented in this chapter handles 1-to-1, k-to-1, and piecewise k-to-1 transformations for both independent and dependent random variables. We also present other procedures that operate on bivariate random variables (e.g., calculating correlation and marginal distributions).
John H. Drew, Diane L. Evans, Andrew G. Glen, Lawrence M. Leemis

6. Products of Random Variables

Abstract
This chapter describes an algorithm for computing the PDF of the product of two independent continuous random variables. This algorithm has been implemented in the Product procedure in APPL. The algorithms behind the Transform and BiTransform procedures from the two previous chapters differ fundamentally from the algorithm behind the Product procedure in that the transformation algorithms are more general whereas determining the distribution of the product of two random variables is more specific. Some examples given in the chapter demonstrate the algorithm’s application.
John H. Drew, Diane L. Evans, Andrew G. Glen, Lawrence M. Leemis

Algorithms for Discrete Random Variables

Frontmatter

7. Data Structures and Simple Algorithms

Abstract
This chapter introduces the data structures necessary to define a discrete random variable in APPL and surveys some simple algorithms associated with discrete random variables. The first section will show that the nature of the support of discrete random variables makes the data structures required much more complicated than for continuous random variables.
John H. Drew, Diane L. Evans, Andrew G. Glen, Lawrence M. Leemis

8. Sums of Independent Discrete Random Variables

Abstract
This chapter presents an algorithm for computing the PDF of the sum of two independent discrete random variables, along with an implementation of the algorithm in APPL. Some examples illustrate the utility of this algorithm.
John H. Drew, Diane L. Evans, Andrew G. Glen, Lawrence M. Leemis

9. Order Statistics for Random Sampling from Discrete Populations

Abstract
This chapter presents an algorithm for computing the PDF of order statistics drawn from discrete parent populations, along with an implementation of the algorithm in APPL. Several examples illustrate the utility of this algorithm.
John H. Drew, Diane L. Evans, Andrew G. Glen, Lawrence M. Leemis

Applications

Frontmatter

10. Reliability and Survival Analysis

Abstract
The remaining chapters contain dozens of computational probability applications using APPL. The applications range in complexity from brief examples to results and algorithms requiring long derivations. This chapter surveys some applications in reliability and the closely-related field of survival analysis.
John H. Drew, Diane L. Evans, Andrew G. Glen, Lawrence M. Leemis

11. Symbolic ARMA Model Analysis

Abstract
This chapter extends the APPL language to include the analysis of ARMA (autoregressive moving average) time series models. ARMA models provide a parsimonious and flexible mechanism for modeling the evolution of a time series. Some useful measures of these models (e.g., the autocorrelation function or the spectral density function) are oftentimes tedious to compute by hand, and APPL can help ease the computational burden.
John H. Drew, Diane L. Evans, Andrew G. Glen, Lawrence M. Leemis

12. Stochastic Simulation

Abstract
This chapter considers applications from stochastic simulation. Section 12.1 considers tests of randomness. Section 12.2 investigates the use of computational probability in input modeling. Section 12.3 contains a development of an algorithm to find the distribution of the Kolmogorov–Smirnov goodness-of-fit test statistic in the all-parameters-known case.
John H. Drew, Diane L. Evans, Andrew G. Glen, Lawrence M. Leemis

13. Transient Queueing Analysis

Abstract
An APPL extension that computes the exact distribution of the nth customer’s sojourn time in an MMs queue with k customers initially present is derived in this chapter. Algorithms for computing the covariance between sojourn times for an MM∕1 queue with k customers present at time zero are also developed. Maple computer code is developed to implement the transient queue analysis for many system measures of performance without regard to traffic intensity (i.e., the system may be unstable with traffic intensity greater than one).
John H. Drew, Diane L. Evans, Andrew G. Glen, Lawrence M. Leemis

14. Bayesian Applications

Abstract
This chapter considers Bayesian applications of APPL. Section 14.1 introduces Bayesian statistics and motivates the use of a computer algebra system to derive posterior distributions. Section 14.2 develops algorithms in the case of a single unknown parameter. Section 14.3 develops algorithms in the case of multiple unknown parameters.
John H. Drew, Diane L. Evans, Andrew G. Glen, Lawrence M. Leemis

15. Other Applications

Abstract
This chapter contains miscellaneous computational probability applications. Section 15.1 concerns algorithms for calculating the probability distribution of the longest path of a series-parallel stochastic activity network with continuous activity durations.
John H. Drew, Diane L. Evans, Andrew G. Glen, Lawrence M. Leemis

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise