Eettuiamo ora il confronto tra i due sistemi di transizione appena de niti. Nel sistema di tranzione per l'algoritmo DPDF la lista degli stati è inizializzata al valore ε: questo valore della lista iniziale è l'unico per cui sperimentalmente si è veri cata l'equivalenza. Nella proposizione 1 confrontiamo le probabilità di eettuare due
assegnamenti equivalenti. Nella proposizione 2 confrontiamo le probabilità di non eettuare nessun assegnamento. Nella proposizione 3 studiamo la probabilità asso- ciata alle transizioni che sono presenti nel PDAR ma non nel DPFD. Le proposizioni 4, 5 e 6 preparano la proposizione 7. Nella proposizione 7 dimostriamo che, dati i valori xi e ti, le probabilità di raggiungere lo stato x = xi al tempo t = ti sono
uguali nei due algoritmi a meno di una quantità trascurabile. Nelle espressioni che seguono utilizziamo il simbolo o(δt) per indicare gli in nitesimi di ordine superiore a δt. Nel caso speci co si tratta di termini in cui δt appare con un esponente intero maggiore o uguale a due. Nel caso in cui δt sia molto minore di uno questi termini si possono considerare trascurabili rispetto ai termini che dipendono linearmente da δt.
Il contenuto della proposizione 1 è: se i due algoritmi hanno attraversato la stessa sequenza di stati e il DPFD è stato inizializzato con la lista ε , allora le probabilità di eettuare due assegnamenti equivalenti (ad esempio x =apply(x, 1) nel DPFD e x =apply(x, {R1}) nel PDAR) sono uguali a meno di un termine o(δt).
Proposizione 1
Date le de nizioni precedenti consideriamo le due quantità: PDP F D = P (X(n + 1, j)|I(ε, x0)E(1, x1)....E(n, xn))
PP DAR= P (X0(n + 1, {Rj})|I0(x0)E0(1, x1)....E0(n, xn))
si ha che PP DAR− PDP F D = o(δt)
dimostrazione
segue direttamente dalle formule 1, 2 e 3:
o(δt)
Il contenuto della proposizione 2 è: se i due algoritmi hanno attraversato la stessa sequenza di stati e il DPFD è stato inizializzato con la lista ε, allora le probabilità di non eettuare nessun assegnamento sono uguali a meno di un termine o(δt).
Proposizione 2
Date le de nizioni precedenti consideriamo le due quantità: PDP F D = 1 −P
m
j=1P (X(n + 1, j)|I(ε, x0)E(1, x1)....E(n, xn)) j = 1, ...., m
PP DAR= 1−PLP (X
0(n+1, L)|I0(x
0)E0(1, x1)....E0(n, xn)) L ⊆ {R1, ...., Rm}L 6=
∅
si ha che PP DAR− PDP F D = o(δt)
dimostrazione
segue direttamente dalle formule1, 2 e 3: Se L ⊆ {R1, ...., Rm}e L 6= ∅
PP DAR = 1 −PLpL = (1 − p1)(1 − p2)....(1 − pm) = 1 −Pmj=1pj+ o(δt) =
PDP DF + o(δt)
Il contenuto della proposizione 3 è: se i due algoritmi hanno attraversato la stessa sequenza di stati e il DPFD è stato inizializzato con la lista ε, allora la probabilità di eettuare un assegnamento nel PDAR che non ha un equivalente nel DPFD (ad esempio x =apply(x, {R1, R2} )) è un o(δt).
Proposizione 3
Date le de nizione precedenti considerando la quantità:
PP DAR = P (X0(n + 1, L)|I0(x0)E0(1, x1)....E0(n, xn))con L ⊆ {R1, ...., Rm}ed
L 6= {Rj}∀j = 1, ..., m
si ha che: PP DAR= o(δt)
dimostrazione
segue direttamente dalla formula 3.
Se L = {Ri1, ...., Rik}con k ≥ 2 allora PP DAR = Qj∈Lpj ·Qj /∈L(1 − pj) =
o(δtk) = o(δt)
Iniziano adesso le proposizioni che utilizzano l'insieme degli stati raggiungibili e la lista di operazioni associata ad uno stato raggiungibile. Dato s0stato iniziale nel
sistema di transizioni etichettate associato al DPFD indichiamo con R(s0)l'insieme
degli stati raggiungibili in tale sistema. Dato sp
0 stato iniziale nel sistema di tran-
sizioni etichettate associato al PDAR indichiamo con R0(sp
0) l'insieme degli stati
raggiungibili in tale sistema.
Il contenuto della proposizione 4 è: se i due algoritmi sono stati inizializzati con gli stessi valori di x0 e t0 e e se il DPFD è stato inizializzato con la lista ε allora se
uno stato raggiungibile nel DPFD ha associata la stessa lista di operazioni di uno stato raggiungibile nel PDAR i valori di x e t nei due stati sono uguali.
Proposizione 4
Sia s =< i, x, t, j > in R(< ε, x0, t0>)e sia s0=< i, x0, t0, L >in R0(< x0, t0>)
se L(s)=L(s0) allora x = x0 e t = t0.
dimostrazione
Per induzione sulla lunghezza della lista. Lunghezza uguale ad 1:
Se L(s)=L(s0)=empty.add({R
i}) allora x = x0=apply(x0,{Ri}), t = t0= t0+ δt.
Se L(s)=L(s0)=empty.add(∅) allorax = x0= x
0, t = t0= t0+ δt.
Lunghezza uguale ad n implica lunghezza uguale ad n + 1: L(s)=L(s0)=Ln.add(I) siano s
n =< i, xn, tn, j > in R(< ε, x0, t0 >) tale che
(sn, l, s) è in → nel DPFD ed spn =< i, xpn, tpn, H > in R0(< x0, t0 >) tale che
(sp
n, l, s0)è in → nel PDAR allora:
L(sn)=L(spn)=Ln da cui, per ipotesi induttiva, xn = xnp tn = tpn. Se I = {Ri}
allora x =apply(xn, I)=apply(xpn, I)= x0 t = t0 = tn+ δt. Se I = ∅ allorax =
xn= xpn= x0 t = t0= tn+ dt.
Il contenuto della proposizione 5 è: se i due algoritmi sono stati inizializzati con gli stessi valori di x0 e t0 e e se il DPFD è stato inizializzato con la lista ε allora dati
sstato raggiungibile nel DPFD ed s0 stato raggiungibile nel PDAR se L(s)=L(s0) allora p(s0) = p(s) + o(δt).
Proposizione 5
Sia s =< i, x, t, j > in R(< ε, x0, t0>)e sia s0=< i, x0, t0, H >in R0(< x0, t0>)
se L(s)=L(s0) allora p(s0) = p(s) + o(δt).
dimostrazione
Per induzione sulla lunghezza della lista. Lunghezza uguale ad 1:
L(s)=L(s0)=empty.add({R
j}) allora p(s0) =PP DAR(X(1, {Rj})|I(x0))= PDP F D(X(1, j)|I(ε, x0))+
o(δt) = p(s) + o(δt)per la proposizione 1
L(s)=L(s0)=empty.add(∅) allora p(s0)=p(s)+o(δt) per la proposizione 2
Lunghezza uguale ad n implica lunghezza uguale ad n + 1: L(s)=L(s0)=Ln.add(I) siano s
n =< i, xn, tn, j > in R(< ε, x0, t0 >) tale che
(sn, l, s)è in → nel DPFD ed spn=< i, xpn, tpn, H >in R0(< x0, t0>)tale tale che
(sp
n, l, s0)è in → nel PDAR allora L(sn)=L(spn)=Ln da cui, per ipotesi induttiva,
p(sp
n) = p(sn).
Se I = {Ri}allora p(s0) = p(spn)·PP DAR(X(n+1, {Ri})|I(x0)E(1, x1), ...., E(n, xn)) =
(p(sn) + o(δt)) · (PDP F D(X(n + 1, i)|I(ε, x0)E(1, x1), ...., E(n, xn)) + o(δt))=
p(s) + o(δt). Nella seconda eguaglianza si è usata la proposizione 1. SeI = ∅ analogo al precedente ma va usata la proposizione 2.
Il contenuto della proposizione 6 è: se i due algoritmi sono stati inizializzati con gli stessi valori di x0e t0e e se il DPFD è stato inizializzato con la lista ε allora se s è
uno stato raggiungibile nel PDAR e non esiste s0 stato raggiungibile nel DPFD tale
Proposizione 6
Sia s0 =< i, x0, t0, L > in R0(< x
0, t0 >) se non esiste s =< i, x, t, j > in R(<
ε, x0, t0>)tale che L(s)=L(s0) allora p(s0) = o(δt).
dimostrazione
Non esiste s in R(< ε, x0, t0 >) tale che L(s)=L(s0) se solo se almeno uno degli
elementi L(s0) è un insieme che contiene più di una reazione. Dato che p(s0) è il
prodotto delle probabilità delle operazioni eettuate ad ogni iterazione e che, per la proposizione 3, la probabilità associata ad operazioni che applicano più di una reazione è un o(δt) segue la tesi.
Il contenuto della proposizione 7 è: se i due algoritmi sono stati inizializzati con gli stessi valori di x0 e t0 e se il DPFD è stato inizializzato con la lista ε allora, dati
i valori di xi e ti, la probabilità che x = xi e t = ti è uguale nei due algortimi a
meno di un o(δt).
Proposizione 7
Nel PDAR la probabilità di x = xi e t = ti è la somma di p(s0) dove s0 =<
i, x0, t0, L >è in R0(< x0, t0>), x0= xie t0= ti. Nel DPFD la probabilità di x =
xial tempo t = ti è la somma di p(s) dove s =< i, x, t, j > è in R(< ε, x0, t0>),
x = xi e t = ti. Dato il valore di xi e di ti la probabilità di x = xi e t = ti è
dimostrazione
Consideraimo il PDAR sia Mp l'insieme degli stati s0 =< i, x0, t0, L > in R0(<
x0, t0 >)tali che x0= xi e t0 = ti per ogni stato s0 in T0 vale una delle seguenti:
o non esiste s tale che L(s)=L(s0) e allora, per la proposizione 6, il contributo di
s0 a Ps0∈Mpp(s
0) è un o(δt) oppure esiste s tale che L(s)=L(s0) e allora, per la
proposizione 5, p(s0)=p(s)-o(δt). Sia M l'insieme degli stati s =< i, x, t, j > in
R(< ε, x0, t0>)tali che x = xi e t = ti. Per quanto detto si ha che Ps0∈Mpp(s
0)
= Ps∈Mp(s) − o(δt).
Abbiamo quindi trovato che la proprietà che supponiamo essere soddisfatta da DPF e PDAR è soddisfatta dalle due versioni nel discreto DPFD e PDAR a meno di una quantità o(δt).