0
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Do variables have weight, or does somehow number of variables have weight? If it is the second case -- how does it affect the result? $\endgroup$
    – Tim
    Commented Nov 4, 2016 at 14:57
  • $\begingroup$ 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? $\endgroup$
    – Mark Johnson
    Commented Nov 4, 2016 at 15:02
  • 1
    $\begingroup$ 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 ?? $\endgroup$
    – StijnDeVuyst
    Commented Nov 4, 2016 at 15:02
  • $\begingroup$ @StijnDeVuyst I ran the calcs with a typo; fixed now. Thanks. $\endgroup$
    – Mark Johnson
    Commented Nov 4, 2016 at 15:05

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Mark Johnson
    Commented Nov 4, 2016 at 15:48
  • 1
    $\begingroup$ 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. stats.stackexchange.com/questions/41247 and 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. $\endgroup$
    – whuber ♦
    Commented Nov 4, 2016 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.