<jupyter_start><jupyter_text>Empirical growth testing The [time](https://en.wikipedia.org/wiki/Time_complexity) and [computational](https://en.wikipedia.org/wiki/Computational_complexity) complexity are critical fields of algorithms research since birth of computer science. However in modern world where applications are more and more often implemented as sets of communicating services (or processes) without hard guarantees the message delivery time direct analysis becomes problematic. But since hardware or software update can change behaviour of whole system, the need to estimate scalability of the new solution is still present. In this document I show methods I have created to: - Phase 1: find out which of implementations showing signs of bad scalability(exponetial growth) - Phase 2: compare implementations with the polynomial scalability (find degree of polynomial)based on regular empirical sample we can get from a standard testing.In the phase 1 we we assume null hypothesis that the growth is not at least exponential, if we are able to reject it algorithm is not interesting for us. Else we go to the phase 2 where we try to estimate if the growth is polynomial and what is the degree of the polynomial (useful for comparison to other algorithms). We assume that a checked algorithm needs for resources grows monotically with the amount of data we are processing. In the case the measure errors break this assumption you can use [isotonic regression](https://en.wikipedia.org/wiki/Isotonic_regression) to create good values.  Best wishes  <NAME><jupyter_code>import numpy as np
import sympy as sp
import scipy as sc
from scipy import optimize
from sympy import limit, sin, Symbol, oo
sp.init_printing(use_latex='mathjax')<jupyter_output><empty_output><jupyter_text>Phase 1: Exponetial growth testing We know that we know that f is monotonicly growing function, so we can present it as $f(x)=e^{g(x)}$. Which gives: \begin{equation}\nonumber\ln(f(x))=\ln(e^{g(x)})=g(x)\end{equation} The f is monotonicly growing function, so $\forall_{x>0} g(x) > 1$. If the growth of $g$ is constant or increasing then $f$ grows exponetially or faster. So we can present the growth as derivatives: \begin{equation}\tag{1}\frac{d}{dx}\ln(f(x))=\frac{d}{dx}(\ln(e^{g(x)}))=\frac{d}{dx}g(x)\end{equation} Since $g$ is growing: \begin{equation}\nonumber \frac{d}{dx}g(x)\geq 0\end{equation} If $\frac{d}{dx}g(x)$ goes to $\infty$ the $f$ grows exponentially or more. Lets assume that $\exists l>0$ so: \begin{equation}\tag{2}\lim_{x\to \infty}\frac{d}{dx}g(x)=l\end{equation} We can give $h(x)= l\cdot x - k$ with $k$ big enough, so $\forall_{x>0}\ h(x) \leq g(x)$. Since $e^{h(x)}$ grows at least exponetially, so $f$ does. So if $\frac{d}{dx}g(x)$ goes towards limit higher than $0$ it means the $f$ grows at least exponentially. We can also point out that if $g(x)=ln(x^n)$ then: \begin{equation}\nonumber f(x)=e^{ln(x^n)}=e^{n\cdot ln(x)}=x^n\end{equation} It means $f$ has at most polynomial growth if g(x) if $g$ has at most logarithmic growth. We can use sympy(or other CAS) to estimate cooefficients in above considerations. Lets assume exponetially growing $f$ has form: \begin{equation}\nonumber f(x)=b\cdot e^{c\cdot (x^s)}+d\end{equation}<jupyter_code>a,b,c,d,s,x = sp.symbols('a b c d s x')
SymF = b**(c*(x**s))+d
SymF<jupyter_output><empty_output><jupyter_text>And \begin{equation}\nonumber g(x)=\log_a({f(x)})\end{equation}<jupyter_code>SymG = sp.log(SymF,a)
SymG 
DSymG = sp.diff(SymG,x)
DSymG
try:
    sp.limit(DSymG, x, oo)
except Exception as inst:
    print(inst.__context__)<jupyter_output>Result depends on the sign of sign(s)<jupyter_text>We can assume that all the values are positive and the $b$ is bigger than $0$. Lets check $s=1$:<jupyter_code>a,b,c,d,s,x = sp.symbols('a b c d s x', positive=True)
SymF = (b+1)**(c*(x**(1)))+d
SymG = sp.log(SymF,a)
DSymG = sp.diff(SymG,x)
DSymG
sp.limit(DSymG, x, oo)<jupyter_output><empty_output><jupyter_text>We can try to estimate how fast the function aproaches limit:<jupyter_code>p = sp.symbols('p', positive=True)
DSymGP = DSymG.subs((b+1)**(c*x),p)
sp.apart(DSymGP,p).subs(p,(b+1)**(c*x))<jupyter_output><empty_output><jupyter_text>It looks with exponetial acceleration. We get form of the constant $l$ above $0$. Lets check $s>1$:<jupyter_code>a,b,c,d,s,x = sp.symbols('a b c d s x', positive=True)
SymF = (b+1)**(c*(x**(1+s)))+d
SymG = sp.log(SymF,a)
DSymG = sp.diff(SymG,x)
DSymG
sp.limit(DSymG, x, oo)<jupyter_output><empty_output><jupyter_text>For $s\in [0,1)$ we should get to $0$.<jupyter_code>a,b,c,d,s,x = sp.symbols('a b c d s x', positive=True)
SymF = (b+1)**(c*(x**(s/(1+s))))+d
SymG = sp.log(SymF,a)
DSymG = sp.diff(SymG,x)
DSymG
sp.limit(DSymG, x, oo)
p = sp.symbols('p', positive=True)
DSymGP = DSymG.subs((b+1)**(c*(x**(s/(s+1)))),p)
sp.apart(DSymGP,p).subs(p,(b+1)**(c*(x**(s/(s+1)))))<jupyter_output><empty_output><jupyter_text>The first part is going to zero at least with exponetial acceleration, the second with $x^{\frac{s-1}{s+1}}=x^{-2}$ quadratic acceleration.   How to test: We test a hypothesis that $f$ has at least exponetial growth. To check if the $f(x)$ grows we check behaviour of the $\frac{d}{dx}g(x)$. If it does not go to $0$ with at least $\mathcal(\frac{a}{x}+const)$ acceleration then we have that the $f$ is an exponetially growing function.  1. We start with calculating $\frac{d}{dx}g(x)$:  - We compute derivate based on the stencil method [link](http://web.media.mit.edu/~crtaylor/calculator.html)I have chosen locations of sampled points equal to 0,1,2,3,4,5 since I do not want use negative locations with limited data.<jupyter_code>def df_1(f,h):
    f = np.float64(f)
    h = np.float64(h)
    df = lambda f, h:((-137*f[0]+300*f[1]-300*f[2]+200*f[3]-75*f[4]+12*f[5])/(60*1.0*h))
    return [df(f[j:j+6], 1) for j in range(0,f.size-6)]<jupyter_output><empty_output><jupyter_text>- We then use logarithm identity to estimate $\frac{d}{dx}g(x)$: \begin{equation}\nonumber\frac{d}{dx}g(x)=\frac{d}{dx}(\ln(f(x)))\end{equation}<jupyter_code>def d_g(f,h):
    return df_1(np.log(f),h)<jupyter_output><empty_output><jupyter_text>2. We make statistical tests to check if the $\frac{d}{dx}g(x)$ has all necessary properties:  - We calculate [Spearman rank coefficient](https://en.wikipedia.org/wiki/Spearman%27s_rank_correlation_coefficient) to check if it is monotonically decreasing, otherwise we can assume $f$ is growing at least exponentially.  - We test for existence of unit root with [KPSS test](https://en.wikipedia.org/wiki/KPSS_test) and [Augmented Dickey Fuller test](https://en.wikipedia.org/wiki/Augmented_Dickey%E2%80%93Fuller_test), if there is no unit root and the $\frac{d}{dx}g(x)$ is stationary around value significantly bigger than zero, we can assume $f$ is growing at least exponentially. - We do curve fitting for $a_0\cdot x +b+0$, $\frac{a_1}{x}+b_1$ and $\frac{a_2}{x^2}+b_2$ check p-values of ordinary regressions. If the p-value of the first is smaller than the others, there is something fishy. 3. If all test went through we cannot reject the hypothesis.  Phase 2: Polynomial growth testing We can assume $a\cdot x^n = f(x)=e^{g(x)}$. So \begin{equation}\nonumber g(x)=n\cdot \ln(x)+\ln(a)\end{equation} We try to find $n$:  1. We try do curve fitting for $g(x)$, we get estimated $n$ parameter, we should check p-values of ordinary regression.        We can try two aproaches from [wiki](https://en.wikipedia.org/wiki/Degree_of_a_polynomial)    \begin{equation}\nonumber \deg\ f = \lim_{x\to\infty}\frac{log\lvert f(x)\rvert}{log(x)} = \lim_{x\to\infty}\frac{g(x)}{log(x)} \end{equation}        \begin{equation}\nonumber \deg\ f = \lim_{x\to\infty}\frac{x\cdot \frac{d}{dx}f(x)}{f(x)} \end{equation}  2. We compute the $n$th and $(n+1)$th derivate of $f$ based on the stencil method [link](http://web.media.mit.edu/~crtaylor/calculator.html)  3. Check with [KPSS test](https://en.wikipedia.org/wiki/KPSS_test) and/or [Augmented Dickey Fuller test](https://en.wikipedia.org/wiki/Augmented_Dickey%E2%80%93Fuller_test) if \begin{equation}\nonumber\frac{d^{n+1}}{dx^{n+1}}f(x)\equiv 0\end{equation}  - If not try to divide  $(n+1)$th by $n$th derivate and check if it is close to $0$, it should be since it is $\frac{0}{const}$.  - Also execute polynomial regression and check if the residuals confim the findings. Alternative: We can try use [Stolz–Cesàro theorem](https://en.wikipedia.org/wiki/Stolz%E2%80%93Ces%C3%A0ro_theorem) to estimate limit. $$\lim_{x\to\infty}\frac{1}{x}=0$$ so $$\lim_{x\to\infty}\frac{1}{\frac{1}{x}}=\infty$$  and is monotonic. Lets try reach $$\lim_{x\to\infty}\frac{\frac{1}{\frac{dg}{dx}(x)}}{x^n}$$ for $n > 0$ This is tricky alternative since Stolz–Cesàro theorem assumes that we differentiate strongly growing function. It is the case for the first iteration, but later Spearman rank coefficient test has to be applied every step and isotonic regression in case some strange outliners.  Examples for exponetial growth testing:<jupyter_code>import statsmodels.tsa.stattools as stat
import statsmodels.api as sm
import scipy.stats as sps
import matplotlib.pyplot as plt
#%matplotlib inline<jupyter_output><empty_output><jupyter_text>Example: $2^x+1$<jupyter_code>Exponential = np.asarray([np.power(2,x)+1 for x in range(50)])
dg = np.transpose(d_g(Exponential,100))
X = range(dg.size)
X = sm.add_constant(X)
dg<jupyter_output><empty_output><jupyter_text>Quite clearly the series going asymptoticly to value in $[0,1]$.<jupyter_code>sps.spearmanr(range(dg.size),dg)<jupyter_output><empty_output><jupyter_text>The first value is correlation rank. Since it is more than $0$ the hypothesis is that the function is monoticaly growing.The second value is p-value. p-value numerically equals $0$, so the hypothesis is valid. So $f$ grows at least exponetially. It is not necessary, we will go through the second point.<jupyter_code>Result = stat.kpss(dg, regression='c')
(R_scr,pvalue) = Result[0:2]
(R_scr,pvalue) 
Result = stat.adfuller(dg, maxlag=None, regression='c', autolag='AIC')
(R_scr,pvalue) = Result[0:2]
(R_scr,pvalue)<jupyter_output><empty_output><jupyter_text>With Augmented Dickey Fuller test we reject (p-value $= 0$) thesis that there is an unit root. KPSS doesn't allow us to reject a thesis that the $\frac{d}{dx}g(x)$ is not stationary (big R-score, p-value over $5\%$). The series stabilizes around value significally bigger than $0$. So $f$ grows at least exponetially.  Example: $e^x+1$<jupyter_code>Exponential_2  = np.asarray([np.exp(x)+1 for x in range(50)])
dg = np.transpose(d_g(Exponential_2,100))
X = range(dg.size)
X = sm.add_constant(X)
dg
sps.spearmanr(range(dg.size),dg)<jupyter_output><empty_output><jupyter_text>The same situation as in the [example above](2toN). So $f$ grows at least exponetially.<jupyter_code>Result = stat.kpss(dg, regression='c')
(R_scr,pvalue) = Result[0:2]
(R_scr,pvalue) 
Result = stat.adfuller(dg, maxlag=None, regression='c', autolag='AIC')
(R_scr,pvalue) = Result[0:2]
(R_scr,pvalue)<jupyter_output><empty_output><jupyter_text>Actually we cannot reject or accept thesis about stationarity of the series, even if we can see that it stabilizes around $1$. Lets check linear regresion then:<jupyter_code>model = sm.OLS(dg,X)
results = model.fit()
results.params
slope, intercept, r_value, p_value, std_err = sps.linregress(range(dg.size),dg)
slope, intercept, r_value, p_value<jupyter_output><empty_output><jupyter_text>We can see that slope is minimal and above $0$, intercept close to $1$ and the p-value is way below $0.05$. So $f$ grows at least exponetially. NOTE: Negative slope would be indicator that there is posibility of a smaller growth, but with spearman rank positive it should not happen.  Example: $4x^2+1$<jupyter_code>Polynomial_2   = np.asarray([4*np.power(x,2)+1 for x in range(50)])
dg = np.transpose(d_g(Polynomial_2,100))
X = range(dg.size)
X = sm.add_constant(X)
dg
sps.spearmanr(range(dg.size),dg)<jupyter_output><empty_output><jupyter_text>We have low p-value so it is a monotonic series. The correlation is negative, so series is decreasing.<jupyter_code>Result = stat.kpss(dg, regression='c')
(R_scr,pvalue) = Result[0:2]
(R_scr,pvalue) 
Result = stat.adfuller(dg, maxlag=None, regression='c', autolag='AIC')
(R_scr,pvalue) = Result[0:2]
(R_scr,pvalue)<jupyter_output><empty_output><jupyter_text>The tests suggest that values of the function are stationary. (The final values are already close to $0$, but this is not exactly valid argument since changes in coefficients could streach values of the last value without changing $\mathcal{O}$ )<jupyter_code>model = sm.OLS(dg,X)
results = model.fit()
results.params
slope, intercept, r_value, p_value, std_err = sps.linregress(np.array(range(dg.size))+0.0001,dg)
slope, intercept, r_value, p_value<jupyter_output><empty_output><jupyter_text>Negative slope with low p-value, suggest we should reject hypothesis that $f$ is at least exponetial. Let try to estimate the highest power of the polynomial.<jupyter_code>g = np.transpose(np.log(Polynomial_2))
X = range(g.size)
X = sm.add_constant(X)
g
Polynomial_2   = np.asarray([4*np.power(x,2)+1 for x in range(50)])
def log_func(X,n,a):
    return n * np.log(X) + a
def exp_func(x, n, ln_a):
    return np.power(x,n) * np.exp(ln_a)
slope, intercept, r_value, p_value, std_err = \
    sps.linregress(np.log(np.array(range(g.size))+1.1),g)
params=slope, intercept
slope, intercept, r_value, p_value<jupyter_output><empty_output><jupyter_text>Double check with algorithm from the [wolfram mathworld](http://mathworld.wolfram.com/LeastSquaresFittingLogarithmic.html).<jupyter_code>def log_linregress(X,Y):
    n =  Y.size
    logX = np.log(X)
    num_b = n*(logX.dot(Y))- np.sum(logX) * np.sum(Y)
    den_b = n*np.sum(np.power(logX,2))-(np.power(np.sum(logX),2))
    slope = np.divide(num_b,den_b)
    intercept = np.divide((np.sum(Y) - slope * np.sum(logX)),n)
    return slope,intercept

log_linregress(np.array(range(g.size))+1.1,g)
plt.figure(figsize=(8, 4))
plt.scatter(np.array(range(g.size))+1.1, g, label='g')
plt.plot(np.array(range(g.size))+1.1, log_func(np.array(range(g.size))+1.1, params[0], params[1]),
         label='Fitted function g')
plt.legend(loc='best')
plt.show()
plt.figure(figsize=(8, 4))
plt.scatter(np.array(range(g.size))+1.1, np.transpose(Polynomial_2), label='f')
plt.plot(np.array(range(g.size))+1.1, exp_func(np.array(range(g.size))+1.1, params[0], params[1]),
         label='Fitted function f')
plt.legend(loc='best')
plt.show()<jupyter_output><empty_output><jupyter_text>In the $f$ picture we can already see that we should check if the function grows exponetially, since in later values the exponetial function starts to grow much faster.  We compute the $2$nd and $3$rd derivate of $f$ based on the stencil method [link](http://web.media.mit.edu/~crtaylor/calculator.html)<jupyter_code>def df_2(f,h):
    f = np.float64(f)
    h = np.float64(h)
    df = lambda f, h:((45*f[0]-154*f[1]+214*f[2]-156*f[3]+61*f[4]-10*f[5])/(12*1.0*np.power(h,2)))
    return [df(f[j:j+6], 1) for j in range(0,f.size-6)]

df_2(Polynomial_2,100)
def df_3(f,h):
    f = np.float64(f)
    h = np.float64(h)
    df = lambda f, h:((-17*f[0]+71*f[1]-118*f[2]+98*f[3]-41*f[4]+7*f[5])/(4*1.0*np.power(h,3)))
    return [df(f[j:j+6], 1) for j in range(0,f.size-6)]
df_3(Polynomial_2,100)<jupyter_output><empty_output><jupyter_text>$\mathcal{O}(x^2)$ confirmed.  Example: $x^{9}+1$<jupyter_code>Polynomial_12  = np.asarray([np.power(x,9)+1 for x in range(50)])
dg = np.transpose(d_g(Polynomial_12,100))
X = range(dg.size)
X = sm.add_constant(X)
dg
sps.spearmanr(range(dg.size),dg)<jupyter_output><empty_output><jupyter_text>We have low p-value so it is a monotonic series. The correlation is negative, so the series is decreasing.<jupyter_code>Result = stat.kpss(dg, regression='c')
(R_scr,pvalue) = Result[0:2]
(R_scr,pvalue) 
Result = stat.adfuller(dg, maxlag=None, regression='c', autolag='AIC')
(R_scr,pvalue) = Result[0:2]
(R_scr,pvalue)<jupyter_output><empty_output><jupyter_text>The tests suggest that values of the function are stationary. (The final values are already close to $0$, but this is not exactly valid argument since changes in coefficients could streach values of the last value without changing $\mathcal{O}$ )<jupyter_code>model = sm.OLS(dg,X)
results = model.fit()
results.params
slope, intercept, r_value, p_value, std_err = sps.linregress(np.array(range(dg.size))+0.0001,dg)
slope, intercept, r_value, p_value<jupyter_output><empty_output><jupyter_text>Negative slope with low p-value, suggest we cannot reject hypothesis that $f$ is not at least exponetial. We will try to show that it is polynomial. Let try to estimate the highest power of the polynomial.<jupyter_code>g = np.transpose(np.log(Polynomial_12))
X = range(g.size)
X = sm.add_constant(X)
g
slope, intercept, r_value, p_value, std_err = \
    sps.linregress(np.log(np.array(range(g.size))+1.1),g)
params=slope, intercept
slope, intercept, r_value, p_value
log_linregress(np.array(range(g.size))+1.1,g)
plt.figure(figsize=(8, 4))
plt.scatter(np.array(range(g.size))+1.1, g, label='g')
plt.plot(np.array(range(g.size))+1.1, log_func(np.array(range(g.size))+1.1, params[0], params[1]),
         label='Fitted function g')
plt.legend(loc='best')
plt.show()
plt.figure(figsize=(8, 4))
plt.scatter(np.array(range(g.size))+1.1, np.transpose(Polynomial_12), label='f')
plt.plot(np.array(range(g.size))+1.1, exp_func(np.array(range(g.size))+1.1, params[0], params[1]),
         label='Fitted function f')

plt.legend(loc='best')
plt.show()<jupyter_output><empty_output><jupyter_text>We compute the $9$th and $10$th derivate of $f$ based on the stencil method [link](http://web.media.mit.edu/~crtaylor/calculator.html)<jupyter_code>def df_9(f,h):
    f = np.float64(f)
    h = np.float64(h)
    df = lambda f, h:(-1*f[0]+9*f[1]-36*f[2]+84*f[3]-126*f[4]+126*f[5]-84*f[6]+36*f[7]-9*f[8]+1*f[9])/(1*1.0*np.power(h,9))
    return [df(f[j:j+10], 1) for j in range(0,f.size-10)]

df9 = np.array(df_9(Polynomial_12,100))
df9
plt.figure(figsize=(8, 4))
plt.scatter(np.array(range(df9.size))+0.1, df9, label='f')
plt.plot(np.array(range(df9.size))+0.1, np.array(np.repeat(np.mean(df9),df9.size)),
         label='Fitted function f')

plt.legend(loc='best')
plt.show()
def df_10(f,h):
    f = np.float64(f)
    h = np.float64(h)
    df = lambda f, h: \
    (1*f[0]-10*f[1]+45*f[2]-120*f[3]+210*f[4]-252*f[5]+210*f[6]-120*f[7]+45*f[8]-10*f[9]+1*f[10])\
    /(1*1.0*np.power(h,10))
    return [df(f[j:j+11], 1) for j in range(0,f.size-11)]

df10 = np.array(df_10(Polynomial_12,100))
df10
sc.stats.ttest_1samp(df10, 0)<jupyter_output><empty_output><jupyter_text>Quite interesting average doesn't pass a t-test for the mean of $0$. But when we compare $10$th and $9$th derivate we will get conclusion.<jupyter_code>np.linalg.norm(np.divide(df10,df9[:-1]))<jupyter_output><empty_output><jupyter_text>NOTE: The assumption that we deal with growing function and polynomial is important here. In that case we know that $10$th derivative is $0$, $9$th is constant and $8$th is linear with significant slope (if slope is not significant then $9$th will be close to $0$). We can just go for polynomial regression and check residuals.<jupyter_code>(coef, residuals, rank, singular_values, rcond) = \
np.polyfit(np.array(range(g.size))+1.1, np.transpose(Polynomial_12), 8, full=True)
residuals
(coef, residuals, rank, singular_values, rcond) = \
np.polyfit(np.array(range(g.size))+1.1, np.transpose(Polynomial_12), 10, full=True)
residuals
(coef, residuals, rank, singular_values, rcond) = \
np.polyfit(np.array(range(g.size))+1.1, np.transpose(Polynomial_12), 9, full=True)
residuals
plt.figure(figsize=(8, 4))
plt.scatter(np.array(range(g.size))+1.1, np.transpose(Polynomial_12), label='f')
plt.plot(np.array(range(g.size))+1.1, np.polyval(coef, np.array(range(g.size))+1.1),
         label='Fitted function f')

plt.legend(loc='best')
plt.show()<jupyter_output><empty_output><jupyter_text>So polynomial with degree $9$ fits not much worse than with degree $10$, but degree $8$ is not enough. Two time the same conclusion, should be ok.  Lets try add a little errors, since we obviously will get them in a product environment.  Example: $e^x+1$ with added error<jupyter_code>Exponential_2 = np.asarray([np.exp(x)+1 for x in range(50)])
Exponential_2 = Exponential_2 + 0.05 * np.random.normal(size=Exponential_2.size)
dg = np.transpose(d_g(Exponential_2,100))
X = range(dg.size)
X = sm.add_constant(X)
dg

sps.spearmanr(range(dg.size),dg)<jupyter_output><empty_output><jupyter_text>The same situation as in the example [without error](eXplus1). So $f$ grows at least exponetially.<jupyter_code>Result = stat.kpss(dg, regression='c')
(R_scr,pvalue) = Result[0:2]
(R_scr,pvalue) 
Result = stat.adfuller(dg, maxlag=None, regression='c', autolag='AIC')
(R_scr,pvalue) = Result[0:2]
(R_scr,pvalue)<jupyter_output><empty_output><jupyter_text>What is very interesting, for me adding normal errors made augmented Dickey–Fuller test to work. We can now state that the series is stationary. Lets check linear regresion then, we want to know intercept:<jupyter_code>model = sm.OLS(dg,X)
results = model.fit()
results.params
slope, intercept, r_value, p_value, std_err = sps.linregress(range(dg.size),dg)
slope, intercept, r_value, p_value<jupyter_output><empty_output><jupyter_text>Intercept above $0$, the p-value is way below $0.05$. So $f$ grows at least exponetially.  Example: $x^{9}+1$ with added error<jupyter_code>Polynomial_12  = np.asarray([np.power(x,9)+1 for x in range(50)])
Polynomial_12 = Polynomial_12 + 0.05 * np.random.normal(size=Polynomial_12.size)
dg = np.transpose(d_g(Polynomial_12,100))
X = range(dg.size)
X = sm.add_constant(X)
dg
sps.spearmanr(range(dg.size),dg)<jupyter_output><empty_output><jupyter_text>As in not error [case](highPoly). We have low p-value so it is a monotonic series. The correlation is negative, so series is decreasing.<jupyter_code>import warnings
warnings.filterwarnings('ignore')
Result = stat.kpss(dg, regression='c')
warnings.filterwarnings('always')     

(R_scr,pvalue) = Result[0:2]
(R_scr,pvalue) 
Result = stat.adfuller(dg, maxlag=None, regression='c', autolag='AIC')
(R_scr,pvalue) = Result[0:2]
(R_scr,pvalue)<jupyter_output><empty_output><jupyter_text>Hard to get conclusions here, p-value changes from run to run for me.<jupyter_code>model = sm.OLS(dg,X)
results = model.fit()
results.params
slope, intercept, r_value, p_value, std_err = sps.linregress(np.array(range(dg.size))+0.0001,dg)
slope, intercept, r_value, p_value<jupyter_output><empty_output><jupyter_text>Negative slope with low p-value (not always). We cannot reject hypothesis that growth $f$ is not at least exponetial anyway. We will try to show that it is polynomial. Let try to estimate the highest power of the polynomial.<jupyter_code>g = np.transpose(np.log(Polynomial_12))
X = range(g.size)
X = sm.add_constant(X)
g
slope, intercept, r_value, p_value, std_err = \
    sps.linregress(np.log(np.array(range(g.size))+1.1),g)
params=slope, intercept
slope, intercept, r_value, p_value
log_linregress(np.array(range(g.size))+1.1,g)
plt.figure(figsize=(8, 4))
plt.scatter(np.array(range(g.size))+1.1, g, label='g')
plt.plot(np.array(range(g.size))+1.1, log_func(np.array(range(g.size))+1.1, params[0], params[1]),
         label='Fitted function g')
plt.legend(loc='best')
plt.show()
plt.figure(figsize=(8, 4))
plt.scatter(np.array(range(g.size))+1.1, np.transpose(Polynomial_12), label='f')
plt.plot(np.array(range(g.size))+1.1, exp_func(np.array(range(g.size))+1.1, params[0], params[1]),
         label='Fitted function f')
plt.legend(loc='best')
plt.show()<jupyter_output><empty_output><jupyter_text>We compute the $9$th and $10$th derivate of $f$ based on the stencil method [link](http://web.media.mit.edu/~crtaylor/calculator.html)<jupyter_code>df9 = np.array(df_9(Polynomial_12,100))
df9
plt.figure(figsize=(8, 4))
plt.scatter(np.array(range(df9.size))+0.1, df9, label='f')
plt.plot(np.array(range(df9.size))+0.1, np.array(np.repeat(np.mean(df9),df9.size)),
         label='Fitted function f')
plt.legend(loc='best')
plt.show()
def df_10(f,h):
    f = np.float64(f)
    h = np.float64(h)
    df = lambda f, h: \
    (1*f[0]-10*f[1]+45*f[2]-120*f[3]+210*f[4]-252*f[5]+210*f[6]-120*f[7]+45*f[8]-10*f[9]+1*f[10])\
    /(1*1.0*np.power(h,10))
    return [df(f[j:j+11], 1) for j in range(0,f.size-11)]

df10 = np.array(df_10(Polynomial_12,100))
df10
sc.stats.ttest_1samp(df10, 0)<jupyter_output><empty_output><jupyter_text>Higher variance help statistical tests to get conclusions about the mean. Still it is not significant. But when we compare $10$th and $9$th derivate we will get conclusion.<jupyter_code>np.linalg.norm(np.divide(df10,df9[:-1]))<jupyter_output><empty_output><jupyter_text>Do the polynomial regression and check residuals.<jupyter_code>(coef, residuals, rank, singular_values, rcond) = \
np.polyfit(np.array(range(g.size))+1.1, np.transpose(Polynomial_12), 8, full=True)
residuals
(coef, residuals, rank, singular_values, rcond) = \
np.polyfit(np.array(range(g.size))+1.1, np.transpose(Polynomial_12), 10, full=True)
residuals
(coef, residuals, rank, singular_values, rcond) = \
np.polyfit(np.array(range(g.size))+1.1, np.transpose(Polynomial_12), 9, full=True)
residuals
plt.figure(figsize=(8, 4))
plt.scatter(np.array(range(g.size))+1.1, np.transpose(Polynomial_12), label='f')
plt.plot(np.array(range(g.size))+1.1, np.polyval(coef, np.array(range(g.size))+1.1),
         label='Fitted function f')

plt.legend(loc='best')
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.15873511614288502, 'fraction_numerical': 0.028772203786843645, 'mean_word_length': 5.863879957127546, 'pattern_counts': {'":': 0, '<': 157, '<?xml version=': 0, '>': 163, 'https://': 10, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '39', 'dir': 'jupyter-structured-clean-dedup', 'id': '231159', 'license': 'Apache-2.0', 'n_tokens_mistral': 10279, 'n_tokens_neox': 9682, 'n_words': 2407, 'path': 'Empirical_growth_testing.ipynb', 'repo_name': 'flmath/empirical-growth-testing', 'size': '25622'}