Probabilistic Bisimulation - Semantics of Probabilistic Processes: An Operational Approach - page 31

Fig. 3.2 The transportation problem

and note that

ʔ 2 ( s i ) ʔ 2 ( t j ) = q j and = p i . (3.5)

j ∈ J i i ∈ I j

Because of ( 3.5 )wehave
ʔ 1 = i ∈ I p i · = i ∈ I p i · j ∈ J i

q j
ʔ 2 ( s i ) ·

s i s i

= i ∈ I j ∈ J i

q j
ʔ 2 ( s i ) ·

p i ·

s i .

Similarly
ʔ 3 = j ∈ J q j · = j ∈ J q j · i ∈ I j

p i

t j

ʔ 2 ( t j ) ·

t j

= j ∈ J i ∈ I j

p i · q j
ʔ 2 ( t j ) ·

t j

= i ∈ I j ∈ J i

q j
ʔ 2 ( t j ) ·

p i ·

t j by ( 3.4 ).

Now for each j in J i we know that in fact t j = s i , and so from the middle parts
of ( 3.2 ) and ( 3.3 ), we obtain ʔ 1 (

R 1 · R 2 ) † ʔ 3 .

† †

) † 3. By Clause 2 above we have R · R = ( R · R for any relation R .If R is

) †

† .It

transitive, then R · R ↆ R . By Clause 1 above, we obtain ( R · R ↆ R

† † † , thus †

follows that R · R ↆ R R is transitive.

3.4 Justifying the Lifting Operation

The lifting operation given in Definition 3.2 is not only concise but also intrinsi-
cally related to some fundamental concepts in mathematics, notably the Kantorovich
metric.

3.4.1 Justification by the Kantorovich Metric

We begin with some historical notes. The transportation problem plays an important
role in linear programming due to its general formulation and methods of solution.