#StackBounty: #asymptotics #big-o-notation Big O notation for Average case in Linear search

Bounty: 50

Average case complexity for linear search is (n+1)/2 i.e, half the size of input n.

The average case efficiency of an algorithm can be obtained by finding the average number of comparisons as given below:

Minimum number of comparisons = 1

Maximum number of comparisons = n

If the element not found then maximum number of comparison = n

Therefore, average number of comparisons = (n + 1)/2

Hence the average case efficiency will be expressed as O (n).(I’ve seen this in many websites…)

Here, how can we say it as O(n) in big O notation or terminology. It should be O(n/2), I suppose. Kindly clarify me


Get this bounty!!!

#StackBounty: #asymptotics #iid #delta-method Does a version of the Delta Method exist for non-i.i.d. sequences?

Bounty: 150

I have a sequence of random variables that are non-independent, but usually identically distributed. I am wondering if a version of the Delta Method exists under the case when I only have that the data is identically distributed. If so, would there also be cases where it may hold when the sequence is neither independent nor identically distributed? Thanks.


Get this bounty!!!

#StackBounty: #time-series #stochastic-processes #stationarity #asymptotics #moving-average Is the MA($infty$) process with i.i.d. noi…

Bounty: 100

I have a MA($infty$) process defined by
$$
X_t = sum_{k=0}^infty alpha_{k} epsilon_{t-k}, qquad tinmathbb{Z}
$$

where the sums converge a.s. and the $epsilon_t$ are i.i.d. centered noise with Var($epsilon_t$) = $sigma^2< infty$.

There are plenty of proofs that this process is weakly stationary in the literature.

Is this process strictly stationary?


Get this bounty!!!

#StackBounty: #least-squares #asymptotics #average Asymptotic dist of an average involving OLS coefs?

Bounty: 50

Suppose that we have iid sample of size $n$. i.e., the random vector $(Y_{i}, X_{1i}, X_{2i}, X_{3i})$ is iid from $1,ldots,n$. And suppose the following relationship is true:

$$
Y_i = beta_0 + beta_1X_{1i} + beta_2X_{2i} + beta_3X_{1i}X_{2i} + epsilon_i
$$

Suppose for simplicity that $X_{1i}$ and $X_{2i}$ are uniformly distributed from 0 to 1, and are correlated. Let’s assume further that $epsilon_i$ is normally distributed and independent of $X_{1i}$ and $X_{2i}$.

Let the OLS estimators be $hat{beta}_0, hat{beta}_1, hat{beta}_2$.

Let $Z_i$ be

$$
Z_i = 1hat{beta}_0 + 2X_{1i}hat{beta}_1 + 3X_{2i}hat{beta}_2 + 4hat{beta}3*X{1i}*X_{2i}
$$

How do I find the asymptotic distribution of $bar{Z}=frac{1}{n}sum_{i=1}^n Z_i$?

I cannot apply a CLT since the $Z_i$ are correlated with each other because of the $hat{beta}$. In addition to solving this particular case, any reference to theory I can study related to this would be helpful. I do not have an advanced statistical theory knowledge.

I would like to derive a non-degenerate asymptotic distribution, i.e., something like $sqrt{n}(bar{Z} – E(Z_i))$.


Get this bounty!!!

#StackBounty: #mathematical-statistics #confidence-interval #maximum-likelihood #asymptotics How can I obtain an asymptotic $1-alpha$ …

Bounty: 50

Let $X sim Gamma(alpha,1)$ and $Y|X=x sim Exp(frac{1}{theta x}), alpha >1$ and $theta >0$ are unknown. Let $tau=E(Y)$. Suppose that based on the random sample $Y_1,…,Y_n$, we have MLEs, $hat{alpha}$ and $hat{theta}$. Use these MLEs to develop an asymptotic $1-alpha$ confidence interval for $tau$.

my work:

First, I need to find $tau=E(Y)=E(frac{1}{theta x})=frac{1}{theta}E(frac{1}{x})$. We use a transformation of $T=frac{1}{X}$, where $f_T(t)=frac{1}{Gamma(alpha)t^{alpha+1}}e^{-1/t},t>0$. However, I am having trouble evaluating $E(T)=int^infty_0frac{1}{Gamma(alpha)t^{alpha}}e^{-1/t}dt$.

Assuming we have $tau$, we can get the asymptotic $1-alpha$ CI by using the asymptotic property of MLE. We know that $hat{alpha}sim AN(alpha,frac{1}{ni(alpha)})$ and $hat{theta} sim AN(theta,frac{1}{ni(theta)})$. However, I am failing to see how I can obtain the asymptotic CI for $tau$.


Get this bounty!!!

#StackBounty: #regression #pca #asymptotics Is high dimensional PCA regression consistent?

Bounty: 50

Consider a set $(y_i, x_i), i=1ldots,n$. The OLS estimator, which is a $sqrt{n}$-consistent estimator of $beta$ is obtained as $$hatbeta=(X^tX)^{-1}X^ty$$.

Now perform a PCA on the matrix $Xinmathbb{R}^{ntimes p}, n>p$. Consider the matrix of principal components $Qinmathbb{R}^{ptimes p}$ defined in a way such that the first principal component has the largest possible variance, and each succeeding component has the largest possible variance under the constraint that it is orthogonal to the preceding components. From an algebra perpective, Q is the matrix of eigenvectors from X and define an orthogonal change of basis maximizing the variance from X.

Consider $Z=XQinmathbb{R}^{ntimes p}$, the projection of $X$ into the subspace generated by $Q$ and solve,

$$tilde{beta}=(Z^tZ)^{-1}Z^ty$$.

It is trivial to see that $$hat{beta}=Qtildebeta$$ is the OLS estimator, and thus it is oracle. Now my question is: what happens when $p>n$?, this is, when we are in a high dimensional framework in which the OLS estimator cannot be solved. We can still perform a PCA and obtain a matrix Q of principal components that will in this case be equal to $$Qinmathbb{R}^{ptimes n}$$ meaning that in order to explain $100%$ of the original variability we will require $n$ PCs. $$hat{beta}=Qtildebeta$$

This $hatbeta$ will not be the OLS estimator in the high dimensional framework, but is it still $sqrt{n}$-consistent?


Get this bounty!!!

#StackBounty: #variance #monte-carlo #asymptotics #central-limit-theorem How are the variance of an estimate to $int_Bf:{rm }dmu$ a…

Bounty: 50

Let $(E,mathcal E,mu)$ be a probability space, $(X_n){ninmathbb N_0}$ be an $(E,mathcal E)$-valued ergodic time-homogeneous Markov chain with stationary distribution $mu$ and $$A_nf:=frac1nsum{i=0}^{n-1}f(X_i);;;text{for }finmathcal L^1(mu)text{ and }ninmathbb N.$$ Suppose we’re estimating an integral $$mu f=int f:{rm d}mu$$ for some $finmathcal L^1(mu)$ and that $$sqrt n(A_nf-mu f)xrightarrow{ntoinfty}mathcal N(0,sigma^2(f))tag1$$ with $$sigma^2(f)=lim_{ntoinfty}noperatorname{Var}[A_nf].$$

Assume that the support $B:={fne0}$ is “small”, but $mu(B)>0$. Now let $$f_B:=1_Bleft(f-frac{mu(1_Bf)}{mu(B)}right).$$ Instead of $sigma^2(f)$ we could consider $sigma^2(f_B)$ which, by definition, should tell us something about the deviation of $f=1_Bf$ from its mean.

If our concern is the minimization of the asymptotic variance of our estimation of $mu f$, does it make sense to consider $sigma^2(f_B)$ instead of $sigma^2(f)$? How are $sigma^2(f_B)$ and $sigma^2(f)$ related?

Background:

My actual concern is that I need to estimate $lambda(hf)$ for a variety of $mathcal E$-measurable $h:Eto[0,infty)$, where $lambda$ is a reference measure on $(E,mathcal E)$ so that $mu$ has a density $p$ with respect to $lambda$ and ${p=0}subseteq{f=0}$. Now the support $E_0:={p>0}cap{h>0}$ is very “small” and you may assume that $h=1_{{:h:>:0:}}$. I want to estimate $lambda(hf)$ using the importance sampling estimator.

Say $(X_n){ninmathbb N_0}$ is the chain generated by the Metropolis-Hastings algorithm with target distribution $mu$, $(Y_n){ninmathbb N}$ is the corresponding proposal sequence and $Z_n:=(X_{n-1},Y_n)$ for $ninmathbb N$. If the proposal kernel is denoted by $Q$, we know that $(Z_n)_{ninmathbb N}$ has stationary distribution $nu:=muotimes Q$.

Now, in light of the special form of the to be estimated integral $lambda(hf)$, I thought it might be tempting to consider the Markov chain corresponding to the successive times of its returns to the set $Etimes E_0$. To be precise, let $tau_0:=0$ and $$tau_k:=infleft{n>tau_{k-1}:Y_nin E_0right};;;text{for }kinmathbb N.$$ Assuming that $Etimes E_0$ is a recurrent set for $(Z_n)_{ninmathbb N}$, we know that $left(Z_{tau_k}right)_{kinmathbb N}$ is again an ergodic time-homogeneous Markov chain with stationary distribution $$nu_0:=frac{left.nuright|_{Etimes E_0}}{nu(Etimes E_0)}.$$

I wondered whether it makes sense to build an estimator using $left(Z_{tau_k}right){kinmathbb N}$ instead of $(Z_n){ninmathbb N}$ or if this would gain nothing.


Get this bounty!!!

#StackBounty: #variance #monte-carlo #asymptotics #central-limit-theorem How are the variance of an estimate to $int_Bf:{rm }dmu$ a…

Bounty: 50

Let $(E,mathcal E,mu)$ be a probability space, $(X_n){ninmathbb N_0}$ be an $(E,mathcal E)$-valued stationary time-homogeneous Markov chain with initial distribution and $$A_nf:=frac1nsum{i=0}^{n-1}f(X_i);;;text{for }finmathcal L^1(mu)text{ and }ninmathbb N.$$ Suppose we’re estimating an integral $$mu f=int f:{rm d}mu$$ for some $finmathcal L^1(mu)$ and that $$sqrt n(A_nf-mu f)xrightarrow{ntoinfty}mathcal N(0,sigma^2(f))tag1$$ with $$sigma^2(f)=lim_{ntoinfty}noperatorname{Var}[A_nf].$$

Assume that the support $B:={fne0}$ is “small”, but $mu(B)>0$. Now let $$f_B:=1_Bleft(f-frac{mu(1_Bf)}{mu(B)}right).$$ Instead of $sigma^2(f)$ we could consider $sigma^2(f_B)$ which, by definition, should tell us something about the deviation of $f=1_Bf$ from its mean.

If our concern is the minimization of the asymptotic variance of our estimation of $mu f$, does it make sense to consider $sigma^2(f_B)$ instead of $sigma^2(f)$? How are $sigma^2(f_B)$ and $sigma^2(f)$ related?


Get this bounty!!!

#StackBounty: #variance #monte-carlo #asymptotics #central-limit-theorem How are the variance of an estimate to $int_Bf:{rm }dmu$ a…

Bounty: 50

Let $(E,mathcal E,mu)$ be a probability space, $(X_n){ninmathbb N_0}$ be an $(E,mathcal E)$-valued stationary time-homogeneous Markov chain with initial distribution and $$A_nf:=frac1nsum{i=0}^{n-1}f(X_i);;;text{for }finmathcal L^1(mu)text{ and }ninmathbb N.$$ Suppose we’re estimating an integral $$mu f=int f:{rm d}mu$$ for some $finmathcal L^1(mu)$ and that $$sqrt n(A_nf-mu f)xrightarrow{ntoinfty}mathcal N(0,sigma^2(f))tag1$$ with $$sigma^2(f)=lim_{ntoinfty}noperatorname{Var}[A_nf].$$

Assume that the support $B:={fne0}$ is “small”, but $mu(B)>0$. Now let $$f_B:=1_Bleft(f-frac{mu(1_Bf)}{mu(B)}right).$$ Instead of $sigma^2(f)$ we could consider $sigma^2(f_B)$ which, by definition, should tell us something about the deviation of $f=1_Bf$ from its mean.

If our concern is the minimization of the asymptotic variance of our estimation of $mu f$, does it make sense to consider $sigma^2(f_B)$ instead of $sigma^2(f)$? How are $sigma^2(f_B)$ and $sigma^2(f)$ related?


Get this bounty!!!

#StackBounty: #variance #monte-carlo #asymptotics #central-limit-theorem How are the variance of an estimate to $int_Bf:{rm }dmu$ a…

Bounty: 50

Let $(E,mathcal E,mu)$ be a probability space, $(X_n){ninmathbb N_0}$ be an $(E,mathcal E)$-valued stationary time-homogeneous Markov chain with initial distribution and $$A_nf:=frac1nsum{i=0}^{n-1}f(X_i);;;text{for }finmathcal L^1(mu)text{ and }ninmathbb N.$$ Suppose we’re estimating an integral $$mu f=int f:{rm d}mu$$ for some $finmathcal L^1(mu)$ and that $$sqrt n(A_nf-mu f)xrightarrow{ntoinfty}mathcal N(0,sigma^2(f))tag1$$ with $$sigma^2(f)=lim_{ntoinfty}noperatorname{Var}[A_nf].$$

Assume that the support $B:={fne0}$ is “small”, but $mu(B)>0$. Now let $$f_B:=1_Bleft(f-frac{mu(1_Bf)}{mu(B)}right).$$ Instead of $sigma^2(f)$ we could consider $sigma^2(f_B)$ which, by definition, should tell us something about the deviation of $f=1_Bf$ from its mean.

If our concern is the minimization of the asymptotic variance of our estimation of $mu f$, does it make sense to consider $sigma^2(f_B)$ instead of $sigma^2(f)$? How are $sigma^2(f_B)$ and $sigma^2(f)$ related?


Get this bounty!!!