# Poisson binomial distribution-like problem

Given n trials, where, on each trial, you have a given probability of either winning or losing a set amount of money (with both the amount of money and the probability changing for each trial)- what is your probability of walking away ahead or at least breaking even?

Edit: From reading Wikipedia, it looks like it might be approached by determining the cumulative distribution function from either the characteristic function or the probability generating function - but I am having a hard time working out how to do so exactly.

• Binomial distribution assumes that each trial is an independent event. If P(win) is changing with the the trial, it's not binomial. Also, where is the poisson part? Please provide more detail if possible. – Ujjwal Kumar Jan 16 '17 at 14:08
• @UjjwalKumar - that's what the Poisson Binomial distribution is, one where you are faced with a possibly different probability at each Bernoulli draw. Its name comes from Poisson himself, not from any relationship to the Poisson distribution we are most familiar with. – jbowman Jan 16 '17 at 17:55
• Since the chances and payoffs potentially vary with each trial, there cannot in general be any simpler answer than one obtained by computing and combining all $2^n$ possible outcomes. What, then, do you mean by "working out how to do so exactly"? – whuber Jan 16 '17 at 22:56
• As it depends on $n$ and each of the individual $p_i$, I doubt there is a closed form formula for this. It may be easiest to fix $n$ and then calculate $P(k = \frac{n}{2})$. – Avraham Jan 16 '17 at 22:56

Suppose we play $n$ times, and the reward (or loss) of the $k$th play is $r_k$, and the probability we win the $k$th play is $p_k$.
Define $\mathcal{A}$ as the set of all break-even (or better) events: $$\mathcal{A} = \left\{A : \sum_{i \in A} r_i \ge \sum_{j \in A^c} r_j\right\}$$ Each element of $\mathcal{A}$ can be thought of as a set of indices corresponding to the 'wins' in a trial where we win at least as much as we lose.
The probability you are asking for is the probability any of the independent events in $\mathcal{A}$ happens, which is $$\mathbb{P}(\mathcal{A}) = \sum_{A \in \mathcal{A}} \prod_{i \in A} p_i \prod_{j \in A^c}(1-p_j)$$ which, on the surface, looks a lot like the Poisson Binomial distribution. A key difference is that, given the information you provided, we don't know an easy way to enumerate the sets in $\mathcal{A}$ without iterating through each of the $2^n$ options. If you have some more information about the problem which leads to an easy way to characterize $\mathcal{A}$, then I think you'll have a viable path forward to computing $\mathbb{P}(\mathcal{A})$ (at least if $\lvert \mathcal{A}\rvert$ is small).
For a simple example, if all $r_k$ and all $p_k$ are equal, then this is a sum over the upper half of the binomial probability mass function: $$\mathbb{P}(\mathcal{A}) = \sum_{k=\lceil n/2\rceil}^n \binom{n}{k} p^k (1-p)^{n-k}$$ Even this case is challenging numerically if $n$ is large, due to the binomial coefficient.