import%20marimo%0A%0A__generated_with%20%3D%20%220.24.0%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20pandas%20as%20pd%0A%20%20%20%20import%20plotly.graph_objects%20as%20go%0A%20%20%20%20from%20plotly.subplots%20import%20make_subplots%0A%20%20%20%20import%20scipy.stats%20as%20stats%0A%0A%20%20%20%20return%20go%2C%20make_subplots%2C%20mo%2C%20np%2C%20pd%2C%20stats%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Note%2010%3A%20Chebyshev%20Inequality%2C%20Tail%20Bounds%2C%20and%20Concentration%20of%20Measure%0A%0A%20%20%20%20%26larr%3B%20Previous%20Note%3A%20%5B09%20Condition%20Number%5D(09_condition_number.py)%20%7C%20Next%20Note%3A%20%5B11%20Empirical%20CDF%5D(11_ecdf.py)%20%26rarr%3B%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%20%5Ba%5D%20Why%20do%20you%20need%20to%20know%20these%20concepts%3F%0A%0A%20%20%20%20Most%20statistical%20methods%20rely%20on%20distributional%20assumptions%2C%20such%20as%20Gaussianity.%20In%20real-world%20data%20science%2C%20machine%20learning%2C%20and%20streaming%20pipelines%2C%20however%2C%20true%20underlying%20probability%20distributions%20are%20frequently%20non-Gaussian%2C%20asymmetric%2C%20multi-modal%2C%20or%20heavy-tailed.%0A%0A%20%20%20%20**Chebyshev's%20Inequality**%20provides%20a%20universal%20mathematical%20guarantee%20that%20holds%20across%20every%20probability%20distribution%20with%20finite%20variance.%0A%0A%20%20%20%20Key%20applications%20across%20modern%20AI%20and%20statistics%3A%0A%20%20%20%201.%20**Distribution-Free%20Statistical%20Guarantees**%3A%20Chebyshev's%20inequality%20guarantees%20that%20no%20matter%20how%20strange%2C%20skewed%2C%20or%20uncharacterized%20a%20distribution%20is%2C%20the%20probability%20of%20falling%20beyond%20%24k%24%20standard%20deviations%20from%20the%20mean%20cannot%20exceed%20%241%2Fk%5E2%24.%0A%20%20%20%202.%20**Foundation%20of%20Learning%20Theory%20(PAC%20Learning)**%3A%20Generalization%20bounds%20in%20statistical%20learning%20theory%20bound%20the%20difference%20between%20empirical%20risk%20and%20expected%20risk%20using%20concentration%20inequalities.%20Chebyshev%20is%20the%20gateway%20inequality%20connecting%20first-moment%20bounds%20(Markov)%20to%20exponential%20concentration%20(Chernoff%2C%20Hoeffding%2C%20McDiarmid).%0A%20%20%20%203.%20**The%20Weak%20Law%20of%20Large%20Numbers%20(WLLN)**%3A%20Chebyshev's%20inequality%20provides%20the%20most%20direct%20proof%20that%20sample%20averages%20converge%20in%20probability%20to%20population%20means%20(%24%5Cbar%7BX%7D_n%20%5Cxrightarrow%7BP%7D%20%5Cmu%24)%2C%20establishing%20that%20empirical%20estimations%20stabilize%20as%20sample%20sizes%20grow.%0A%20%20%20%204.%20**Robust%20Outlier%20Detection%20and%20Quality%20Control**%3A%20Unlike%20Gaussian%20rules%20(e.g.%20the%203-sigma%20rule%20asserting%20%2499.7%5C%25%24%20coverage)%2C%20which%20fail%20under%20heavy%20tails%2C%20Chebyshev%20gives%20an%20unconditional%20upper%20bound%20on%20outlier%20probabilities%20(%24P(%7CX%20-%20%5Cmu%7C%20%5Cgeq%203%5Csigma)%20%5Cleq%2011.1%5C%25%24)%20valid%20for%20any%20production%20metric.%0A%20%20%20%205.%20**Randomized%20and%20Streaming%20Algorithms**%3A%20In%20big-data%20sketching%20algorithms%20(such%20as%20the%20Count-Min%20Sketch%20or%20the%20Median-of-Means%20estimator)%2C%20Chebyshev%20bounds%20the%20failure%20probability%20of%20sub-linear%20memory%20approximations.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%20%5Bb%5D%20Concept%20explanation%20with%20their%20role%20in%20ML%2FAI%2FStats%3F%0A%0A%20%20%20%20%23%23%23%20Markov's%20Inequality%3A%20The%20First-Moment%20Foundation%0A%0A%20%20%20%20Markov's%20inequality%20applies%20to%20any%20non-negative%20random%20variable%20%24Y%20%5Cgeq%200%24%20with%20finite%20expectation%20%24%5Cmathbb%7BE%7D%5BY%5D%20%3C%20%5Cinfty%24.%20For%20any%20constant%20%24a%20%3E%200%24%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20P(Y%20%5Cgeq%20a)%20%5Cleq%20%5Cfrac%7B%5Cmathbb%7BE%7D%5BY%5D%7D%7Ba%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20%23%23%23%23%20Derivation%0A%20%20%20%20Let%20%24%5Cmathbb%7BI%7D_%7BY%20%5Cgeq%20a%7D%24%20denote%20the%20indicator%20random%20variable%20that%20equals%20%241%24%20if%20%24Y%20%5Cgeq%20a%24%20and%20%240%24%20otherwise.%20Since%20%24Y%20%5Cgeq%200%24%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20a%20%5Ccdot%20%5Cmathbb%7BI%7D_%7BY%20%5Cgeq%20a%7D%20%5Cleq%20Y%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Taking%20mathematical%20expectations%20on%20both%20sides%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmathbb%7BE%7D%5Ba%20%5Ccdot%20%5Cmathbb%7BI%7D_%7BY%20%5Cgeq%20a%7D%5D%20%5Cleq%20%5Cmathbb%7BE%7D%5BY%5D%20%5Cimplies%20a%20P(Y%20%5Cgeq%20a)%20%5Cleq%20%5Cmathbb%7BE%7D%5BY%5D%20%5Cimplies%20P(Y%20%5Cgeq%20a)%20%5Cleq%20%5Cfrac%7B%5Cmathbb%7BE%7D%5BY%5D%7D%7Ba%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%23%20Chebyshev's%20Inequality%3A%20The%20Second-Moment%20Extension%0A%0A%20%20%20%20Let%20%24X%24%20be%20any%20random%20variable%20with%20finite%20mean%20%24%5Cmu%20%3D%20%5Cmathbb%7BE%7D%5BX%5D%24%20and%20finite%20variance%20%24%5Csigma%5E2%20%3D%20%5Ctext%7BVar%7D(X)%20%3C%20%5Cinfty%24.%0A%20%20%20%20We%20apply%20Markov's%20inequality%20to%20the%20non-negative%20random%20variable%20%24Y%20%3D%20(X%20-%20%5Cmu)%5E2%24%20with%20threshold%20%24a%20%3D%20(k%5Csigma)%5E2%24%20for%20%24k%20%3E%200%24%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20P(%7CX%20-%20%5Cmu%7C%20%5Cgeq%20k%5Csigma)%20%3D%20P%5Cleft((X%20-%20%5Cmu)%5E2%20%5Cgeq%20k%5E2%20%5Csigma%5E2%5Cright)%20%5Cleq%20%5Cfrac%7B%5Cmathbb%7BE%7D%5B(X%20-%20%5Cmu)%5E2%5D%7D%7Bk%5E2%20%5Csigma%5E2%7D%20%3D%20%5Cfrac%7B%5Csigma%5E2%7D%7Bk%5E2%20%5Csigma%5E2%7D%20%3D%20%5Cfrac%7B1%7D%7Bk%5E2%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20%23%23%23%23%20Version%201%20(Tail%20Probability%20Upper%20Bound)%0A%20%20%20%20The%20probability%20that%20a%20random%20variable%20deviates%20from%20its%20mean%20by%20%24k%24%20or%20more%20standard%20deviations%20is%20bounded%20from%20above%20by%20%241%2Fk%5E2%24%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20P(%7CX%20-%20%5Cmu%7C%20%5Cgeq%20k%5Csigma)%20%5Cleq%20%5Cfrac%7B1%7D%7Bk%5E2%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20%23%23%23%23%20Version%202%20(Concentration%20Lower%20Bound)%0A%20%20%20%20Taking%20the%20complementary%20probability%2C%20the%20fraction%20of%20values%20lying%20strictly%20within%20%24k%24%20standard%20deviations%20is%20bounded%20from%20below%20by%20%241%20-%201%2Fk%5E2%24%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20P(%7CX%20-%20%5Cmu%7C%20%3C%20k%5Csigma)%20%5Cgeq%201%20-%20%5Cfrac%7B1%7D%7Bk%5E2%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20%23%23%23%23%20Practical%20Numerical%20Thresholds%0A%20%20%20%20*%20%24k%20%3D%202%24%3A%20%24P(%7CX%20-%20%5Cmu%7C%20%3C%202%5Csigma)%20%5Cgeq%201%20-%20%5Cfrac%7B1%7D%7B4%7D%20%3D%2075.00%5C%25%24%0A%20%20%20%20*%20%24k%20%3D%203%24%3A%20%24P(%7CX%20-%20%5Cmu%7C%20%3C%203%5Csigma)%20%5Cgeq%201%20-%20%5Cfrac%7B1%7D%7B9%7D%20%5Capprox%2088.89%5C%25%24%0A%20%20%20%20*%20%24k%20%3D%204%24%3A%20%24P(%7CX%20-%20%5Cmu%7C%20%3C%204%5Csigma)%20%5Cgeq%201%20-%20%5Cfrac%7B1%7D%7B16%7D%20%3D%2093.75%5C%25%24%0A%20%20%20%20*%20%24k%20%3D%205%24%3A%20%24P(%7CX%20-%20%5Cmu%7C%20%3C%205%5Csigma)%20%5Cgeq%201%20-%20%5Cfrac%7B1%7D%7B25%7D%20%3D%2096.00%5C%25%24%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%23%20Proof%20of%20the%20Weak%20Law%20of%20Large%20Numbers%20(WLLN)%0A%0A%20%20%20%20Let%20%24X_1%2C%20X_2%2C%20%5Cdots%2C%20X_n%24%20be%20independent%2C%20identically%20distributed%20(i.i.d.)%20random%20variables%20with%20mean%20%24%5Cmu%24%20and%20variance%20%24%5Csigma%5E2%24.%0A%20%20%20%20The%20sample%20mean%20is%20%24%5Cbar%7BX%7D_n%20%3D%20%5Cfrac%7B1%7D%7Bn%7D%20%5Csum_%7Bi%3D1%7D%5En%20X_i%24.%0A%20%20%20%20The%20expectation%20and%20variance%20of%20the%20sample%20mean%20are%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Cmathbb%7BE%7D%5B%5Cbar%7BX%7D_n%5D%20%3D%20%5Cmu%2C%20%5Cquad%20%5Ctext%7BVar%7D(%5Cbar%7BX%7D_n)%20%3D%20%5Cfrac%7B%5Csigma%5E2%7D%7Bn%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Applying%20Chebyshev's%20inequality%20to%20%24%5Cbar%7BX%7D_n%24%20with%20arbitrary%20error%20tolerance%20%24%5Cepsilon%20%3E%200%24%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20P(%7C%5Cbar%7BX%7D_n%20-%20%5Cmu%7C%20%5Cgeq%20%5Cepsilon)%20%5Cleq%20%5Cfrac%7B%5Ctext%7BVar%7D(%5Cbar%7BX%7D_n)%7D%7B%5Cepsilon%5E2%7D%20%3D%20%5Cfrac%7B%5Csigma%5E2%7D%7Bn%20%5Cepsilon%5E2%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Taking%20the%20limit%20as%20the%20sample%20size%20%24n%20%5Cto%20%5Cinfty%24%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20%5Clim_%7Bn%20%5Cto%20%5Cinfty%7D%20P(%7C%5Cbar%7BX%7D_n%20-%20%5Cmu%7C%20%5Cgeq%20%5Cepsilon)%20%5Cleq%20%5Clim_%7Bn%20%5Cto%20%5Cinfty%7D%20%5Cfrac%7B%5Csigma%5E2%7D%7Bn%20%5Cepsilon%5E2%7D%20%3D%200%0A%20%20%20%20%24%24%0A%0A%20%20%20%20This%20establishes%20**convergence%20in%20probability**%20(%24%5Cbar%7BX%7D_n%20%5Cxrightarrow%7BP%7D%20%5Cmu%24)%2C%20proving%20the%20fundamental%20theorem%20of%20empirical%20science.%0A%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%23%20Tightness%20and%20Comparison%20Across%20Probability%20Distributions%0A%0A%20%20%20%20Chebyshev's%20bound%20is%20sharp%3A%20it%20cannot%20be%20improved%20without%20making%20additional%20assumptions%20beyond%20finite%20variance.%20A%20discrete%20random%20variable%20taking%20values%20%24%5Cmu%20-%20k%5Csigma%24%20and%20%24%5Cmu%20%2B%20k%5Csigma%24%20each%20with%20probability%20%24%5Cfrac%7B1%7D%7B2k%5E2%7D%24%2C%20and%20%24%5Cmu%24%20with%20probability%20%241%20-%20%5Cfrac%7B1%7D%7Bk%5E2%7D%24%2C%20satisfies%20the%20bound%20with%20exact%20equality.%0A%0A%20%20%20%20When%20specific%20distributional%20families%20are%20known%2C%20exact%20tail%20probabilities%20are%20substantially%20smaller%3A%0A%20%20%20%20*%20**Normal%20Distribution**%3A%20%24P(%7CX%20-%20%5Cmu%7C%20%5Cgeq%202%5Csigma)%20%5Capprox%204.55%5C%25%24%20(Chebyshev%20upper%20bound%3A%20%2425%5C%25%24).%0A%20%20%20%20*%20**Uniform%20Distribution**%3A%20%24P(%7CX%20-%20%5Cmu%7C%20%5Cgeq%202%5Csigma)%20%3D%200%5C%25%24%20(since%20maximum%20deviation%20is%20%24%5Csqrt%7B3%7D%5Csigma%20%5Capprox%201.732%5Csigma%24).%0A%20%20%20%20*%20**Exponential%20Distribution**%3A%20%24P(%7CX%20-%20%5Cmu%7C%20%5Cgeq%202%5Csigma)%20%5Capprox%204.98%5C%25%24.%0A%20%20%20%20*%20**Student-t%20(%24df%20%3D%204%24)**%3A%20%24P(%7CX%20-%20%5Cmu%7C%20%5Cgeq%202%5Csigma)%20%5Capprox%207.92%5C%25%24.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%20%5Bc%5D%20Interactive%20Visualizations%3A%20Universal%20Bounds%20Across%20Diverse%20Distributions%0A%0A%20%20%20%20The%20interactive%20subplots%20below%20display%20Chebyshev's%20distribution-free%20guarantee%3A%0A%20%20%20%20*%20**Left%20Panel**%3A%20Tail%20probability%20%24P(%7CX%20-%20%5Cmu%7C%20%5Cgeq%20k%5Csigma)%24%20as%20a%20function%20of%20the%20deviation%20factor%20%24k%24.%20The%20red%20curve%20represents%20the%20universal%20Chebyshev%20envelope%20%241%2Fk%5E2%24.%20Regardless%20of%20distribution%20(Gaussian%2C%20Exponential%2C%20Uniform%2C%20Student-t)%2C%20all%20tail%20probabilities%20remain%20strictly%20beneath%20this%20theoretical%20ceiling.%0A%20%20%20%20*%20**Right%20Panel**%3A%20Probability%20density%20of%20an%20asymmetric%20Exponential%20distribution%20(%24%5Clambda%20%3D%201.0%24)%2C%20with%20shaded%20regions%20marking%20the%20guaranteed%20inner%20mass%20(%24P%20%5Cgeq%2075%5C%25%24)%20and%20bounded%20tail%20mass%20(%24P%20%5Cleq%2025%5C%25%24)%20at%20%24k%20%3D%202%24.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(go%2C%20make_subplots%2C%20np%2C%20stats)%3A%0A%20%20%20%20%23%20Left%20Panel%3A%20Tail%20Probability%20vs%20k%20comparison%0A%20%20%20%20k_values%20%3D%20np.linspace(1.1%2C%204.5%2C%20120)%0A%20%20%20%20chebyshev_bound_curve%20%3D%201.0%20%2F%20(k_values**2)%0A%0A%20%20%20%20%23%20Theoretical%20tails%20for%20standardized%20distributions%20(mean%3D0%2C%20std%3D1)%0A%20%20%20%20%23%201.%20Normal%20N(0%2C%201)%0A%20%20%20%20normal_tail_curve%20%3D%202.0%20*%20(1.0%20-%20stats.norm.cdf(k_values))%0A%0A%20%20%20%20%23%202.%20Standardized%20Exponential(1)%3A%20mean%3D1%2C%20std%3D1.%0A%20%20%20%20%23%20Deviation%20%7CX%20-%201%7C%20%3E%3D%20k%20%3D%3E%20X%20%3E%3D%201%20%2B%20k%20(since%20X%20%3E%3D%200%2C%20for%20k%20%3E%201%2C%201%20-%20k%20%3C%200%20is%20impossible)%0A%20%20%20%20exp_tail_curve%20%3D%20np.exp(-(1.0%20%2B%20k_values))%0A%0A%20%20%20%20%23%203.%20Student-t%20with%20df%3D4%20(heavy%20tails%2C%20std%20%3D%20sqrt(4%2F(4-2))%20%3D%20sqrt(2))%0A%20%20%20%20t_tail_curve%20%3D%202.0%20*%20(1.0%20-%20stats.t.cdf(k_values%20*%20np.sqrt(2.0)%2C%20df%3D4))%0A%0A%20%20%20%20%23%204.%20Standardized%20Uniform%5B-sqrt(3)%2C%20sqrt(3)%5D%0A%20%20%20%20uniform_tail_curve%20%3D%20np.maximum(0.0%2C%201.0%20-%20k_values%20%2F%20np.sqrt(3.0))%0A%0A%20%20%20%20%23%20Right%20Panel%3A%20Exponential%20distribution%20with%20k%20%3D%202%20coverage%0A%20%20%20%20x_grid%20%3D%20np.linspace(0.0%2C%206.0%2C%20300)%0A%20%20%20%20exp_pdf%20%3D%20np.exp(-x_grid)%0A%20%20%20%20mu_exp%20%3D%201.0%0A%20%20%20%20sigma_exp%20%3D%201.0%0A%20%20%20%20k_demo%20%3D%202.0%0A%20%20%20%20lower_cutoff%20%3D%20max(0.0%2C%20mu_exp%20-%20k_demo%20*%20sigma_exp)%0A%20%20%20%20upper_cutoff%20%3D%20mu_exp%20%2B%20k_demo%20*%20sigma_exp%0A%0A%20%20%20%20fig%20%3D%20make_subplots(%0A%20%20%20%20%20%20%20%20rows%3D1%2C%0A%20%20%20%20%20%20%20%20cols%3D2%2C%0A%20%20%20%20%20%20%20%20subplot_titles%3D%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Tail%20Probability%20vs%20Deviation%20Factor%20(k)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22Coverage%20on%20Skewed%20Exponential%20Distribution%20(k%20%3D%202)%22%2C%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Left%3A%20Chebyshev%20Upper%20Bound%0A%20%20%20%20fig.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dk_values%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dchebyshev_bound_curve%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%23dc2626%22%2C%20width%3D3.5)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Chebyshev%20Envelope%20(1%2Fk%C2%B2)%22%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20row%3D1%2C%0A%20%20%20%20%20%20%20%20col%3D1%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Left%3A%20Normal%20Distribution%0A%20%20%20%20fig.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dk_values%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dnormal_tail_curve%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%232563eb%22%2C%20width%3D2.0)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Normal%20N(0%2C%201)%22%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20row%3D1%2C%0A%20%20%20%20%20%20%20%20col%3D1%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Left%3A%20Student-t%20Distribution%0A%20%20%20%20fig.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dk_values%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dt_tail_curve%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%23ea580c%22%2C%20width%3D2.0)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Student-t%20(df%3D4%2C%20heavy-tailed)%22%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20row%3D1%2C%0A%20%20%20%20%20%20%20%20col%3D1%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Left%3A%20Exponential%20Distribution%0A%20%20%20%20fig.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dk_values%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dexp_tail_curve%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%2316a34a%22%2C%20width%3D2.0)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Exponential(1)%20(skewed)%22%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20row%3D1%2C%0A%20%20%20%20%20%20%20%20col%3D1%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Left%3A%20Uniform%20Distribution%0A%20%20%20%20fig.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dk_values%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Duniform_tail_curve%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%239333ea%22%2C%20width%3D2.0%2C%20dash%3D%22dot%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Uniform%5B-%E2%88%9A3%2C%20%E2%88%9A3%5D%22%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20row%3D1%2C%0A%20%20%20%20%20%20%20%20col%3D1%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Right%3A%20Full%20PDF%0A%20%20%20%20fig.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dx_grid%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dexp_pdf%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%232563eb%22%2C%20width%3D2.5)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Exponential%20PDF%20f(x)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20showlegend%3DTrue%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20row%3D1%2C%0A%20%20%20%20%20%20%20%20col%3D2%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Right%3A%20Shaded%20central%20region%20%5B0%2C%203%5D%20(within%20%C2%B12%CF%83)%0A%20%20%20%20mask_inside%20%3D%20(x_grid%20%3E%3D%20lower_cutoff)%20%26%20(x_grid%20%3C%3D%20upper_cutoff)%0A%20%20%20%20fig.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dnp.concatenate(%5B%5Blower_cutoff%5D%2C%20x_grid%5Bmask_inside%5D%2C%20%5Bupper_cutoff%5D%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dnp.concatenate(%5B%5B0.0%5D%2C%20exp_pdf%5Bmask_inside%5D%2C%20%5B0.0%5D%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20fill%3D%22toself%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20fillcolor%3D%22rgba(37%2C%2099%2C%20235%2C%200.20)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22rgba(255%2C255%2C255%2C0)%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Inside%20%C2%B12%CF%83%20(Actual%3A%2095.0%25%2C%20Bound%3A%20%E2%89%A575%25)%22%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20row%3D1%2C%0A%20%20%20%20%20%20%20%20col%3D2%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Right%3A%20Shaded%20tail%20region%20%5B3%2C%206%5D%20(outside%20%C2%B12%CF%83)%0A%20%20%20%20mask_tail%20%3D%20x_grid%20%3E%3D%20upper_cutoff%0A%20%20%20%20fig.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dnp.concatenate(%5B%5Bupper_cutoff%5D%2C%20x_grid%5Bmask_tail%5D%2C%20%5B6.0%5D%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dnp.concatenate(%5B%5B0.0%5D%2C%20exp_pdf%5Bmask_tail%5D%2C%20%5B0.0%5D%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20fill%3D%22toself%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20fillcolor%3D%22rgba(220%2C%2038%2C%2038%2C%200.30)%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22rgba(255%2C255%2C255%2C0)%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20name%3D%22Tail%20%3E%20%CE%BC%2B2%CF%83%20(Actual%3A%205.0%25%2C%20Bound%3A%20%E2%89%A425%25)%22%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20row%3D1%2C%0A%20%20%20%20%20%20%20%20col%3D2%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20Right%3A%20Vertical%20line%20at%20upper%20cutoff%0A%20%20%20%20fig.add_trace(%0A%20%20%20%20%20%20%20%20go.Scatter(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3D%5Bupper_cutoff%2C%20upper_cutoff%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3D%5B0.0%2C%20np.exp(-upper_cutoff)%20%2B%200.15%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mode%3D%22lines%2Btext%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20line%3Ddict(color%3D%22%23dc2626%22%2C%20width%3D2.0%2C%20dash%3D%22dash%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20text%3D%5B%22%22%2C%20%22%CE%BC%20%2B%202%CF%83%20%3D%203.0%22%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20textposition%3D%22top%20center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20showlegend%3DFalse%2C%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20row%3D1%2C%0A%20%20%20%20%20%20%20%20col%3D2%2C%0A%20%20%20%20)%0A%0A%20%20%20%20fig.update_layout(%0A%20%20%20%20%20%20%20%20template%3D%22plotly_white%22%2C%0A%20%20%20%20%20%20%20%20height%3D520%2C%0A%20%20%20%20%20%20%20%20margin%3Ddict(l%3D40%2C%20r%3D40%2C%20t%3D60%2C%20b%3D40)%2C%0A%20%20%20%20%20%20%20%20xaxis%3Ddict(title%3D%22Deviation%20Factor%20k%22%2C%20gridcolor%3D%22%23f1f5f9%22)%2C%0A%20%20%20%20%20%20%20%20yaxis%3Ddict(title%3D%22Tail%20Probability%20P(%7CX%20-%20%CE%BC%7C%20%E2%89%A5%20k%CF%83)%22%2C%20gridcolor%3D%22%23f1f5f9%22)%2C%0A%20%20%20%20%20%20%20%20xaxis2%3Ddict(title%3D%22x%22%2C%20gridcolor%3D%22%23f1f5f9%22)%2C%0A%20%20%20%20%20%20%20%20yaxis2%3Ddict(title%3D%22Probability%20Density%22%2C%20gridcolor%3D%22%23f1f5f9%22)%2C%0A%20%20%20%20%20%20%20%20legend%3Ddict(orientation%3D%22h%22%2C%20yanchor%3D%22bottom%22%2C%20y%3D-0.26%2C%20xanchor%3D%22center%22%2C%20x%3D0.5)%2C%0A%20%20%20%20)%0A%20%20%20%20return%20(fig%2C)%0A%0A%0A%40app.cell%0Adef%20_(fig%2C%20mo)%3A%0A%20%20%20%20mo.ui.plotly(fig)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%20%5Bd%5D%20Code%20Examples%0A%0A%20%20%20%20%23%23%23%20Example%201%3A%20Empirical%20Verification%20Across%20Five%20Diverse%20Distributions%0A%0A%20%20%20%20In%20this%20example%2C%20we%20generate%20%24N%20%3D%20200%2C000%24%20synthetic%20samples%20from%20five%20fundamentally%20distinct%20distributions%3A%0A%20%20%20%201.%20**Gaussian**%3A%20Standard%20bell-shaped%20symmetric%20distribution.%0A%20%20%20%202.%20**Exponential**%3A%20Heavily%20right-skewed%20non-negative%20distribution.%0A%20%20%20%203.%20**Uniform**%3A%20Bounded%20distribution%20with%20finite%20support.%0A%20%20%20%204.%20**Bimodal%20Gaussian%20Mixture**%3A%20Mixture%20of%20two%20separated%20Gaussian%20components.%0A%20%20%20%205.%20**Student-t%20(%24df%20%3D%205%24)**%3A%20Heavy-tailed%20polynomial%20decay%20distribution.%0A%0A%20%20%20%20For%20each%20distribution%2C%20we%20compute%20the%20empirical%20tail%20probability%20%24P(%7CX%20-%20%5Cmu%7C%20%5Cgeq%20k%5Csigma)%24%20at%20%24k%20%5Cin%20%5C%7B2%2C%203%2C%204%5C%7D%24%20and%20verify%20that%20it%20strictly%20satisfies%20Chebyshev's%20upper%20bound%20(%241%2Fk%5E2%24).%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20rng_sim%20%3D%20np.random.default_rng(42)%0A%20%20%20%20n_samples_sim%20%3D%20200000%0A%0A%20%20%20%20test_distributions%20%3D%20%7B%0A%20%20%20%20%20%20%20%20%22Gaussian%20N(0%2C%201)%22%3A%20rng_sim.standard_normal(n_samples_sim)%2C%0A%20%20%20%20%20%20%20%20%22Exponential(%CE%BB%3D1)%22%3A%20rng_sim.exponential(scale%3D1.0%2C%20size%3Dn_samples_sim)%2C%0A%20%20%20%20%20%20%20%20%22Uniform%5B-2%2C%202%5D%22%3A%20rng_sim.uniform(-2.0%2C%202.0%2C%20size%3Dn_samples_sim)%2C%0A%20%20%20%20%20%20%20%20%22Bimodal%20Mixture%22%3A%20np.concatenate(%0A%20%20%20%20%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rng_sim.normal(-2.5%2C%200.8%2C%20n_samples_sim%20%2F%2F%202)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20rng_sim.normal(2.5%2C%200.8%2C%20n_samples_sim%20%2F%2F%202)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20%20%20%20%20)%2C%0A%20%20%20%20%20%20%20%20%22Student-t%20(df%3D5)%22%3A%20rng_sim.standard_t(df%3D5%2C%20size%3Dn_samples_sim)%2C%0A%20%20%20%20%7D%0A%0A%20%20%20%20empirical_bound_records%20%3D%20%5B%5D%0A%0A%20%20%20%20for%20dist_name%2C%20sample_data%20in%20test_distributions.items()%3A%0A%20%20%20%20%20%20%20%20sample_mean%20%3D%20float(np.mean(sample_data))%0A%20%20%20%20%20%20%20%20sample_std%20%3D%20float(np.std(sample_data))%0A%0A%20%20%20%20%20%20%20%20for%20k_factor%20in%20%5B2%2C%203%2C%204%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20deviations%20%3D%20np.abs(sample_data%20-%20sample_mean)%0A%20%20%20%20%20%20%20%20%20%20%20%20empirical_tail_prob%20%3D%20float(np.mean(deviations%20%3E%3D%20k_factor%20*%20sample_std))%0A%20%20%20%20%20%20%20%20%20%20%20%20theoretical_upper_bound%20%3D%201.0%20%2F%20(k_factor**2)%0A%20%20%20%20%20%20%20%20%20%20%20%20bound_holds%20%3D%20empirical_tail_prob%20%3C%3D%20theoretical_upper_bound%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20empirical_bound_records.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Distribution%22%3A%20dist_name%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22k%20(Std%20Devs)%22%3A%20k_factor%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Empirical%20Tail%20P%22%3A%20f%22%7Bempirical_tail_prob%3A.4f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Chebyshev%20Bound%20(1%2Fk%C2%B2)%22%3A%20f%22%7Btheoretical_upper_bound%3A.4f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Empirical%20Inner%20P%22%3A%20f%22%7B1.0%20-%20empirical_tail_prob%3A.4f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Chebyshev%20Lower%20(1%20-%201%2Fk%C2%B2)%22%3A%20f%22%7B1.0%20-%20theoretical_upper_bound%3A.4f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Bound%20Satisfied%22%3A%20str(bound_holds)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20return%20(empirical_bound_records%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(empirical_bound_records%2C%20mo%2C%20pd)%3A%0A%20%20%20%20df_chebyshev%20%3D%20pd.DataFrame(empirical_bound_records)%0A%20%20%20%20mo.ui.table(df_chebyshev)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20---%0A%0A%20%20%20%20%23%23%23%20Example%202%3A%20Weak%20Law%20of%20Large%20Numbers%20Convergence%20and%20Sample%20Complexity%0A%0A%20%20%20%20By%20Chebyshev's%20inequality%2C%20the%20probability%20that%20the%20sample%20mean%20%24%5Cbar%7BX%7D_n%24%20deviates%20from%20the%20true%20expectation%20%24%5Cmu%24%20by%20more%20than%20tolerance%20%24%5Cepsilon%24%20shrinks%20as%20%24%5Cmathcal%7BO%7D(1%2Fn)%24%3A%0A%0A%20%20%20%20%24%24%0A%20%20%20%20P(%7C%5Cbar%7BX%7D_n%20-%20%5Cmu%7C%20%5Cgeq%20%5Cepsilon)%20%5Cleq%20%5Cfrac%7B%5Csigma%5E2%7D%7Bn%20%5Cepsilon%5E2%7D%0A%20%20%20%20%24%24%0A%0A%20%20%20%20Below%2C%20we%20draw%20from%20a%20population%20with%20true%20mean%20%24%5Cmu%20%3D%205.0%24%20and%20standard%20deviation%20%24%5Csigma%20%3D%202.0%24.%20We%20run%20%24M%20%3D%201%2C000%24%20independent%20Monte%20Carlo%20experiments%20across%20increasing%20sample%20sizes%20%24n%20%5Cin%20%5C%7B50%2C%20100%2C%20250%2C%20500%2C%201000%2C%202500%5C%7D%24%20with%20error%20tolerance%20%24%5Cepsilon%20%3D%200.08%24.%0A%0A%20%20%20%20We%20compare%20the%20empirical%20fraction%20of%20trials%20violating%20tolerance%20against%20the%20theoretical%20Chebyshev%20ceiling.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20rng_wlln%20%3D%20np.random.default_rng(101)%0A%20%20%20%20num_monte_carlo%20%3D%201000%0A%20%20%20%20epsilon_tol%20%3D%200.08%0A%20%20%20%20pop_mean%20%3D%205.0%0A%20%20%20%20pop_std%20%3D%202.0%0A%20%20%20%20sample_sizes_list%20%3D%20%5B50%2C%20100%2C%20250%2C%20500%2C%201000%2C%202500%5D%0A%0A%20%20%20%20wlln_summary_records%20%3D%20%5B%5D%0A%0A%20%20%20%20for%20n_size%20in%20sample_sizes_list%3A%0A%20%20%20%20%20%20%20%20%23%20Draw%20matrix%20of%20shape%20(num_monte_carlo%2C%20n_size)%0A%20%20%20%20%20%20%20%20mc_samples%20%3D%20rng_wlln.normal(loc%3Dpop_mean%2C%20scale%3Dpop_std%2C%20size%3D(num_monte_carlo%2C%20n_size))%0A%20%20%20%20%20%20%20%20sample_means%20%3D%20np.mean(mc_samples%2C%20axis%3D1)%0A%0A%20%20%20%20%20%20%20%20%23%20Proportion%20of%20trials%20where%20%7CX_bar%20-%20mu%7C%20%3E%3D%20epsilon%0A%20%20%20%20%20%20%20%20empirical_violations%20%3D%20float(np.mean(np.abs(sample_means%20-%20pop_mean)%20%3E%3D%20epsilon_tol))%0A%20%20%20%20%20%20%20%20theoretical_bound_wlln%20%3D%20min(1.0%2C%20float((pop_std**2)%20%2F%20(n_size%20*%20(epsilon_tol**2))))%0A%0A%20%20%20%20%20%20%20%20wlln_summary_records.append(%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Sample%20Size%20(n)%22%3A%20n_size%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Error%20Tolerance%20(%CE%B5)%22%3A%20epsilon_tol%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Empirical%20P(%7CX%CC%84%20-%20%CE%BC%7C%20%E2%89%A5%20%CE%B5)%22%3A%20f%22%7Bempirical_violations%3A.4f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Chebyshev%20Upper%20Bound%20(%CF%83%C2%B2%2Fn%CE%B5%C2%B2)%22%3A%20f%22%7Btheoretical_bound_wlln%3A.4f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22Guaranteed%20Convergence%22%3A%20str(empirical_violations%20%3C%3D%20theoretical_bound_wlln)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20return%20(wlln_summary_records%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20pd%2C%20wlln_summary_records)%3A%0A%20%20%20%20df_wlln%20%3D%20pd.DataFrame(wlln_summary_records)%0A%20%20%20%20mo.ui.table(df_wlln)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A
7e53da9a1861f18688f9f040ccce7e13