108 apply (simp add: algebra_simps power2_eq_square) |
108 apply (simp add: algebra_simps power2_eq_square) |
109 done |
109 done |
110 then have "(\<Sum>k\<le>n. (k - n * x)\<^sup>2 * Bernstein n k x)/n^2 = x * (1 - x) / n" |
110 then have "(\<Sum>k\<le>n. (k - n * x)\<^sup>2 * Bernstein n k x)/n^2 = x * (1 - x) / n" |
111 by (simp add: power2_eq_square) |
111 by (simp add: power2_eq_square) |
112 then show ?thesis |
112 then show ?thesis |
113 using n by (simp add: sum_divide_distrib divide_simps mult.commute power2_commute) |
113 using n by (simp add: sum_divide_distrib field_split_simps mult.commute power2_commute) |
114 qed |
114 qed |
115 { fix k |
115 { fix k |
116 assume k: "k \<le> n" |
116 assume k: "k \<le> n" |
117 then have kn: "0 \<le> k / n" "k / n \<le> 1" |
117 then have kn: "0 \<le> k / n" "k / n \<le> 1" |
118 by (auto simp: divide_simps) |
118 by (auto simp: field_split_simps) |
119 consider (lessd) "\<bar>x - k / n\<bar> < d" | (ged) "d \<le> \<bar>x - k / n\<bar>" |
119 consider (lessd) "\<bar>x - k / n\<bar> < d" | (ged) "d \<le> \<bar>x - k / n\<bar>" |
120 by linarith |
120 by linarith |
121 then have "\<bar>(f x - f (k/n))\<bar> \<le> e/2 + 2 * M / d\<^sup>2 * (x - k/n)\<^sup>2" |
121 then have "\<bar>(f x - f (k/n))\<bar> \<le> e/2 + 2 * M / d\<^sup>2 * (x - k/n)\<^sup>2" |
122 proof cases |
122 proof cases |
123 case lessd |
123 case lessd |
156 apply (simp add: divide_simps Mge0 mult_le_one mult_left_le) |
156 apply (simp add: divide_simps Mge0 mult_le_one mult_left_le) |
157 done |
157 done |
158 also have "... < e" |
158 also have "... < e" |
159 apply (simp add: field_simps) |
159 apply (simp add: field_simps) |
160 using \<open>d>0\<close> nbig e \<open>n>0\<close> |
160 using \<open>d>0\<close> nbig e \<open>n>0\<close> |
161 apply (simp add: divide_simps algebra_simps) |
161 apply (simp add: field_split_simps algebra_simps) |
162 using ed0 by linarith |
162 using ed0 by linarith |
163 finally have "\<bar>f x - (\<Sum>k\<le>n. f (real k / real n) * Bernstein n k x)\<bar> < e" . |
163 finally have "\<bar>f x - (\<Sum>k\<le>n. f (real k / real n) * Bernstein n k x)\<bar> < e" . |
164 } |
164 } |
165 then show ?thesis |
165 then show ?thesis |
166 by auto |
166 by auto |
280 have pt_pos: "p t > 0" if t: "t \<in> S-U" for t |
280 have pt_pos: "p t > 0" if t: "t \<in> S-U" for t |
281 proof - |
281 proof - |
282 obtain i where i: "i \<in> subU" "t \<in> Uf i" using subU t by blast |
282 obtain i where i: "i \<in> subU" "t \<in> Uf i" using subU t by blast |
283 show ?thesis |
283 show ?thesis |
284 using subU i t |
284 using subU i t |
285 apply (clarsimp simp: p_def divide_simps) |
285 apply (clarsimp simp: p_def field_split_simps) |
286 apply (rule sum_pos2 [OF \<open>finite subU\<close>]) |
286 apply (rule sum_pos2 [OF \<open>finite subU\<close>]) |
287 using Uf t pf01 apply auto |
287 using Uf t pf01 apply auto |
288 apply (force elim!: subsetCE) |
288 apply (force elim!: subsetCE) |
289 done |
289 done |
290 qed |
290 qed |
291 have p01: "p x \<in> {0..1}" if t: "x \<in> S" for x |
291 have p01: "p x \<in> {0..1}" if t: "x \<in> S" for x |
292 proof - |
292 proof - |
293 have "0 \<le> p x" |
293 have "0 \<le> p x" |
294 using subU cardp t |
294 using subU cardp t |
295 apply (simp add: p_def divide_simps sum_nonneg) |
295 apply (simp add: p_def field_split_simps sum_nonneg) |
296 apply (rule sum_nonneg) |
296 apply (rule sum_nonneg) |
297 using pf01 by force |
297 using pf01 by force |
298 moreover have "p x \<le> 1" |
298 moreover have "p x \<le> 1" |
299 using subU cardp t |
299 using subU cardp t |
300 apply (simp add: p_def divide_simps sum_nonneg) |
300 apply (simp add: p_def field_split_simps sum_nonneg) |
301 apply (rule sum_bounded_above [where 'a=real and K=1, simplified]) |
301 apply (rule sum_bounded_above [where 'a=real and K=1, simplified]) |
302 using pf01 by force |
302 using pf01 by force |
303 ultimately show ?thesis |
303 ultimately show ?thesis |
304 by auto |
304 by auto |
305 qed |
305 qed |
329 have "k-1 \<le> 1/\<delta>" |
329 have "k-1 \<le> 1/\<delta>" |
330 using \<delta>01 by (simp add: k_def) |
330 using \<delta>01 by (simp add: k_def) |
331 with \<delta>01 have "k \<le> (1+\<delta>)/\<delta>" |
331 with \<delta>01 have "k \<le> (1+\<delta>)/\<delta>" |
332 by (auto simp: algebra_simps add_divide_distrib) |
332 by (auto simp: algebra_simps add_divide_distrib) |
333 also have "... < 2/\<delta>" |
333 also have "... < 2/\<delta>" |
334 using \<delta>01 by (auto simp: divide_simps) |
334 using \<delta>01 by (auto simp: field_split_simps) |
335 finally have k2\<delta>: "k < 2/\<delta>" . |
335 finally have k2\<delta>: "k < 2/\<delta>" . |
336 have "1/\<delta> < k" |
336 have "1/\<delta> < k" |
337 using \<delta>01 unfolding k_def by linarith |
337 using \<delta>01 unfolding k_def by linarith |
338 with \<delta>01 k2\<delta> have k\<delta>: "1 < k*\<delta>" "k*\<delta> < 2" |
338 with \<delta>01 k2\<delta> have k\<delta>: "1 < k*\<delta>" "k*\<delta> < 2" |
339 by (auto simp: divide_simps) |
339 by (auto simp: field_split_simps) |
340 define q where [abs_def]: "q n t = (1 - p t ^ n) ^ (k^n)" for n t |
340 define q where [abs_def]: "q n t = (1 - p t ^ n) ^ (k^n)" for n t |
341 have qR: "q n \<in> R" for n |
341 have qR: "q n \<in> R" for n |
342 by (simp add: q_def const diff power pR) |
342 by (simp add: q_def const diff power pR) |
343 have q01: "\<And>n t. t \<in> S \<Longrightarrow> q n t \<in> {0..1}" |
343 have q01: "\<And>n t. t \<in> S \<Longrightarrow> q n t \<in> {0..1}" |
344 using p01 by (simp add: q_def power_le_one algebra_simps) |
344 using p01 by (simp add: q_def power_le_one algebra_simps) |
482 moreover |
482 moreover |
483 have pff01: "pff x \<in> {0..1}" if t: "x \<in> S" for x |
483 have pff01: "pff x \<in> {0..1}" if t: "x \<in> S" for x |
484 proof - |
484 proof - |
485 have "0 \<le> pff x" |
485 have "0 \<le> pff x" |
486 using subA cardp t |
486 using subA cardp t |
487 apply (simp add: pff_def divide_simps sum_nonneg) |
487 apply (simp add: pff_def field_split_simps sum_nonneg) |
488 apply (rule Groups_Big.linordered_semidom_class.prod_nonneg) |
488 apply (rule Groups_Big.linordered_semidom_class.prod_nonneg) |
489 using ff by fastforce |
489 using ff by fastforce |
490 moreover have "pff x \<le> 1" |
490 moreover have "pff x \<le> 1" |
491 using subA cardp t |
491 using subA cardp t |
492 apply (simp add: pff_def divide_simps sum_nonneg) |
492 apply (simp add: pff_def field_split_simps sum_nonneg) |
493 apply (rule prod_mono [where g = "\<lambda>x. 1", simplified]) |
493 apply (rule prod_mono [where g = "\<lambda>x. 1", simplified]) |
494 using ff by fastforce |
494 using ff by fastforce |
495 ultimately show ?thesis |
495 ultimately show ?thesis |
496 by auto |
496 by auto |
497 qed |
497 qed |
510 using atLeastAtMost_iff by blast |
510 using atLeastAtMost_iff by blast |
511 also have "... < e / card subA" |
511 also have "... < e / card subA" |
512 using ff [THEN conjunct2, THEN conjunct2, THEN conjunct1] v subA x |
512 using ff [THEN conjunct2, THEN conjunct2, THEN conjunct1] v subA x |
513 by auto |
513 by auto |
514 also have "... \<le> e" |
514 also have "... \<le> e" |
515 using cardp e by (simp add: divide_simps) |
515 using cardp e by (simp add: field_split_simps) |
516 finally have "pff x < e" . |
516 finally have "pff x < e" . |
517 } |
517 } |
518 then have "\<And>x. x \<in> A \<Longrightarrow> pff x < e" |
518 then have "\<And>x. x \<in> A \<Longrightarrow> pff x < e" |
519 using A Vf subA by (metis UN_E contra_subsetD) |
519 using A Vf subA by (metis UN_E contra_subsetD) |
520 moreover |
520 moreover |
530 also have "... < pff x" |
530 also have "... < pff x" |
531 apply (simp add: pff_def) |
531 apply (simp add: pff_def) |
532 apply (rule prod_mono_strict [where f = "\<lambda>x. 1 - e / card subA", simplified]) |
532 apply (rule prod_mono_strict [where f = "\<lambda>x. 1 - e / card subA", simplified]) |
533 apply (simp_all add: subA(2)) |
533 apply (simp_all add: subA(2)) |
534 apply (intro ballI conjI) |
534 apply (intro ballI conjI) |
535 using e apply (force simp: divide_simps) |
535 using e apply (force simp: field_split_simps) |
536 using ff [THEN conjunct2, THEN conjunct2, THEN conjunct2] subA B x |
536 using ff [THEN conjunct2, THEN conjunct2, THEN conjunct2] subA B x |
537 apply blast |
537 apply blast |
538 done |
538 done |
539 finally have "1 - e < pff x" . |
539 finally have "1 - e < pff x" . |
540 } |
540 } |