# Distribution of $\sum_k \alpha^k X_k$

Let $(X_k)$ be a sequence of independent Bernoulli random variables, such that $\Pr[X_k = 1] = p$. Then for $0\le\alpha<1$ the sum $$\sum_{k=0}^\infty \alpha^k X_k$$ is real random variable in the range $[0, 1/(1-\alpha)]$.

Does this variable follow a well-known distribution? I have tried to calculate it's characteristic function and moments, but I can't quite figure out how to approach it.

• math.stackexchange.com/questions/2570573 seems related, but it only considers the case $p = \alpha = 1/2$ which appears easier. Commented May 8, 2018 at 19:28
• If $\alpha < 1/2$, the sum has a singular continuous distribution, supported on a generalized Cantor set. Commented May 8, 2018 at 19:31
• @RobertIsrael Right, it probably makes sense to restrict to the case $\alpha>1/2$. For $\alpha\to1$ it appears we get convergence to a normal (perhaps binomial) distribution. Commented May 8, 2018 at 19:44
• What convergence? As $\alpha \to 1-$ with $p$ fixed, the sum goes to $\infty$ almost surely. Commented May 8, 2018 at 20:04
• @RobertIsrael right, I guess you need the right normalization. Looking at it again, it is actually obvious, since the mgf (as you wrote in your answer) becomes $(1-p+p e^t)^n$ when $\alpha\to 1$ (if you limit the sum at $n$) which is exactly the mgf for a binomial distribution. Commented May 8, 2018 at 20:11

The moment generating function of a sum of independent random variables is the product of the mgf's of the summands. Thus in your case

$$M(t) = \prod_{k=0}^\infty \mathbb E[\exp(t X_k)] = \prod_{k=0}^\infty \left(1 + p (e^{t \alpha^k}-1)\right)$$ I don't think this has a closed form in general.

• Right, I guess what I meant to say was that I was looking to make a Laplace transformation of the mgf (or a Chernoff bound) in order to find the tail probabilities. In this case I need to solve an equation on $M'(t)$ which seems hard. Commented May 8, 2018 at 20:09
• One option is to use the power means inequality to pull $\alpha^k$ out of the expectation. Then we get $M(t)\le (pe^t+1-p)^{1/(1-\alpha)}$. It seems we might be able to also lower bound $(pe^{t\alpha}+1-p)\ge (pe^{t}+1-p)^{f(\alpha,p)}$, that is uniformely in $t$, but I don't know how to get the best value for $f$. Commented May 13, 2018 at 13:01

I got a bit closer to an answer myself.

Consider \begin{align} EX^n &= E\left(\sum_k \alpha^k X_k\right)^n \\&= \sum_{k_1,\dots,k_n}\alpha^{k_1+\dots+k_n}E(X_{k_1}\cdots X_{k_n}) \\& = \sum_{P\in\text{partitions(n)}}{n\choose P}p^{|P|}\sum_{k_1,\dots,k_{|P|}}\alpha^{P_1k_1+\dots P_{|P|}k_{|P|}}[\forall_{i,j}k_i \neq k_j] \\& \le \sum_{P\in\text{partitions(n)}}{n\choose P}p^{|P|} \prod_{s\in P}\frac{1}{1-\alpha^s}, \end{align} where partitions($$n$$) is the integer partitions of $$n$$, e.g. partitions($$5$$) = $$\{\{5\},\{4,1\},\{3,2\},\{3,1,1\},\{2,2,1\},\{2,1,1,1\},\{1,1,1,1,1\}\}$$. We let $${n\choose P} = {n\choose P_1, \dots, P_{|P|}}$$ be the number of ways a particular partition can appear.

Now we know from Ramanujan that $$|\text{partitions}(n)| \sim \exp(\pi\sqrt{2n/3})$$. Hence, if we only want to know $$EX^n$$ up to exponential terms, it suffices to find the largest element of the (all positive) sum. We may guess that the largest partitions are those where all elements of $$P$$ are the same, hence we consider for $$n=sm$$:

\begin{align} \log\left({n\choose \underbrace{s, \dots, s}_{\text{m times}}}p^m\left(\frac1{1-\alpha^s}\right)^m\right) &= \left(n\log\frac ns+o(n)\right)+m\log p+m\log\frac{1}{1-\alpha^s} \\&= n\left(\log\frac ns+o(1)+\frac1s\log\frac{p}{1-\alpha^s}\right). \end{align}

This is decreasing in $$s$$, so it suggests the bound $$\log EX^n\le n\log\frac{np}{1-\alpha}+o(n)$$. It may be that this upper bound is too lose to get an equivalent (up polynomial terms) lower bound and that we need to not throw away the $$[\forall_{i,j}k_i\neq k_j]$$ condition.

Update: Using this result of Hitczenko: $$\|\sum a_i X_i\|_n\sim\sum_{i\le p}a_i + \sqrt{n}\sqrt{\sum_{i>n}a_i^2}$$, we can find $$\|X\|_n = (EX^n)^{1/n}$$ up to a constant:

$$\|X\|_n \sim \sum_{1\le i\le n}\alpha^{i-1} + \sqrt{n}\sqrt{\sum_{i > n}\alpha^{2i-1}} = \frac{1-\alpha^n}{1-\alpha} + \sqrt{n}\frac{\alpha^n}{\sqrt{1-\alpha^2}}.$$

This is for $$p=1/2$$ of course.

For $$p\neq 1/2$$ we might use the biased Khintchine inequalities by Wolff and Oleszkiewi to show:

\begin{align} \|X\|_n &\le \sqrt{\frac{q^{2-2/n}-p^{2-2/n}}{p^{1-2/n}q-q^{1-2/n}p}}\frac1{\sqrt{1-\alpha^2}} \\&\sim\begin{cases} \sqrt{\frac{p^{2/n}}{p\,(1-\alpha^2)}} & \text{if}\quad \frac1{n-1}\le\log\frac1p\\ \sqrt{\frac{(n-1)\,p\log1/p}{1-\alpha^2}} & \text{if}\quad \frac1{n-1} >\log\frac1p \end{cases} \end{align}

where $$q=1-p$$. However, this isn't necessarily tight.

Note the previous suggested bound was $$\|X\|_n\le\frac{np}{1-\alpha}+o(1)$$ which is mostly less than the hypercontractive bound. Presumably, the right answer is somewhere in between.

Perhaps a generalized (in the sense of Hitczenko) biased Khintchine is needed to solve this problem.