Exercise 1 (Warm-up):
Write a probabilistic program representing the probability
distribution given by the following generalized density:
Λr. ∫dx(1/2·[0≤x]·[x≤1]+1/2·1/(√(2π)·e^(x^2)))·(1/2·δ(x)[r]+1/2·δ(x²)[r])
Exercise 2 (Properties):
In the lecture, you have seen the following definitions:
return : T → D[T]
return(x) = Λt. δ(x)[t]
map : (A → B) → (D[A] → D[B])
map(f)(d) = Λb. ∫da d[a]·δ(f(a))[b]
(;) : (A → D[B]) → (B → D[C]) → (A → D[C])
(f;g) = λa.Λc. ∫db f(a)[b]·g(b)[c]
Show the following identities (we quantify universally over free variables):
- map(λx. f(g(x)))(d) = map(f)(map(g)(d)).
- return(f(x)) = map(f)(return(x)).
- f;return = f
- return;f = f
- (f;g);h = f;(g;h).
Hint: The following identities may be useful:
- (λx. f(x))(v) = f(v)
- (Λx. f[x])[y] = f[y]
- ∫dx δ(v)[x]·f(x) = f(v). (Basic Dirac delta elimination).
- ∫dx f[x]·δ(x)[y] = f[y]. (Reverse Dirac delta elimination).
- ∫dx∫dy f[x,y] = ∫dy∫dx f[x,y]. (Fubini's theorem).
- λt.Λr. f(t)[r] = f
Exercise 3 (Dirac delta inversion):
Manually compute the distribution of the result of the following PSI
programs as a simplified symbolic expression representing a generalized
probability density (there should be no integral signs left in your solution):
def main(){
x := uniform(0,1);
y := uniform(0,1);
return x+y;
}
def main(){
x := uniform(0,1);
y := uniform(0,1);
return x*y;
}
def main(){
x := if flip(1/2)
then uniform(0,1)
else 1/2;
return x*(1-x);
}
def main(){
x := uniform(0,1);
y := (2+x)/(3+x);
return y;
}
Exercise 4 (Conditioning):
Manually compute the distribution of the result of the following PSI
program as a symbolic expression representing a generalized
probability density (there should be no integral signs left in your solution):
def main(){
p := uniform(0,1);
x₁ := flip(p);
x₂ := flip(p);
observe(x₁ && !x₂);
return p
}
Hints:
- ⟦observe(x)⟧ = λσ.Λσ'.[⟦x⟧(σ)≠0]·δ(σ)[σ']
- Remember to renormalize the final result.
Exercise 5 (Continuous conditioning):
Manually compute the expected result of the following PSI programs:
def main(){
x := uniform(0,1);
y := uniform(0,1);
cobserve(x-y,0);
assert(x == y);
return x;
}
def main(){
x := uniform(0,1);
y := uniform(0,1);
cobserve(x/y,1);
assert(x == y);
return x;
}
Intuitively, why is the result not the same for both programs? Add a
parameter ε>0 and rewrite the programs using a standard "observe"
statement (but without the assertions), such that you recover the
above programs in the limit ε→0.