# Confidence interval for sum of random subsequence generated by coin tossing

This question is related to Sum of random subsequence generated by coin tossing. Here is the corresponding problem description as given by Memming:

Let $(\pi_1, \pi_2, \cdots)$ be an infinite sequence of real numbers such that $\forall i\; \pi_i > 0$ and $\sum_i \pi_i = 1$. This can be thought of as a probability over natural numbers.

Let $(z_1, z_2, \ldots)$ be a sequence of independently and identically distributed Bernoulli random variables such that $P(z_i = 1) = p$ and $P(z_i = 0) = (1-p)$.

What can we say about the distribution of $X = \sum_i \pi_i z_i$?

$X$ is the sum of a random subsequence of $(\pi_i)$ generated by coin tossing.

Since $E[X] = p$, $X$ can be used to get an estimation for $p$. Given the sequence $\pi_i$, how does the corresponding confidence interval look like? I am especially interested in the case, where $\pi_i$ is a geometric sequence $\pi_i := (1-\rho) \rho^{i-1}$.

Edit: More precisely, I would like to know a method to calculate the optimal (smallest) confidence interval. The corresponding lower and upper bounds are functions of the given sequence $(\pi_1, \pi_2, \cdots)$, $L_\alpha=L_\alpha(\pi_1, \pi_2, \cdots)$ and $U_\alpha=U_\alpha(\pi_1, \pi_2, \cdots)$, respectively, which fulfill $P(X<L_\alpha)=P(X>U_\alpha)\leq\frac{\alpha}{2}$ for given confidence level $\alpha$. I would also be satisfied with an efficient numerical procedure.

Edit: Changed ...how do the corresponding confidence intervals look like? to ...how does the corresponding confidence interval look like? to make this question more clearly.

• The Edit modified drastically the question... The new version roughly asks for the full distribution of $X$. This is not computable theoretically in full generality. Hence one can rely on Monte Carlo simulations to generate a sample of size $n$ and decide that $L_{\alpha}$ is the $\alpha/2$-empirical quantile (and similarly for $U_\alpha$). To check whether $L_\alpha\leqslant x$ for some given $x$, one needs only to decide if each sample $X$ is $\leqslant x$ or not. To do that, a finite (random) number of $z_i$s suffices. – Did Jan 7 '13 at 10:26
• Do not understand me wrong, I appreciate your answer below (although my reputation is still too low to rate it as useful). It is the best I have so far. I agree that a general solution might not exist. However, there may be a better solution for the special case $\pi_i = (1-\rho) \rho^{i-1}$. At least for another special case ($\pi_i=\frac{1}{n}$ if $i\leq n$ and $\pi_i=0$ else) there exists a better one: Since $n X$ is binomial, an optimal confidence interval can be constructed easily and calculated using numerical means. – otmar Jan 7 '13 at 12:04
• I understand quite well the situation--and I fully disagree with the way you managed this question, which reflects, either a lack of reflexion about what you really wanted to ask when you posted the question, or a lack of consideration for the answerers, or both. – Did Jan 7 '13 at 12:13
• I am sorry for your inconvenience, this is my first question here. I think the formulation of the question was somewhat misleading due to a small typo. See edit. – otmar Jan 7 '13 at 12:46
• See edit... Sorry, but no. – Did Jan 7 '13 at 12:47

Since $\mathbb E(X)=p$ and $\mathrm{var}(X)=p(1-p)\vartheta$ with $\vartheta=\sum\limits_i\pi_i^2$, iterating $n$ times the experience and denoting by $S_n$ the sum of these $n$ results yields $S_n$ of mean $np$ and variance $np(1-p)\vartheta$. Thus, $$Z_n=\frac{S_n-np}{\sqrt{np(1-p)\vartheta}}\longrightarrow Z,$$ where $Z$ is standard normal. Hence $$\mathbb P\left(\left|p-\frac{S_n}n\right|\geqslant\frac{z_\alpha}{n\sqrt{n}}\sqrt{S_n(n-S_n)\vartheta}\right)\longrightarrow\mathbb P(|Z|\geqslant z_\alpha)=2(1-\Phi(z_\alpha)).$$ If $\pi_i=\rho(1-\rho)^{i-1}$, then $\vartheta=\dfrac{\rho}{2-\rho}$.
Edit: Nonasymptotic bounds are that, for every $z\gt0$ and every $n\geqslant1$, $$\mathbb P(|Z_n|\geqslant z)\leqslant\frac1{z^2}.$$ In other words, considering the domain $$D_{n,z}(s)=\{u\in[0,1]\mid (s-nu)^2\leqslant nzu(1-u)\vartheta\},$$ one gets $$\mathbb P(p\in D_{n,z}(S_n))\geqslant1-\frac1{z^2}.$$ Note that if $S_n/n\approx p$, $D_{n,z}(S_n)$ is approximately the interval $$\left[p-\frac{z}{n\sqrt{n}}\sqrt{S_n(n-S_n)\vartheta};p+\frac{z}{n\sqrt{n}}\sqrt{S_n(n-S_n)\vartheta}\right],$$ hence the loss in the apparent quality of the approximation this surplus of rigor entails is mainly to replace the asymptotic upper bound $2(1-\Phi(z))$ by $1/z^2$.
• Assume $\pi_i = \frac{1}{N}$ for $i\leq N$ and $\pi_i = 0$ else. Then $X$ corresponds to a binomial distribution, for which the standard normal approximation is justified for $\max(Np,N(1-p))\gg 1$. Therefore, due to similar reasons, I doubt that your approximation works well for the geometric sequence, if for example $\rho=0.5$ and $p=0.9$. I would like to know a method, which allows an accurate and efficient numerical evaluation of such confidence intervals for any $\rho$ and $p$. – otmar Jan 7 '13 at 8:39
• See Edit.   – Did Jan 7 '13 at 9:03