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.