Mathematical Preliminaries - Semantics of Probabilistic Processes: An Operational Approach - page 18

The triple ( X , , μ ) is called a measure space .A Borel measure is a measure on a

Borel ˃ -algebra. If μ ( X )

X

, μ ) is called a prob-
ability space , μ a probability measure , also called probability distribution , the set
X a sample space , and the elements of

= 1, then the measure space ( X , X

1, then we obtain a
subprobability measure , also called subprobability distribution or simply subdistri-
bution . A measure over a discrete measurable space ( X ,

X events .If μ ( X ) ≤

P ( X )) is called a discrete

measure over X .
A (discrete) probability subdistribution over a set S can also be considered as a
function ʔ : S [0, 1] with s ∈ S ʔ ( s )

ₒ ≤ 1; the support of such a ʔ is the set

is s ∈ ʔ

ʔ : ={ s ∈ S | ʔ ( s ) > 0 } , and its mass | ʔ | ʔ ( s ). A subdistribution is

a (total, or full) distribution if 1. The poin t distribution s assigns probability

1to s and 0 to all other elements of S , so that

| ʔ |=

s ={ s } . With D sub ( s ) we denote

the set of subdistributions over S , and with D ( S ) its subset of full distributions. For

ʔ , ʘ ∈ D sub ( S ) we write ʔ ≤ ʘ iff ʔ ( s ) ≤ ʘ ( s ) for all s ∈ S .

be a set of subdistributions, possibly infinite. Then k ∈ K ʔ k is
the real-valued function in S

Let { ʔ k | k ∈ K }

= k ∈ K ʔ k ( s ). This
is a partial operation on subdistributions because for some state s the sum of ʔ k ( s )
might exceed 1. If the index set is finite, say

defined by ( k ∈ K ʔ k )( s ):

ₒ R

{ 1, ... , n } , we often write ʔ 1 +···+ ʔ n .

·

For a real number p from [0, 1] we use p ʔ to denote the subdistribution given by

· = ·

( p ʔ ( s ). Finally, we use ʵ to denote the everywhere-zero subdistribution

that thus has empty support. These operations on subdistributions do not readily adapt
themselves to distributions; yet if k ∈ K p k =

ʔ )( s ): p

1 for some collection of probabilities
p k , and the ʔ k are distributions, then so is k ∈ K p k · ʔ k . In general when 0 ≤ p ≤ 1,

we write x p ↕ y for p · x + · y where that makes sense, so that for example

ʔ 1 p ↕ ʔ 2 is always defined, and is full if ʔ 1 and ʔ 2 are. Finally, the product of two
probability distributions ʔ , ʘ over S , T is the distribution ʔ

(1 − p )

× ʘ over S × T defined

by ( ʔ × ʘ )( s , t ): = ʔ ( s ) · ʘ ( t ).

2.6 Linear Programming

A linear programming problem is the problem of maximising or minimising a
linear function subject to linear constraints. The constraints may be equalities or
inequalities.

Example 2.16 (The Transportation Problem) There are m factories that supply n
customers with a particular product. Maximum production at factory i is s i . The
demand for the product from customer j is r j . Let c ij be the cost of transporting
one unit of the product from factory i to customer j . The problem is to determine
the quantity of product to be supplied from each factory to each customer so as to
minimise total costs.