0

Let $\left\{X_{{1}}, X_{{2}}, \ldots, X_{k}\right\}$ denotes Bernoulli random variables with $\quad\left[p_{1}, p_{2}, \ldots, p_{k}\right]$ as respective parameters. Let

$S=a_1X_{{1}}+a_2X_{{2}}+\ldots+a_kX_{k}$.

where $a_i > 0$ and $a_i \neq 0, \forall i \in {1,2,\ldots,k}$

Note that all $p_i$ values are closer to $0$ (but not equal to) and they are different. Moreover, $k$ is not too large to invoke asymptotic approximations or not too small.

What are some suitable weights $a_i$'s such that the distribution of $S$ has a closed form?

Note that the trivial solution of $a_i=constant$ is not useful for me. Some possibility of weights I could consider are as follows:

  1. $a_i=i \implies S=X_{{1}}+2X_{{2}}+\ldots+kX_{k}$ . Does the distribution of S have a closed form in this case.?
  2. $a_i =q^{i-1} \implies S=X_{{1}}+q^1X_{{2}}+\ldots+q^{k-1 }X_{k}$ . This has geometric weights.
  3. $a_i=1/i \implies S=X_{{1}}+(1/2)X_{{2}}+\ldots+(1/k)X_{k}$

I am flexible with choosing any weight sets as long as they are all positives and unique.

wanderer
  • 61
  • If $0 \leq q \leq 1/2 $, the geometric weight one is uniform on some set of rational numbers. (it can be represented in base n (if q is 1/n for some integer n). In particular, if q = 1/2, you can show that that sum converges to a uniform distribution in [0,2]. – E-A Jan 01 '20 at 16:45
  • @E-A, Could you elaborate this? I am ok with $0<q\leq0.5$. I am not able to understand how the sum converges to $U~[0,2]$, when $q$ is 1/2. Also, if the number of random variables (k) is not too large to invoke asymptotic approximations, does it hold. – wanderer Jan 01 '20 at 18:14
  • We can quite explicitly write the distribution of

    $$ S_k = \frac{1}{2} X_1 + (\frac{1}{2})^2 X_2 + ... + (\frac{1}{2})^k X_k $$

    through it probability mass function, which puts weight $(\frac{1}{2})^k$ on $\frac{j}{2^k}$ for all $j \in {0, ..., 2^k - 1}$.

     – E-A Jan 01 '20 at 19:11
  • @E-A , It seems wrong to me. $S_1=\frac{1}{2}X_{1}$ is not uniform as $X_1$ is bernoulli with probability $p_1$. Are you assuming $k\rightarrow \infty$? (I have finite k) – wanderer Jan 01 '20 at 19:22
  • Yeah, the asymptotic was for k tending to infinity. Also just realized that the first case can be partially done counting partitions with distinct parts, but I don't know enough number theory to do it. – E-A Jan 01 '20 at 19:30
  • 1
    The $p_i$'s are arbitrary, so even asymptotically in the $q=1/2$ case we don't end up with uniform, since each bit in the binary representation is $1$ with a different probability. In fact, I'd say the case of $a_i = $constant is not trivial at all. It has a name though, Poisson Binomial Distribution, according to this – antkam Jan 06 '20 at 23:38
  • @antkam, Yes. you are right. Even when all the weights are unity, it is not having a closed-form distribution. I was hoping if there exists a nicer set of weights where I could have a closed-form. – wanderer Jan 07 '20 at 19:13
  • 1
    If you have arbitrary $p_i$ given by an adversary, then, for all practical purposes, the answer, most likely, is "there is no way to get a closed form for the distribution under any useful meaning of the notion of "closed form", though the formal proof of that may be difficult and requires a long discussion of and agreement on some "meta-mathematical" definitions. So I would rather ask why you want closed form at all, i.e., what exactly you are going to achieve with it. – fedja Jan 10 '20 at 18:20
  • @fedja, say, if I am okay with having my weights as a function of $p_i$, do you think it is still intractable? – wanderer Jan 11 '20 at 21:17
  • As requested, yes, because even describing the exact support of the resulting probability measure is a nightmare unless there is some arithmetic relation between the weights, forget the distribution. – fedja Jan 11 '20 at 21:21

0 Answers0