3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ math.stackexchange.com/questions/2570573 seems related, but it only considers the case $p = \alpha = 1/2$ which appears easier. $\endgroup$ Commented May 8, 2018 at 19:28
  • 1
    $\begingroup$ If $\alpha < 1/2$, the sum has a singular continuous distribution, supported on a generalized Cantor set. $\endgroup$ Commented May 8, 2018 at 19:31
  • $\begingroup$ @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. $\endgroup$ Commented May 8, 2018 at 19:44
  • $\begingroup$ What convergence? As $\alpha \to 1-$ with $p$ fixed, the sum goes to $\infty$ almost surely. $\endgroup$ Commented May 8, 2018 at 20:04
  • 1
    $\begingroup$ @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. $\endgroup$ Commented May 8, 2018 at 20:11

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Commented May 8, 2018 at 20:09
  • $\begingroup$ 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$. $\endgroup$ Commented May 13, 2018 at 13:01
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .