0

I'm attempting to implement a numerical approximation to assess the frequency of outcomes given $N$ independent random variables. There is a slight twist however, each $N$ has a weight,

Each variable has the form:

$f_n=\{probability, weight\}$

I'm having difficulty confirming what the result should be. Here's an example.

$f_1=\{0.6,7\}$

$f_2=\{0.5, 4\}$

$f_3=\{0.4, 5\}$

My objective is to calculate the probability of each permutation's sum of weights; so given 3 functions, there are 8 permutations:

Sum of Weights: Likelihood
0: 12.03%
4: 11.98%
5: 8.02%
7: 17.98%
9: 8.04%
11: 18%
12: 12.02%
16: 11.93%

Are these outcomes correct? Maybe there is a closed solution that doesn't require monte carlo methods?

Mark Johnson
  • 137
  • 1
  • 5
  • Do *variables* have weight, or does somehow *number of variables* have weight? If it is the second case -- how does it affect the result? – Tim Nov 04 '16 at 14:57
  • If an event occurs, the outcome is assigned the weight. If the event does not occur, the outcome is assigned 0. I'm not sure I'm explaining it adequately. Suppose you're drawing plastic eggs that contain money from $N$ baskets. Some eggs have money, some eggs don't. The money would be the weight. So after drawing a single egg from each $N$ basket, how much money do you have? – Mark Johnson Nov 04 '16 at 15:02
  • 1
    The example doesn't seem to make much sense. For example, the probability of having a sum of 16 should be 0.6*0.5*0.4=0.12 and not 14.43 ?? – StijnDeVuyst Nov 04 '16 at 15:02
  • @StijnDeVuyst I ran the calcs with a typo; fixed now. Thanks. – Mark Johnson Nov 04 '16 at 15:05

1 Answers1

0

This is conceptually very easy, but maybe a little harder in practice. Let $B_i$, $i=1,\ldots,N$ be independent Bernoulli variables: $\text{Prob}[B_i=1]=p_i$ and $\text{Prob}[B_i=0]=1-p_i$, independently from the other variables. If $B_i=1$, a reward $w_i$ is given. The total reward is: $$ R = \sum_{i=1}^N w_i B_i\,. $$ The expected reward is therefore: $$ \text{E}[R] = \sum_{i=1}^N w_i \text{E}[B_i] = \sum_{i=1}^N w_i p_i\,. $$ In general there is no attractive analytical formula for the probability mass function of $R$ however, except perhaps: $$ \text{Prob}[R=m] = \sum_{i_1=0}^1 \cdots \sum_{i_N=0}^1 \mathbf{1}(\sum_{i=1}^Nw_i=m) \prod_{j=1}^N p_j^{i_j}(1-p_j)^{1-i_j}\,, $$ where $\mathbf{1}(A)$ is 1 if $A$ is true and 0 otherwise. What this means in practice is that you have to test all $2^N$ possible events and check the sum of weights.

StijnDeVuyst
  • 2,161
  • 11
  • 17
  • Thanks! You've augmented my conceptual understanding. If you have access to something like mathematica, could you generate, if its easy, a possible outcome for $N=10$ by seeding random events and weights? Having a value I could check my implementation against would be super helpful. – Mark Johnson Nov 04 '16 at 15:48
  • 1
    If the "weights" are all integral and lie within relatively small bounds, you do not have to do this by brute force: use a convolution instead. http://stats.stackexchange.com/questions/41247 and http://stats.stackexchange.com/questions/5347 are readily generalized. As a small example, expanding the product $$(.4+.6 x^7)(.5+.5 x^4)(.6+.4x^5)\\=0.12+0.12 x^4+0.08 x^5+0.18 x^7+0.08 x^9+0.18 x^{11}+ 0.12x^{12}+0.12x^{16}$$ is a convolution, performed in time proportional to $17 \log(17)$, from which one can read off the exact answers corresponding to the approximate values given in the question. – whuber Nov 04 '16 at 17:34