src/HOL/Probability/Probability_Mass_Function.thy
changeset 61808 fc1556774cfe
parent 61634 48e2de1b1df5
child 62026 ea3b1b0413b4
equal deleted inserted replaced
61807:965769fe2b63 61808:fc1556774cfe
    52     then obtain X where "finite X" "card X = Suc (Suc n)" "X \<subseteq> ?X"
    52     then obtain X where "finite X" "card X = Suc (Suc n)" "X \<subseteq> ?X"
    53       by (metis infinite_arbitrarily_large)
    53       by (metis infinite_arbitrarily_large)
    54     from this(3) have *: "\<And>x. x \<in> X \<Longrightarrow> ?M / Suc n \<le> ?m x"
    54     from this(3) have *: "\<And>x. x \<in> X \<Longrightarrow> ?M / Suc n \<le> ?m x"
    55       by auto
    55       by auto
    56     { fix x assume "x \<in> X"
    56     { fix x assume "x \<in> X"
    57       from `?M \<noteq> 0` *[OF this] have "?m x \<noteq> 0" by (auto simp: field_simps measure_le_0_iff)
    57       from \<open>?M \<noteq> 0\<close> *[OF this] have "?m x \<noteq> 0" by (auto simp: field_simps measure_le_0_iff)
    58       then have "{x} \<in> sets M" by (auto dest: measure_notin_sets) }
    58       then have "{x} \<in> sets M" by (auto dest: measure_notin_sets) }
    59     note singleton_sets = this
    59     note singleton_sets = this
    60     have "?M < (\<Sum>x\<in>X. ?M / Suc n)"
    60     have "?M < (\<Sum>x\<in>X. ?M / Suc n)"
    61       using `?M \<noteq> 0`
    61       using \<open>?M \<noteq> 0\<close>
    62       by (simp add: `card X = Suc (Suc n)` of_nat_Suc field_simps less_le measure_nonneg)
    62       by (simp add: \<open>card X = Suc (Suc n)\<close> of_nat_Suc field_simps less_le measure_nonneg)
    63     also have "\<dots> \<le> (\<Sum>x\<in>X. ?m x)"
    63     also have "\<dots> \<le> (\<Sum>x\<in>X. ?m x)"
    64       by (rule setsum_mono) fact
    64       by (rule setsum_mono) fact
    65     also have "\<dots> = measure M (\<Union>x\<in>X. {x})"
    65     also have "\<dots> = measure M (\<Union>x\<in>X. {x})"
    66       using singleton_sets `finite X`
    66       using singleton_sets \<open>finite X\<close>
    67       by (intro finite_measure_finite_Union[symmetric]) (auto simp: disjoint_family_on_def)
    67       by (intro finite_measure_finite_Union[symmetric]) (auto simp: disjoint_family_on_def)
    68     finally have "?M < measure M (\<Union>x\<in>X. {x})" .
    68     finally have "?M < measure M (\<Union>x\<in>X. {x})" .
    69     moreover have "measure M (\<Union>x\<in>X. {x}) \<le> ?M"
    69     moreover have "measure M (\<Union>x\<in>X. {x}) \<le> ?M"
    70       using singleton_sets[THEN sets.sets_into_space] by (intro finite_measure_mono) auto
    70       using singleton_sets[THEN sets.sets_into_space] by (intro finite_measure_mono) auto
    71     ultimately show False by simp
    71     ultimately show False by simp
   397   by (auto simp add: nn_integral_0_iff_AE AE_measure_pmf_iff set_pmf_eq not_le less_le pmf_nonneg)
   397   by (auto simp add: nn_integral_0_iff_AE AE_measure_pmf_iff set_pmf_eq not_le less_le pmf_nonneg)
   398 
   398 
   399 lemma bind_pmf_cong:
   399 lemma bind_pmf_cong:
   400   assumes "p = q"
   400   assumes "p = q"
   401   shows "(\<And>x. x \<in> set_pmf q \<Longrightarrow> f x = g x) \<Longrightarrow> bind_pmf p f = bind_pmf q g"
   401   shows "(\<And>x. x \<in> set_pmf q \<Longrightarrow> f x = g x) \<Longrightarrow> bind_pmf p f = bind_pmf q g"
   402   unfolding `p = q`[symmetric] measure_pmf_inject[symmetric] bind_pmf.rep_eq
   402   unfolding \<open>p = q\<close>[symmetric] measure_pmf_inject[symmetric] bind_pmf.rep_eq
   403   by (auto simp: AE_measure_pmf_iff Pi_iff space_subprob_algebra subprob_space_measure_pmf
   403   by (auto simp: AE_measure_pmf_iff Pi_iff space_subprob_algebra subprob_space_measure_pmf
   404                  sets_bind[where N="count_space UNIV"] emeasure_bind[where N="count_space UNIV"]
   404                  sets_bind[where N="count_space UNIV"] emeasure_bind[where N="count_space UNIV"]
   405            intro!: nn_integral_cong_AE measure_eqI)
   405            intro!: nn_integral_cong_AE measure_eqI)
   406 
   406 
   407 lemma bind_pmf_cong_simp:
   407 lemma bind_pmf_cong_simp:
   734 setup_lifting td_pmf_embed_pmf
   734 setup_lifting td_pmf_embed_pmf
   735 
   735 
   736 lemma set_pmf_transfer[transfer_rule]:
   736 lemma set_pmf_transfer[transfer_rule]:
   737   assumes "bi_total A"
   737   assumes "bi_total A"
   738   shows "rel_fun (pcr_pmf A) (rel_set A) (\<lambda>f. {x. f x \<noteq> 0}) set_pmf"
   738   shows "rel_fun (pcr_pmf A) (rel_set A) (\<lambda>f. {x. f x \<noteq> 0}) set_pmf"
   739   using `bi_total A`
   739   using \<open>bi_total A\<close>
   740   by (auto simp: pcr_pmf_def cr_pmf_def rel_fun_def rel_set_def bi_total_def Bex_def set_pmf_iff)
   740   by (auto simp: pcr_pmf_def cr_pmf_def rel_fun_def rel_set_def bi_total_def Bex_def set_pmf_iff)
   741      metis+
   741      metis+
   742 
   742 
   743 end
   743 end
   744 
   744 
  1077       using in_quotient_imp_in_rel[of UNIV ?R C x y] C assms
  1077       using in_quotient_imp_in_rel[of UNIV ?R C x y] C assms
  1078       by (simp add: equivp_equiv)
  1078       by (simp add: equivp_equiv)
  1079     with in_set eq have "measure p {x. R x y} = measure q {y. R x y}"
  1079     with in_set eq have "measure p {x. R x y} = measure q {y. R x y}"
  1080       by auto
  1080       by auto
  1081     moreover have "{y. R x y} = C"
  1081     moreover have "{y. R x y} = C"
  1082       using assms `x \<in> C` C quotientD[of UNIV ?R C x] by (simp add: equivp_equiv)
  1082       using assms \<open>x \<in> C\<close> C quotientD[of UNIV ?R C x] by (simp add: equivp_equiv)
  1083     moreover have "{x. R x y} = C"
  1083     moreover have "{x. R x y} = C"
  1084       using assms `y \<in> C` C quotientD[of UNIV "?R" C y] sympD[of R]
  1084       using assms \<open>y \<in> C\<close> C quotientD[of UNIV "?R" C y] sympD[of R]
  1085       by (auto simp add: equivp_equiv elim: equivpE)
  1085       by (auto simp add: equivp_equiv elim: equivpE)
  1086     ultimately show ?thesis
  1086     ultimately show ?thesis
  1087       by auto
  1087       by auto
  1088   qed
  1088   qed
  1089 next
  1089 next
  1112       unfolding measure_pmf_zero_iff by auto
  1112       unfolding measure_pmf_zero_iff by auto
  1113   qed
  1113   qed
  1114 
  1114 
  1115   fix x y assume "x \<in> set_pmf p" "y \<in> set_pmf q" "R x y"
  1115   fix x y assume "x \<in> set_pmf p" "y \<in> set_pmf q" "R x y"
  1116   have "{y. R x y} \<in> UNIV // ?R" "{x. R x y} = {y. R x y}"
  1116   have "{y. R x y} \<in> UNIV // ?R" "{x. R x y} = {y. R x y}"
  1117     using assms `R x y` by (auto simp: quotient_def dest: equivp_symp equivp_transp)
  1117     using assms \<open>R x y\<close> by (auto simp: quotient_def dest: equivp_symp equivp_transp)
  1118   with eq show "measure p {x. R x y} = measure q {y. R x y}"
  1118   with eq show "measure p {x. R x y} = measure q {y. R x y}"
  1119     by auto
  1119     by auto
  1120 qed
  1120 qed
  1121 
  1121 
  1122 bnf pmf: "'a pmf" map: map_pmf sets: set_pmf bd : "natLeq" rel: rel_pmf
  1122 bnf pmf: "'a pmf" map: map_pmf sets: set_pmf bd : "natLeq" rel: rel_pmf
  1196   then obtain pq where *: "\<And>a b. (a, b) \<in> set_pmf pq \<Longrightarrow> R a b"
  1196   then obtain pq where *: "\<And>a b. (a, b) \<in> set_pmf pq \<Longrightarrow> R a b"
  1197     and eq: "return_pmf x = map_pmf fst pq" "M = map_pmf snd pq"
  1197     and eq: "return_pmf x = map_pmf fst pq" "M = map_pmf snd pq"
  1198     by (force elim: rel_pmf.cases)
  1198     by (force elim: rel_pmf.cases)
  1199   moreover have "set_pmf (return_pmf x) = {x}"
  1199   moreover have "set_pmf (return_pmf x) = {x}"
  1200     by simp
  1200     by simp
  1201   with `a \<in> M` have "(x, a) \<in> pq"
  1201   with \<open>a \<in> M\<close> have "(x, a) \<in> pq"
  1202     by (force simp: eq)
  1202     by (force simp: eq)
  1203   with * show "R x a"
  1203   with * show "R x a"
  1204     by auto
  1204     by auto
  1205 qed (auto intro!: rel_pmf.intros[where pq="pair_pmf (return_pmf x) M"]
  1205 qed (auto intro!: rel_pmf.intros[where pq="pair_pmf (return_pmf x) M"]
  1206           simp: map_fst_pair_pmf map_snd_pair_pmf)
  1206           simp: map_fst_pair_pmf map_snd_pair_pmf)
  1364   shows "rel_pmf P (bind_pmf p f) (bind_pmf q g)"
  1364   shows "rel_pmf P (bind_pmf p f) (bind_pmf q g)"
  1365   unfolding bind_eq_join_pmf
  1365   unfolding bind_eq_join_pmf
  1366   by (rule rel_pmf_joinI)
  1366   by (rule rel_pmf_joinI)
  1367      (auto simp add: pmf.rel_map intro: pmf.rel_mono[THEN le_funD, THEN le_funD, THEN le_boolD, THEN mp, OF _ pq] fg)
  1367      (auto simp add: pmf.rel_map intro: pmf.rel_mono[THEN le_funD, THEN le_funD, THEN le_boolD, THEN mp, OF _ pq] fg)
  1368 
  1368 
  1369 text {*
  1369 text \<open>
  1370   Proof that @{const rel_pmf} preserves orders.
  1370   Proof that @{const rel_pmf} preserves orders.
  1371   Antisymmetry proof follows Thm. 1 in N. Saheb-Djahromi, Cpo's of measures for nondeterminism,
  1371   Antisymmetry proof follows Thm. 1 in N. Saheb-Djahromi, Cpo's of measures for nondeterminism,
  1372   Theoretical Computer Science 12(1):19--37, 1980,
  1372   Theoretical Computer Science 12(1):19--37, 1980,
  1373   @{url "http://dx.doi.org/10.1016/0304-3975(80)90003-1"}
  1373   @{url "http://dx.doi.org/10.1016/0304-3975(80)90003-1"}
  1374 *}
  1374 \<close>
  1375 
  1375 
  1376 lemma
  1376 lemma
  1377   assumes *: "rel_pmf R p q"
  1377   assumes *: "rel_pmf R p q"
  1378   and refl: "reflp R" and trans: "transp R"
  1378   and refl: "reflp R" and trans: "transp R"
  1379   shows measure_Ici: "measure p {y. R x y} \<le> measure q {y. R x y}" (is ?thesis1)
  1379   shows measure_Ici: "measure p {y. R x y} \<le> measure q {y. R x y}" (is ?thesis1)