Think of an airline running many itineraries. Each starts at a random airport (law \(\mu\)), hops along random routes (transition probabilities \(P\)), and ends by a rule that cannot peek ahead (a stopping time \(\tau\)). The final airport has law \(\nu\).
Fix an airport \(y\) and count every stop there. Each stop is either the start of an itinerary or an arrival from an earlier flight, and it is either followed by a departure or is the itinerary’s end. So, on average per itinerary,
departures from \(y\) + itineraries ending at \(y\) = arrivals into \(y\) + itineraries starting at \(y,\)
flowchart LR
S(["Itineraries starting at y"]):::src --> Y
A["Airport x1"] -->|"Flights x1 to y"| Y
B["Airport x2"] -->|"Flights x2 to y"| Y
Y(("Airport y"))
Y -->|"Departures from y"| C["Other airports"]
Y --> E(["Itineraries ending at y"]):::snk
classDef src fill:#d8f0e0,stroke:#2e7d4f,color:#12351f
classDef snk fill:#fbe0dc,stroke:#b3402f,color:#4a1610
Formally, let \(\{X_t\}_t\) be a Markov chain (the walk over desatinations); define occupancy as \(g(y) = \mathbb{E}\sum_{t=0}^{\tau-1} \mathbf{1}\{X_t=y\}\) (the expected departure counts from \(y\)). Then, the occuapancy solves the following dual Poisson-type equation in the space of measures
Theorem(Poisson-type Occupancy Equation). With the notation as above:
the second identity over the effective domain of \(g\).
Proof. On every itinerary, the visits to \(y\) before the end, plus the final stop if there is one, equal the start plus the arrivals:
Take expectations. On the right, \(\{t<\tau\}\) is known at time \(t\), before the next flight, so the Markov property gives \(\mathbb{E}\big[\mathbf{1}\{t<\tau\}\mathbf{1}\{X_{t+1}=y\}\big]=\mathbb{E}\big[\mathbf{1}\{t<\tau\}P(X_t,y)\big]\). Summing over \(t\) (Tonelli, all terms are \(\ge0\)) gives \((gP)(y)\). \(\square\).
Applications. A number of classical results follow. For the first two, assume the chain is irreducible and positive recurrent with stationary law \(\pi\).
Corollary (stationary occupation). If \(\mu=\nu\) (which forces \(\tau<\infty\) a.s.) and \(\mathbb{E}\tau<\infty\), then \(gP=g\), so \(g=\pi\,\mathbb{E}\tau\). The time spent in any set \(S\) is \(\pi(S)\,\mathbb{E}\tau\) in expectation, even from a non-stationary start.
Corollary (Kac). Start at \(z\) and stop at the first return \(T_z^+\). The itinerary visits \(z\) once, so \(g(z)=1\) and \(\displaystyle \mathbb{E}_zT_z^+=\frac{1}{\pi(z)}\). Every other airport \(y\) is visited \(\pi(y)/\pi(z)\) times per loop.
Corollary (Poisson equation). For a finite irreducible chain with \(\mathbb{E}_\mu\tau<\infty\), let \((I-P)h=f-\pi(f)\). Then
When the endpoint laws differ, the mismatch becomes an explicit correction. Pair \(g(I-P)=\mu-\nu\) with \(h\).
Credit. The balance identity is due to Pitman (Prop. 4.1). Its equal-endpoint case, Cor. 3 appears as Prop. 2.4 in Aldous and Fill . Kac’s return-time formula is the case of a single-state excursion. Reading the identity as a dual Poisson equation and pairing it with \(h\) gives the Poisson corollary above, which for finite chains needs no aperiodicity, unlike Pitman’s Prop. 4.6(iii).
One-sided fractional Brownian Motion, introduced in , is an interesting class of Gaussian process, defined as a continuous moving average (CMA) of white noise:
where \(B_u\) is the standard Brownian motion, and integration is understood in the mean-quadratic (Ito) sense for \(H>0\). This process has found important applications in electronics for modelling oscillatory noise , because its spectrum follows a power law.
This note presents a simple yet formal derivation of the fBM spectrum. The argument originally given in is somewhat complicated and leaves some gaps. The novel approach develops a handy closed-form formula using hypergeometric functions, establishing exact convergence rates of time-averaged spectra.
Since \eqref{eq:fbm} is nonstationary, we are going to use the Wigner-Ville instantaneous spectrum, which is the time-varying Fourier transform of the covariance with respect to the lag:
We easily find that the covariance of \(X=X_H\) in terms of time-difference coordinates equals $$ K_X\left(t-\frac{\tau}{2},t+\frac{\tau}{2}\right) = \frac{\left(t-\frac{|\tau|}{2}\right)^{H+\frac{1}{2}}\left(\frac{|\tau|}{2}+t\right)^{H-\frac{1}{2}}\,_2F_1\left(1,\frac{1}{2}-H;H+\frac{3}{2};\frac{2t-|\tau|}{2t+|\tau|}\right)}{\Gamma\left(H+\frac{1}{2}\right)\Gamma\left(H+\frac{3}{2}\right)} \tag{3}\label{eq:covariance} $$ when \(|\tau| < t\), and is zero otherwise. Rather than directly transforming the covariance, we will be working with its second-derivative which happens to have a very simple form: $$ \frac{\partial^2}{\partial t^2} K_X\left(t-\frac{\tau}{2},t+\frac{\tau}{2}\right) = \frac{4^{2-H}t(4t^2-\tau^2)^{H-\frac{3}{2}}}{\Gamma\left(H-\frac{1}{2}\right)\Gamma\left(H+\frac{1}{2}\right)}\tag{4}\label{eq:covarianceD2}\cdot \mathbf{1}\{ |\tau| < 2 t \}, $$
and whose Fourier transform is easy to find in terms of the hypergeometric function \(_0F_1\) $$ \widehat{F}_{\tau} \left[ \frac{\partial^2}{\partial t^2} K_X\left(t-\frac{\tau}{2},t+\frac{\tau}{2}\right) \right](\omega) = \frac{4\sqrt{\pi}t^{2H-1}\,_0F_1\left(;H;-t^2\omega^2\right)}{\Gamma(H) \Gamma\left(H+\frac{1}{2}\right)} \tag{5}\label{eq:covarianceD2_FT}. $$
By taking the antiderivative twice, we find that the spectrum can be expressed in terms of \(_1F_2\): $$ S_X(t,\omega) = \frac{2^{2H+1}t^{2H+1}\,_1F_2\left(H+\frac{1}{2};H+1,H+\frac{3}{2};-t^2\omega^2\right)}{\Gamma(2H+2)} \tag{6}\label{eq:covariance_FT}. $$ The representation in \eqref{eq:covariance_FT} has the advantage that the \(_1F_2\) expression represents a smooth function which is easy to approximate. Using the theory of hypergeometric functions, we easily find that the instantaneous spectrum oscillates around \(\omega^{-2H-1}\): $$S_X(t,\omega) = \omega^{-2H-1}\left(1-O\left(\frac{(t \omega)^{H-\frac{1}{2}}\left(\sin\left(\frac{\pi H}{2}-2t\omega\right)+\cos\left(\frac{\pi H}{2}-2t\omega\right)\right)}{\sqrt{2}\Gamma\left(H+\frac{1}{2}\right)}\right)\right) \tag{7}\label{eq:covariance_FT_approx}. $$
Deviations of instantaneous spectrum from the long-time average.
Despite these growing oscillations, we can prove that the running average converges and matches the power-law. Namely, when \(0<H<\frac{3}{2}\) we have the explicit formula $$ \frac{1}{T}\int_{0}^T S_X(t,\omega)\ \mbox{d} t = \frac{2^{2H+1}T^{2H+1}\,_1F_2\left(H+\frac{1}{2};H+\frac{3}{2},H+2;-T^2\omega^2\right)}{\Gamma(2H+3)} \tag{8}\label{eq:covariance_FT_average}, $$ with the asymptotic behaviour $$\frac{1}{T}\int_{0}^T S_X(t,\omega)\ \mbox{d} t = \omega^{-2H-1}\left(1+O_H(T\omega)^{H-\frac{3}{2}}\right), \quad T\omega \gg 1 \tag{9}\label{eq:covariance_FT_average_approx}, $$ demonstrating, for \(0<H<\frac{3}{2}\), the power law \(\omega^{-2H-1}\) as expected.
It should be noted that using the asymptotic expansion \eqref{eq:covariance_FT_approx} is insufficient to obtain the convergence rate in \eqref{eq:covariance_FT_average_approx}. This is because its second-order error term \(O((t\omega)^{H-3/2})\) does not capture oscillations, as seen with \(H=1/2\) resulting in an error term \(O(\log T / (T\omega))\).
Extracting from bit streams remains an active research area in modern cryptography. Recently, there has been renewed interest in debasing with structured linear mappings, namely by linear codes. Linear codes were proposed as extractors for independent but biased bits in the theory community . Decades later, they were popularized among the hardware designers , and the bounds were refined for precise entropy assessment . The recent work obtained new non-oblivious min-entropy bounds for heterogenous independent bits. This note shows how to establish condensing properties using Fourier Analysis.
Fourier Analysis Basics
For a good introduction into the state-of-the-art Fourier techniques for boolean functions, see . Recall that every \(f : \{0,1\}^n \to \mathbb{R}\) has the (Fourier) expansion as a combination of parity functions: $$ f(x) = \sum_{S \subseteq [n]} \widehat{f}(S) \chi_S(x), $$ with coefficients given by $$ \widehat{f}(S) = 2^{-n}\sum_x f(x) \chi_S(x). $$
Then comes the Parseval theorem, on isometric properties of the Fourier transform: \begin{equation} 2^{-n} \sum_{x\in{0,1}^n} f(x)^2 = \sum_{S \subset [1\ldots n]} \widehat{f}(S)^2. \end{equation} Fourier analysis is often applied to probability distributions \(\mu\) on bit strings. In this case, the Parseval theorem can be restated nicely using the notion of bit bias: $$ \left\| \mu – 2^{-n}\right\|_2 = \sqrt{2^{n} \sum_{\emptyset\not=S \subset [1\ldots n]} \widehat{\mu}(S)^2} =\sqrt{2^{-n} \sum_{\emptyset\not=S \subset [1\ldots n]} \operatorname{bias}\left( \oplus_{i\in S} X_i \right)^2 }, $$ and in this modern form is known as (not surprisingly) the XOR lemma . Recall that the bit bias is \(\mathrm{bias}(X) = \mathbf{P}\{X=1\}-\mathbf{P}\{X=0\} \).
Linear Codes
A linear code is a subspace of \(\mathbb{F}_2^n\), generated by rows of a matrix \(G: \{0,1\}^{m\times n}\). We apply the code matrix to a source \(X_1,\ldots,X_n\) obtaining $$ \begin{bmatrix} Y_1 \\ Y_2 \\ \vdots \\ Y_n \end{bmatrix} = G \cdot \begin{bmatrix} X_1 \\ X_2 \\ \vdots \\ X_n \end{bmatrix}. $$ To generate useful output, the code needs more structure, for instance relatively large Hamming weights. This means that every subset of rows in the matrix should sum up (in \(\mathbb{F}_2\), that is modulo 2) to a not-too-small number, as this will ensure small biases in the XOR lemma.
Condensing and Extraction Properties
Say that \(X_i\) are IID with bias \(\delta\). Then we can expressthe collision entropy of the output in terms of code Hamming weights, using Fourier analysis. Indeed, applying the XOR lemma: $$ \|\mathbf{P}_Y\|_2^2- 2^{-m} = \|\mathbf{P}_Y – 2^{-m}\|_2^2= 2^{-m}\sum_{\mathbf{0}\not=u \in \operatorname{rowspan}(G) } \operatorname{bias}( \oplus u_i X_i)^2 = 2^{-m} \sum_{\mathbf{0}\not= u} \mathbf{W}(k) \delta^{2k } , $$ where \(\mathbf{W}(k)\) is the number of code words with Hamming weight \(k\) (recall that the second norm can be restated as the collision entropy).
Using standard norm inequalities, we obtain the following useful bounds \begin{align} \begin{aligned} \|\mathbf{P}_Y\|_{\infty} – 2^{-m} & \leq \left( 2^{-m} \sum_{\mathbf{0}\not= u} \mathbf{W}(k) \delta^{2k }\right)^{1/2} \\ \|\mathbf{P}_Y – 2^{-m}\|_{1} & \leq \left( \sum_{\mathbf{0}\not= u} \mathbf{W}(k) \delta^{2k } \right)^{1/2}. \end{aligned} \end{align} for min-entropy and smooth min-entropy of the outout \(Y\) respectively.
When the code has distance \(d\), e.g. \(\mathbf{W}(k)\geq d\), then $$ \begin{aligned} \max_{y} \mathbf{P}\{Y=y\} & \leq 2^{-m} + \delta^{d} \\ \|\mathbf{P}_Y – 2^{-m}\|_{1} & \leq 2^{m/2}\delta^d \end{aligned} $$ The first bound is due to . The second bound is stronger than Corollary 3 in . The general formula for the second norm appears to be somewhat novel. It can be used to improve upon the results of from high unpredictability to near uniformity, as high min-entropy is not sufficient for all cryptographic applications.
While the derived formula is non-oblivious, computing the code distribution is a hard problem. It would be interesting to propose some approximation schemes for this purpose.
For many problems in mathematics and theoretical computer science, it is of interest to estimate concentration of sums of heterogenous boolean random variables. This note shows some new results obtained through majorization theory with computer-aided proof in SymPy.
Results
The Poisson Binomial distribution \(Y\sim \mathrm{PB}(p) \) is defined for \(p=(p_1,\ldots, p_n)\) as $$ Y = \sum_{i=1}^n X_i,\quad X_i \sim \mathrm{Bern}(p_i). $$
We are interested in the concentration properties of \(Y\) and its dependency on \( p=(p_1,\ldots,p_n)\). To (partly) answer this question, show that for any convex and non-decreasing function \(f\), the \(f\)-expectation of the PB distribution is Schur-concave with respect to the parameters: $$ \mathbf{E} f(\mathrm{PB}(p) ) \leq \mathbf{E} f(\mathrm{PB}(p’) ),\quad p’ \prec p, $$ where \(X_i\) are independent and \(p \prec p’\) denotes vector majorization. In particular, this means that $$ \mathbf{E} f(\mathrm{PB}(p) ) \leq \mathbf{E}f(\mathrm{Binom}(\bar{p}),\quad \bar{p} = \frac{1}{n}\sum_{i=1}^{n} p_i, $$ which means that the Binomial case is the “most dispersed” one. As for related work, see the recent survey , in particular the Schur-concavity of the tails. The result above is more general, as by focusing on functional expectations it yields various concentration bounds and is applicable to setups with limited dependence, such as \(k\)-wise independence. Indeed, by using \(f(x) = \max\{x,0\}^d\) and assuming that every \(d\) of \(X_i\) are independent, we can improve the previous concentration bounds . Numerically optimal results may be computed with recent formulas for binomial moments .
Proof Sketch
To prove the claim, we will check the Schur-Ostrowski criterion, namely that $$ \Delta_{i,j}\triangleq \left(p_i – p_j\right) \left(\frac{\partial \mathbf{E} f(\mathrm{PB}(p) ) }{ \partial p_i} – \frac{\partial \mathbf{E} f(\mathrm{PB}(p) ) }{ \partial p_j}\right) \leq 0. $$ Due to the independence of the summands $$\mathbf{E}f(Y) = \sum_{y}\mathbf{P}\{Y-X_i-X_j= y\} \mathbf{E}_{X_i,X_j}[f(X_i + X_j + y),$$ it suffices to test for any pair of variables, while treating the sum of the remaining variables \(Y-X_i-X_j\) as fixed. Since the convexity and monotonicity of \(f\) are invariant to translations, we can just work with \(\mathbf{E} f(X_i+ X_j)\). Without loss of generality, we can test this for \(i=1, j=2\), as the variables are identically distributed. Now, let’s implement this in Python!
We obtained $$ \Delta_{i,j}=\left(p_{1} p_{2} – p_{1} – p_{2}^{2}\right) f{\left(2 \right)} + \left(- 2 p_{1} p_{2} + 3 p_{1} + 2 p_{2}^{2} – p_{2} – 1\right) f{\left(1 \right)} + \left(p_{1} p_{2} – 2 p_{1} – p_{2}^{2} + p_{2} + 1\right) f{\left(0 \right)}. $$ To simplify this expression and made use of the remaining assumptions, let us introduce \(\delta_{convex} = \frac{f(2)+f(0)}{2}-f(1)\) and \(\delta_{monotone} = f(1)-f(0)\), both non-negative. Further calculations in SymPy
In this post, I overview the optimal non-parametric approach to quantile confidence intervals. We will discuss the theoretical background as well as an efficient algorithm implemented in Python.
Consider an ordered iid sample \(x^{(1)} < x^{(2)} < \ldots < x^{(n)}\) from a distribution \(X\), and let \(q\) be the \(p\)-th quantile, that is \(\mathbf{P}\{X\leqslant q\}=p\). Using our samples we want to build a possibly short confidence interval with satisfying coverage, that is to solve the optimization problem \begin{align} \begin{aligned} \mathrm{minimize} && r-\ell \\ && \mathbf{P}\{ x^{(\ell)} \leqslant q \leqslant x^{(r)} \} \geqslant 1-\alpha \end{aligned} \end{align}
We start with establishing explicit formulas for the coverage probability. First,
because \(x^{(k)} \leqslant q\) means that at least \(k\) samples are smaller or equal to \(q\). Accordingly, $$ \mathbf{P}\{ x^{(k)} < q \} = \mathbf{P}\{ \mathsf{Binom}(n,p^{-}) \geqslant k\}, $$ with \(p^{-} = \mathbf{P}\{X < q\} \). Therefore, we obtain $$ \mathbf{P}\{ x^{(\ell)} \leqslant q \leqslant x^{(r)} \} = \mathbf{P}\{ \mathsf{Binom}(n,p) \geqslant \ell\} – \mathbf{P}\{ \mathsf{Binom}(n,p^{-}) \geqslant r\}, $$ which reduces to \(\mathbf{P}\{ x^{(\ell)} \leqslant q \leqslant x^{(r)} \} = \mathbf{P}\{ \ell\leqslant \mathsf{Binom}(n,p) \leqslant r-1\} \) if \(q\) is a discontinuity point (this has been known for strictly increasing continuous CDFs 1). Since $$ 1-\mathbf{P}\{ x^{(\ell)} \leqslant q \leqslant x^{(r)} \} = \mathbf{P}\{ \mathsf{Binom}(n,p) \leqslant \ell-1\} + \mathbf{P}\{ \mathsf{Binom}(n,p^{-}) \geqslant r\}, $$ the smallest interval with coverage at least \(1-\alpha\) is determined by the optimization task \begin{align} \begin{aligned} \min_{\ell\leqslant r}&& r-\ell \\ && \mathbf{P}\{ \mathsf{Binom}(n,p) \leqslant \ell-1\} + \mathbf{P}\{ \mathsf{Binom}(n,p^{-}) \geqslant r\} \geqslant \alpha \end{aligned} && (*) \end{align} which can be solved under the necessary condition that \begin{align} (1-p)^{n} + (p^{-})^n \leqslant \alpha. \end{align}
Introducing \(r :=n -r + 1\) we obtain the more convenient/symmetric formulation \begin{align} \begin{aligned} \max_{\ell+r\leqslant n+1}&& \ell + r \\ && \mathbf{P}\{ \mathsf{Binom}(n,p) \leqslant \ell-1\} + \mathbf{P}\{ \mathsf{Binom}(n,1-p^{-}) \leqslant r-1\} \leqslant \alpha \end{aligned} \end{align} and use this formulation to develop an algorithm in Python
from scipy import statsdefquantile_ci(x,p,alpha,p_minus=None,):# solve related binomial covering problem n =len(x)ifnot p_minus: p_minus = p ks = np.arange(n+1) probs_l = stats.binom(n,p).pmf(ks) probs_r = stats.binom(n,1-p_minus).pmf(ks) i_l =0 i_r =0 total = probs_l[i_l]+ probs_r[i_r]while(i_l + i_r < n)and(total <= alpha): p_l = probs_l[i_l+1] p_r = probs_r[i_r+1]if p_l <= p_r: total += p_lif total <= alpha: i_l +=1else: total += p_rif total < alpha: i_r +=1# convert to original indices i_l = i_l+1 i_r =(n+1)-(i_r+1)return(i_l,i_r)
As an example, consider times to failure in hours for a set of pentode radio valves 2:
Zieliński R, Zieliński W. Best exact nonparametric confidence intervals for quantiles. Statistics. Published online February 2005:67-71. doi:10.1080/02331880412331329854
2.
Conover WJ. Practical Nonparametric Statistics. John Wiley & Sons; 1999.
The zero-truncated Poisson distribution is useful to model certain demographic data, such as sizes of households and families 1. This post illustrates this on historical data from the United Kingdom and demonstrates how to assess the goodness-of-fit in Python.
The zero-truncated Poisson distribution \(Y\) is defined as \begin{align} \mathbf{P}\{Y=x\} = \mathbf{P}\{ X = x | X > 0\}, \quad X\sim \mathrm{Poiss}(\lambda) . \end{align} Conditioning which removes zero counts makes it a perfect fit for counting data that starts from 1. For example, consider the following historical UK data from a demographic research study 2
The source data can be read into Python and visualized as follows
import matplotlib.pyplot as pltimport seaborn as snsimport pandas as pdimport numpy as npN =98counts = np.array([5.7,14.2,16.5,15.8,14.7,11.8,8.0,5.4,3.1,1.9,1.1,0.7,1.1])/100* Nbins = pd.IntervalIndex.from_breaks(list(np.arange(1,13+1))+[np.inf],closed="left",name="household size")counts = pd.Series(data=counts,name="count",index=bins)fig,ax = plt.subplots(figsize=(12,4))sns.barplot(counts.reset_index(),x="household size",y="count",ax=ax)ax.tick_params(axis='x',labelrotation=45)
Now, we hypothetize the truncated Python distribution with \(\lambda = 5\), and test the fit quality by adjusting the chi-square method. This chi-squared technique boils down to binning a reference distribution into finitely many categories, consistently with the empirical data, and is well-explained in R packages3. We obtain a high p-value which confirms a good fit:
Jennings V, Lloyd-Smith B, Ironmonger D. Household size and the poisson distribution. Journal of Population Research. Published online May 1999:65-84. doi:10.1007/bf03029455
2.
Laslett P. Size and structure of the household in England over three centuries. Population Studies. Published online July 1969:199-223. doi:10.1080/00324728.1969.10405278
QQ plots, despite their importance, are not well-supported in Python, as of the moment of writing this note. The package statsmodels offers plots of rather poor quality and non-interactive, and even Plotly doesn’t come with its own recipe. In this note, I am sharing how to build an interactive QQ plot and apply it to improve linear regression.
I will use the state-of-the art Vega-Lite language dedicated to interactive visualization, available in Python through the package Altair API.
Let’s use the famous “Prestige” dataset1, and look how prestige is explained by income, education, and job type:
\( prestige \sim income + education:type \)
The model residuals do not follow the normal distribution (as rejected by the Jarque-Bera test). It turns out that the normality of residuals is broken by an anomaly visible on QQ plots. The anomaly in the top-right corner comes from the minister job (hover to inspect!), which comes with high prestige and little money 😉
After removing the political anomaly, the model behaves properly 😉
OLS Regression Results
Dep. Variable:
prestige
R-squared:
0.922
Model:
OLS
Adj. R-squared:
0.914
Method:
Least Squares
F-statistic:
115.8
Date:
Sat, 06 Apr 2024
Prob (F-statistic):
4.31e-21
Time:
18:03:24
Log-Likelihood:
-157.21
No. Observations:
44
AIC:
324.4
Df Residuals:
39
BIC:
333.3
Df Model:
4
Covariance Type:
nonrobust
Omnibus:
3.775
Durbin-Watson:
1.960
Prob(Omnibus):
0.151
Jarque-Bera (JB):
2.734
Skew:
0.583
Prob(JB):
0.255
Kurtosis:
3.365
Cond. No.
261.
Diagnosing and fixing regression by identifying anomalies with QQ-is a common technique. With interactive QQ plots, it becomes more powerful and visually appealing. Below, I attach the full code in Python:
import numpy as npfrom scipy import statsimport pandas as pdimport altair as altimport statsmodels.api as smfrom statsmodels.formula.api import ols# fit a model data = sm.datasets.get_rdataset("Duncan","carData",cache=True).datamodel =ols("prestige ~ income + education:C(type)",data=data).fit()# plot residuals against normal quantilesempirical_quantiles = model.resid.sort_values()dist = stats.norm# for ploting positions, sample extremes are 1/(n+1) and 1-1/(n+1) percentilesnobs =len(empirical_quantiles)pos = np.arange(1.,nobs+1)/(nobs +1)theoretical_quantiles = dist.ppf(pos)df = pd.DataFrame(data={'res':empirical_quantiles.values,dist.name:theoretical_quantiles,'label':empirical_quantiles.index})qqplot = alt.Chart(df).mark_point().encode(y='res',x=dist.name,tooltip='label').interactive()# the line is fit robustly based on 1st and 3rd quartileq1,q3 = stats.mstats.mquantiles(empirical_quantiles,[0.25,0.75])tq1,tq3 = dist.ppf([0.25,0.75])linex = theoretical_quantilesliney =(q3-q1)/(tq3-tq1)*(linex-tq1)+ q1qqline = alt.Chart(pd.DataFrame({'res':liney,dist.name:linex})).mark_line().encode(y='res',x=dist.name,)# combine two plotsqqplot + qqline# fit a fixed model data = sm.datasets.get_rdataset("Duncan","carData",cache=True).datamask =~data.index.isin(["minister"])model =ols("prestige ~ income + education:C(type)",data=data[mask]).fit()model.summary()
References
1.
Duncan OD. A Socioeconomic Index for All Occupations. Occupations and Social Status. 1961;(7).
Normality of data is important in statistics, so it is not a surprise that transforming data to look closer to a normal distribution can be beneficial in many ways. There are ways of finding the right transform, such as the popular Box-Cox method 1,2. In this post, I will share an elegant example on how logarithmic transforms can improve normality and consequently make statistical testing significant, effectively avoiding missing an outcome (false-negative)!
More precisely, by looking into the classical heart disease dataset 3 we will find that the cholesterol level is log-normally distributed, as suggested in the medical literature4, and using this we will prove that cholesterol level is associated with heart disease.
Here is how the data looks like:
We see that under the log-transform statistical tests no longer reject normality, and moreover that the difference between groups becomes significant!
Transform
KS Test p-val
T Test p-val
Healthy
Sick
none
0.003235
0.990000
0.05
log
0.246064
0.453206
0.03
Normality and mean-difference tests for both original and transformed data.
For completeness, here is the code snippet to reproduce:
#%pip install openmlimport matplotlib.pyplot as pltimport seaborn as snsimport openmlimport numpy as npfrom statsmodels.stats import diagnostic, weightstatsimport pandas as pdfrom IPython.display import display## get the datadataset = openml.datasets.get_dataset("Heart-Disease-Prediction")X, y, _, _ = dataset.get_data(dataset_format="dataframe")X["Heart_Disease"]= X["Heart_Disease"].apply({"Absence":False,"Presence":True}.get)sns.histplot(data=X,x="Cholesterol",hue="Heart_Disease")x0 = X['Cholesterol'][X["Heart_Disease"]==False]x1 = X['Cholesterol'][X["Heart_Disease"]==True]## investigate normalityouts =[]for fn_name, fn inzip(["none","log"],[lambdax:x,lambdax:np.log(x)]): p_norm0 = diagnostic.kstest_normal(fn(x0),dist='norm',pvalmethod='table')[1] p_norm1 = diagnostic.kstest_normal(fn(x1),dist='norm',pvalmethod='table')[1] p_ttest = weightstats.ttest_ind(fn(x0),fn(x1),usevar='unequal')[1].round(2) outs.append((fn_name, p_norm0, p_norm1, p_ttest ))outs = pd.DataFrame(data=outs,columns=[("Transform",),('KS Test p-val',"Healthy"),('KS Test p-val',"Sick"),('T Test',)])outs.columns = pd.MultiIndex.from_tuples( outs.columns )display(outs)
References
1.
Daimon T. Box–Cox Transformation. International Encyclopedia of Statistical Science. Published online 2011:176-178. doi:10.1007/978-3-642-04898-2_152
2.
Box GEP, Cox DR. An Analysis of Transformations. Journal of the Royal Statistical Society: Series B (Methodological). Published online July 1964:211-243. doi:10.1111/j.2517-6161.1964.tb00553.x
3.
Andras Janosi WS. Heart Disease. Published online 1989. doi:10.24432/C52P4X
The risk matrix, a popular risk assessment method 1, presents risks in the form of a likelihood / impact heatmap. In this post, I share a convenient and elegant Python snippet for constructing risk matrices, used to generate this hypothetical project risk assessment:
Below are the code details:
import pandas as pdimport matplotlib as mplimport matplotlib.pyplot as pltimport numpy as nplikelihod_cols =["Rare","Unlikely","Moderate","Likely","Almost certain"]impact_cols =["Insignificant","Minor","Significant","Major","Severe"]score_vals = np.arange(len(impact_cols)).reshape(-1,1)+ np.arange(len(likelihod_cols)).reshape(1,-1)cmap = mpl.colormaps["RdYlGn"].reversed().resampled(9)norm = mpl.colors.BoundaryNorm(range(10),10)fig, ax = plt.subplots(figsize=(8,8))ax.imshow(score_vals,cmap=cmap,norm=norm)annotations ={(2,3):["competition"],(3,2):["too ambitiuous"],(3,3):["hardware expertise"],(2,2):["time crunch"],(2,1):["stretched resources"],}annots_style ={'fontweight':'bold'}for(i,j),text in annotations.items(): text ='\n'.join( text ) _ = ax.text(i, j, text,ha="center",va="center",color="b",**annots_style)ax.set_xlabel('Impact',fontweight='bold')ax.set_xticks(range(len(impact_cols)),labels=impact_cols)ax.set_ylabel('Likelihood',fontweight='bold')ax.set_yticks(range(len(likelihod_cols)),labels=likelihod_cols)ax.invert_yaxis()plt.tight_layout()plt.show()fig.savefig("risk_heatmap.svg")
1.
Peace C. The risk matrix: uncertain results? Policy and Practice in Health and Safety. Published online July 3, 2017:131-144. doi:10.1080/14773996.2017.1348571
This distribution arises as passage times of random walks 1. For a survey of its basic properties, see 2. In this note we explore in detail its approximate normality, which holds when \( \lambda/\mu \to \infty\).
Consider the random variable \(X\sim \mathsf{IG}(\mu,\lambda)\) and its standardised version $$Y = \frac{X-\mathbf{E}[X]}{\sqrt{\mathbf{Var}[X]}}.$$ Below we establish normal approximation in various metrics.
Convergence in Distribution
Since the characteristic function of \(X\) is \(\phi_X(t) = e^{\frac{\lambda \left(1 – \sqrt{1 – \frac{2 i \mu^{2} t}{\lambda}}\right)}{\mu}}\), and \(\mathbf{E}[X] = \mu, \mathbf{Var}[X]=\mu^3/\lambda\), the characteristic function of the standardized distribution equals
$$ \phi_Y(t) = e^{k^{2} \cdot \left(1 – \sqrt{1 – \frac{2 i t}{k}}\right)} e^{- i k t}, $$
where \( k \triangleq \sqrt{\lambda/\mu}\). The limit under \(k\to\infty\) equals \(e^{-\frac{t^2}{2}}\), the characteristic function of the standard normal distribution, which proves convergence in distribution:
import sympy as smx, y, t, lmbd, mu, k = sm.symbols('x y t lambda mu k',positive=True)pdf = sm.Mul( sm.sqrt(lmbd/(2*sm.pi*x**3),evaluate=False), sm.exp(-lmbd*(x-mu)**2/(2*mu**2*x)),evaluate=False)mean = muvar = mu**3/lmbdnorm_pdf = sm.sqrt(var)* pdf.subs({x:y*sm.sqrt(var)+mu})norm_pdf.subs({lmbd:k**2*mu}).simplify()
and compare it to that of the standard normal distribution. Namely, we have
that is the convergence of probability densities to the standard normal distribution. By Scheffe’s Theorem 3 this proves the convergence in total variation (stronger than convergence in distribution)
We now attempt to derive concrete numerical estimates. The ratio of the characteristic function \(\phi_k\) of \(Y\) and \(\phi_{\infty}\) of the standard normal equals
$$\phi_k(t)/\phi_{\infty}(t) = e^{ k^2 h(t /k ) }, \quad h(x) \triangleq 1-\sqrt{1-2 i x}- ix + \frac{x^2}{2}.$$
Observe that \(h(x)\) expands into a convergent power series around \(x=0\) when \(|x|<\frac{1}{2}\). Thus, under the condition that \(|t| \leq \sqrt{k}\) and \(k\geq 4\), we obtain that \(|k^2 h(t /k )|\leq O(1)\), and by the bound \(|e^{z}-1| = \Theta(z)\) for \(|z|\leq O(1)\) that
We know handle the regime \(\sqrt{k} < |t| \leq k/2\). Observe that \(\Re h(x) =\Theta(1) x^4\) by the power series expansion. It follows that \(|e^{k^2 h(t /k )}| = e^{\Theta(1)}\) and therefore
By power series expansions we have, uniformly in \(k\) $$\frac{f_Y(y)}{f_{\infty}(y)} = 1-\Theta(y/k),\quad |y|\leq k^{1/3},$$ and because the expression increases in \(y\) and decreases in \(k\) when \(|y| > k^{1/3}, k>8\) (we have \(\frac{\partial}{\partial y} \frac{f_Y(y)}{f_{\infty}(y)} = \frac{k^{\frac{3}{2}} \left(- 3 k + y^{2} \cdot \left(3 k + 2 y\right) – 3 y\right) e^{\frac{y^{3}}{2 \left(k + y\right)}}}{2 \left(k + y\right)^{\frac{7}{2}}}\) and \(\frac{\partial}{\partial k} \frac{f_Y(y)}{f_{\infty}(y)} = – \frac{\sqrt{k} y \left(k y^{2} – 3 k – 3 y\right) e^{\frac{y^{3}}{2 k + 2 y}}}{2 \left(k + y\right)^{\frac{7}{2}}}\)) also $$ \frac{f_Y(y)}{f_{\infty}(y)} > 1,\quad y \geq k^{1/3},k\geq 8$$ and $$ \frac{f_Y(y)}{f_{\infty}(y)} < 1,\quad y \leq -k^{1/3},k\geq 8.$$ Therefore, we obtain $$ \int \left| f_Y(y)-f_{\infty}(y) \right| \mbox{d}y \leq O(1/k)\int_{|y|<k^{1/3}} |y| f_{\infty}(y)\mbox{d} y + \int_{t<-k^{1/3}} 2 f_{\infty}(y) = O(1/k). $$
Which proves that the convergence rate in total variation is \(O(1/k)\):
$$d_{TV}(Y;\mathsf{N}(0,1)) \leq O(1/k) = O(\sqrt{\mu/\lambda})$$ (in fact, here we obtain the matching lower bound too).
Numerical Evaluation
Numerical results match the theoretical analysis, as shown below:
For completeness, here is the script:
import numpy as npimport matplotlib.pyplot as pltfrom scipy.stats import invgauss, normfig, axs = plt.subplots(1,2,figsize=(12,4))# Part 1: evaluate total variationmus = np.linspace(0.5,0.00001,100)out =[]for mu in mus:# construct Inverse Gaussian Z =invgauss(mu=mu) mean = Z.mean() std = Z.std() k =(mean/std)**2# standardise and compare with normal Z_std =invgauss(mu=mu,loc=-mean/std,scale=1/std) Norm =norm(0,1) xs = np.linspace(-10,10,1000) metric = np.abs(Z_std.pdf(xs)- Norm.pdf(xs)).mean()*20 result =(k,metric) out.append(result)ax = axs[1]ax.plot(*zip(*out))ax.set_xscale('log')ax.set_xlabel('$\lambda / \mu$')ax.set_yscale('log')ax.set_ylabel('total-variation to normal')# Part 2: plot pdfax = axs[0]for mu in[0.2,0.1,0.05,0.01,0.0001]:# construct Inverse Gaussian Z =invgauss(mu=mu) mean = Z.mean() std = Z.std() k =(mean/std)**2# standardise and plot Z_std =invgauss(mu=mu,loc=-mean/std,scale=1/std) xs = np.linspace(-5,5,10000) ax.plot(xs,Z_std.pdf(xs),label=f'$\lambda/\mu$={k:.2f}')ax.legend(title="standardised distribution")ax.set_xlabel('$x$')ax.set_ylabel('pdf')plt.tight_layout()plt.show()
Folks JL, Chhikara RS. The Inverse Gaussian Distribution and its Statistical Application—A Review. Journal of the Royal Statistical Society: Series B (Methodological). Published online July 1978:263-275. doi:10.1111/j.2517-6161.1978.tb01039.x
3.
Scheffe H. A Useful Convergence Theorem for Probability Distributions. Ann Math Statist. Published online September 1947:434-438. doi:10.1214/aoms/1177730390
4.
Bobkov SG. Proximity of probability distributions in terms of Fourier-Stieltjes transforms. Russ Math Surv. Published online December 31, 2016:1021-1079. doi:10.1070/rm9749