Binominal Probability Distribution with varying input size I would like to create a formula for a distribution problem. Lets say I have a data structure that tells me whether or not an element has been inserted into it. This data structure has a false positive probability of 0.3. If we do 1000 tests with each 1000 elements that have not been inserted into the data structure we get a binominal distribution with a mean of 300. E.g. for each of the 1000 tests we test for 1000 elements how many of them are present in the data structure. Since none are actually present we only get the false positive distribution which in this case is equal to the Binominal distribution for n=1000 and p=0.3.
Now for my problem say I have 1 test with 1000 elements. But now we do not know how many of the elements are contained in the data structure. So the result might be "800 elements are contained in the data structure". Now we do know that some of these elements are most likely false positives since we still have a false positive rate of 0.3.
I would like to plot a probability distribution for the possible outcomes of the above example. E.g. 
probability that 800 are false positives, 
and 0 elements are actually present: 0.00002
...
probability that 200 are false positives, 
and 600 elements are actually present: 0.1012
...
probability that 100 are false positives, 
and 700 elements are actually present: 0.0043    
...
probability that 0 are false positives, 
and 800 elements are actually present: 0.000043

What function describes this distribution?
 A: So I think there are two cases to consider: the first in which you know the probability that an element is in the data structure, and the second in which this is unknown.
First some notation, lete $X_i \in \{0,1\}$ denote the event that point $i$ is in the structure, and let $Y_i \in \{0,1\}$ denote the observed outcome of whether or not $i$ is in the structure.
Based on your comment above, I will assume that false negatives do not occur: so that if $X_i = 1$, then $Y_i = 1$, but in addition if $X_i = 0$ there is a false positive rate $q$ ($=0.3$ in your example) that $Y_i = 1$. Let $N$ denote the total number if points ($=1000$).
I will assume that each $X_i$ is independent, and since it is $\{0,1\}$ valued, it follows a Binomial distribution, with probability $p \in [0,1]$:
$$P(X_i = 1) = p, \qquad i = 1,\ldots, N.$$
If we also introduce independent variables $Z_i \sim \text{Unif}[0,1]$, then we can write
$$
Y_i = \begin{cases}
1 & \text{if $X_i = 1$, or $Z_i < q$,}\\
0 & \text{else.}
\end{cases}
$$
Again, the variable $Y_i$ must be Bernoulli distributed (since it has support $\{0,1\}$), and simple calculations using condition probabilities show:
\begin{align*}
P(Y_i = 1) & = p + (1-p)q \\
P(X_i = 1 \, | \, Y_i = 1) & = \frac{p}{p + (1-p)q}
\end{align*}
In particular we note that the condition distribution $(X_i = \cdot \, | \, Y_i = 1)$ is Bernoulli distributed:
$$(X_i = \cdot \, | \, Y_i = 1) \sim \text{Ber}\left( \frac{p}{p + (1-p)q} \right)
$$
Since sums of Bernoulli distributions are Binomially distributed, we have:
\begin{align*}
\sum_{i = 1}^n (X_i = \cdot \, | \, Y_i = 1) & \sim \text{Bin}\left(n, \frac{p}{p + (1-p)q} \right). 
\end{align*}
However, we also have:
\begin{align*}
\left( \sum_{i=1}^N X_i = \cdot \, \Bigg|  \sum_{i=1}^N Y_i = n \right) & \sim \sum_{i = 1}^n (X_i = \cdot \, | \, Y_i = 1) \\ & \sim \text{Bin}\left(n, \frac{p}{p + (1-p)q} \right). 
\end{align*}
So in particular if $\sum_{i=1}^N Y_i = n$ ($=800$ in your example) then
\begin{align*}P \left( \sum_{i=1}^N X_i = m \, \Bigg|  \sum_{i=1}^N Y_i = n \right) &=
\binom{n}{m} \left(\frac{p}{p + (1-p)q}\right)^m \left( \frac{(1-p)q}{p +(1-p)q}\right)^{n-m} \\
& =
\binom{n}{m} \frac{p^m(1-p)^{n-m} q^{n-m} }{\big(p + (1-p)q\big)^n} \\
\end{align*}
As I understand it, this is the solution you are after assuming that you know the true positive rate $p$.
However, suppose this is not known. In this case, we can find an estimate for $p$. To see this, we note that since $Y_i \sim \text{Ber}\big( p + (1-p)q \big)$ (as this is the probability that $Y_i = 1$), then
$$ \sum_{i=1}^N Y_i \sim \text{Bin}\big( N, p + (1-p)q \big)$$
In general if we observe a $\text{Bin}(N, \theta)$ to take the value $n$, and we do not know $\theta$, then the (maximum likelihood) estimate for $\theta$ is $\hat \theta = n/N$.
So in our example:
$$\hat \theta = \frac{n}{N} = \hat p + \big( 1 - \hat p\big) q$$
Rearranging for $\hat p$, our estimate for $p$, we have
$$\hat p = \frac{ \frac{n}{N} - q}{1 - q}$$
Note that if $ \frac{n}{N} < q$, that is if the observed number of successes is lower than the false positive rate, then $\hat p < 0$. As such we would approximate instead that $\hat p = 0$ (though in practice this special case is unlikely to occur), so we would set:
$$\hat p =\max \left ( 0, \frac{ \frac{n}{N} - q}{1 - q} \right)$$
This can now be substituted into the formula in the first part, to get an approximation to the probability of interest:
\begin{align*}
P \left( \sum_{i=1}^N X_i = m \, \Bigg|  \sum_{i=1}^N Y_i = n \right) & \approx
\binom{n}{m} \frac{\hat p^m(1-\hat p)^{n-m} q^{n-m} }{\big(\hat p + (1-\hat p)q\big)^n} \\
& =
\begin{cases}
{\bf 1}(m=0), \quad \text{if $\frac{n}{N} <q$,}\\
\binom{n}{m} \left(\frac{N}{n}\right)^n \left(\frac{1}{1-q}\right)^n \left( \frac{n}{N} - q \right)^m \left(1 - \frac{n}{N}\right)^{n-m}q^{n-m}, \quad \text{else.} \end{cases}
\end{align*}
where the first case is the situation that $\hat p = 0$, in which case we approximate $\sum_{i=1}^N = 0$. We use $\approx$ to denote that this is the estimate using the maximum likelihood estimator $\hat p$.
A: In this answer I am responding to the answer of @eclipse, from 28/12/2017.
In my previous answer I had assumed that the number of true positives is understood to be random: as the question was phrased as finding (for instance): "probability that 200 are false positives, 
and 600 elements are actually present". This prompted a model in which the $X_i$ are considered random (same notation as previously), in which case they must be Bernoulli, and under the assumption of independence, implies that $\sum_{i=1}^N X_i$ must be Binomial.
If instead, we want to consider a scenario in which there are not a random number, but simply an unknown fixed number, then we need to be more careful in asking the question: "What is the probability distribution of this unknown number?". This takes us into the differing perspectives of frequentest vs Bayesian thinking.
In the following I provide a discussion of both methods, and how they relate to the answers given to date.
Using the notation adopted in my previous answers; let us suppose that there is some fixed parameter $\theta \in \{0,\ldots, N\}$ which describes the number of true positives: so that $\sum_{i=1}^N X_i = \theta$.
Frequentist approach.
A frequentist would not be willing to assign a probability distribution to $\theta$; they would say there is no randomness describing this value: we  just don't know what value $\theta$ is!
A frequentist statistician would therefore give you their best guess of what $\theta$ is equal to, based on the information they have at hand.
To assess this, one calculates the likelihood of the observations (in our case the total number, $n$, of positives: true and false) for a range of values of $\theta$, and then picks the value $\theta^*$ which maximizes the likelihood of seeing this observation.
In our case, this is: for each possible value $\theta = m$, what is the probability of seeing $n - m$ false positives (where $n = 800$ is the number of positives observed). This is given by the following formula:
\begin{align*}
L\left( \theta = m \, \bigg| \sum_{i=1}^N Y_i = n \right)
& \, \colon = P \left( \sum_{i=1}^N Y_i = n \,\bigg| \, \theta = m \right) \\
& = P \left( \sum_{i=1}^N Y_i = n \,\bigg| \, \sum_{i=1}^N X_i = m \right) \\
& = \binom{N-m}{n-m}q^{n-m}(1-q)^{N-n},
\end{align*}
note that this is exactly the formula (but using different notation) to the first in the answer by @eclipse. Henceforth I abbreviate:
$$L(m \, | \, n)\, \colon= L\left( \theta = m \, \bigg| \sum_{i=1}^N Y_i = n \right)$$
A frequentist would now look to find $\theta^*$ such that:
$$ \theta^* = \text{argmax}_{m}\, L(m \, | \, n)$$
Actually computing $\theta^*$ from this method appears to be difficult for general $q, \, n, \, N$ (it involves a derivative over Gamma functions for which I could not find a closed form). For the case in hand ($N = 1000$, $n=800$, $q = 0.3$) this can be solved numerically (by finding the maximum of the log-likelihood); the closest integer solution returns $\theta^* = 715$, with a likelihood of $L(715 \, | \, 800) \approx 0.0515$. In particular we see that even the most likely of choices of $m$ does not assign a high probability to this event.
However, there are simpler ways to derive equivalent answers, which avoid computing the derivative of the likelihood. Using the first proposed method (see earlier post), I identified the `most likely' value $\hat p$ for the method that used Binomial distributions. Under this model, the expected number of true positives is
$$N \hat p = N \frac{\frac{n}{N} - q}{1 -q}$$
which is approximately $714.29$ for the given values of $N,\,n,\,q$; note that the difference between this and $715$ from the numerical solution is due to the numerical method only considering integer solutions.
An even simpler approach to derive the maximum likelihood estimate is the following heuristic:
\begin{align*}
E[ \text{+ve's} ] &= E[ (\text{true +ve's}) + (\text{false +ve's}) ] \\
& = \theta + q (N-\theta)
\end{align*}
conditioned on there being exactly $n$ positives, this is:
$$
\theta + q(N- \theta) = n
$$
which rearranges to give exactly the same formula as above.
Bayesian Approach.
If we want to derive a range of possible answers for $\theta$, and assign a `belief' or probability to each, then we must adopt a Bayesian approach. The important point about Bayesian thinking is that we are not describing trying to define the true distribution of the parameter $\theta$ (since we have already specified that $\theta$ is not random, so its distribution is trivial): instead we are describing the probability distribution of our belief about $\theta$.
To do this we note that using Bayes rule:
\begin{align*}
P\left(\theta = m \, \bigg| \, \sum_{i=1}^N Y_i = n \right) & =
\frac{P \left( \textstyle \sum_{i=1}^N Y_i = n \,| \, \theta = m \right) P \left( \theta = m \right)}{P\left(\textstyle \sum_{i=1}^N Y_i = n \right)}\\
& = 
L(\theta \, | \, m) \frac{P (\theta = m )}{P\left(\textstyle\sum_{i=1}^N Y_i = n \right)}
\end{align*}
The problem we face is that we do not know what $P(\theta = m)$ is (this is what we are trying to calculate!), and nor do we know $P\left( \sum_{i=1}^N Y_i = n \right)$ (which depends on knowing both the number of true and false positives, which we don't know).
The Bayesian approach is twofold: first of all, as a function of $\theta = m$, the denominator is irrelevant, as we can write:
$$
P\left(\theta = m \, \bigg| \, \sum_{i=1}^N Y_i = n \right)
\propto
L(\theta \, | \, m) P (\theta = m ),
$$
and then calculate whatever the normalizing constant, $Z$, required is to make this a probability distribution.
However, we still do not know the probability $P(\theta = m)$. The approach then is to take a `guess' (known as the prior distribution) of this probability distribution, and then to consider the left hand side of the equation to be an improvement of the guess (the posterior distribution).
This is the important caveat I described above: the Bayesian approach does not give you the true probability distribution for $\theta$, but rather it gives you a way of improving a guess of the distribution, based on observed information.
For instance, if we suppose that our best guess (prior to making any observations) is that $\theta$ is uniformly distributed between $\{0,1,\ldots, 1000\}$, so that our prior distribution is:
$$P(\theta = m) = \frac{1}{1001}, \, m \in \{0,\ldots, 1000\}$$
Then in particular we see that $P(\theta = m ) \propto 1$, so that then the posterior distribution is:
$$P\left(\theta = m \, \bigg| \, \sum_{i=1}^N Y_i = n \right) \propto L(m\,|\,n)$$
i.e.
$$P\left(\theta = m \, \bigg| \, \sum_{i=1}^N Y_i = n \right) =
Z^{-1} \binom{N-m}{n-m} q^{n-m} (1-q)^{N-n},$$
and we obtain exactly the solution given in @eclipse's post (with the powers of $q,\, (1-q)$ corrected).
However there is no reason why we should necessarily choose the prior to be uniform (other than convenience!); two arguments against it in this particular case are, do we really thinking $P(\theta = 0) > 0$ and similarly $P(\theta = 1000) > 0$? In the case of the first this would imply that there are no true positives, and only false positives. This doesn't appear to be a likely situation in a real world application. Similarly in the later, all terms are true-positives, so the notion of the false positive rate $q$ is meaningless.
Conclusion.
If we do not want to take a Bayesian approach then the Frequentist method would result in having just a single point estimate for the most likely value of $\theta$.
This aligns with the proposed `most likely' parameter $\hat p$ for the original Binomial model that I proposed; the difference however, is that the original model does not assume that the number of true positives is fixed but unknown: rather it assumes that the number of true positives is itself random.
It should not be surprising that both of these models return the same prediction of the most likely (frequentist) / average (Binomial model) number of true positives.
If one wants to assume that there is a fixed, but unknown number of true positives, but then wants a probability distribution for this, then we have to use a Bayesian approach. The interpretation of probability is then not the true distribution (which does not exist / is trivial, as $\theta$ is not random), but rather is the distribution of our `belief' in what $\theta$ is: based on some prior belief.
From a Bayesian perspective, the answer provided by @eclipse from 28/12/2017 can is valid under the following caveats:


*

*We are willing to take a Bayesian approach to solving the problem, and as such recognise that the formula given is the posterior distribution to a specific prior distribution: and not a definitive formula for the probability distribution of $\theta$.

*We are happy with the choice of a uniform prior distribution, even with its limitations as outlined above in the context of a real world scenario.

A: I want to thank owen88 for his awesome answer and I want to outline an alternate approach which seems to get different results. Mainly I would like to understand why owen88's answer is better than what I came up with.
I will use the same variables owen88 used. Basically I remodelled the problem as a negative binomial distribution where $200$ is the number of failures ($N-n = 1000-800$ in owen88's answer). $q=0.3$ is the success rate and the number of successes is a $i = 0, ..., 800$.
Edit: I only looked at the false positive and the negative results since I do not know anything about the true positive possibilities. I know that there must be exactly $N-n$ negative results which I declare as the number of failures in the negative binominal distribution. Now I just want to know how many successes (false positives) there typically should be for the number of failures I specified. So I do not look at the true positive results at all but only at the desired number of failures $N-n$ and at how many false positives there must have been for this number of failures.
$Pr(X=i)=\binom{N-n + i - 1}{i} q^{i}(1-q)^{N-n}$
Both owen88's and my answer create a normalized distribution with the same mean, but unfortunately the actual values are different and I would like to understand where the difference of the two approaches is (and which one is correct). 
I added the formulas on wolframalpha to play around with.
owen88 wolframalpha
mine wolframalpha
It would be great if someone could give me an idea which approach is correct and why.
A: After the very good points @owen88 made in his two answers I have a new answer which I think is correct. The main problem that I have with owen88's solution is that $p$ follows a binomial distribution. This surely depends on how you interpret the problem but I think one should assume that the number of true positives $m$ is fixed but unknown. As such in my opinion it would be wrong to say that $m$ follows a binomial distribution. 
Therefore, the problem can be solved as follows:
Let $m$ be fixed but unknown. Let $f=n-m$ be the number of false positives, $k=N-n$ the number of negatives and $q$ the probability of a false positive. Then the probability of getting exactly $f$ false positives can be determined with the binomial distribution:
$\binom{f+k}{f}q^f(1-q)^k$
Now we repeat this process for $m \in [0, n]$ and thereby get $n+1$ probabilities. Let $Z$ be the normalization constant then the distribution can be defined as:
$P(m = x)= Z\binom{n-x+k}{k}q^{k}(1-q)^{n-x}$
If there are no major objections from you I think this was the solution I was looking for. Major shout out to owen88 for his awesome answers! 
