Probability of sequence of samples from A being more likely in B I am trying to solve a problem, whereas I have two discrete and finite probability distributions, $A$ and $B$, over the same space. A sequence of observation of size $k$ is sampled from $A$: $(o_1, o_2, .., o_k) \text{ where } o_i \sim A$
Now, the question is: how can I compute (or approximate) the probability that the sequence of length $k$ (sampled from $A$) is actually more likely to occur in $B$?
There is a simple analytical answer, which is for a fixed $k$, compute all possible combinations, compute the probability of each sequence in both $B$ and $A$, and then simply divide $\frac{|\text{sequences more likely in } B|}{|\text{number of sequences}|}$.
However, this is computationally intractable, so I need either a smarter way of doing it, or a good approximations. I thought about elements which are always more likely in $B$ than $A$, and the working only with those, however I think the error here would be pretty large.
 A: There won't be an efficient general-case exact algorithm for this.
Suppose you had an algorithm that finds the exact solution. You could use it to find the probability that a random sequence is more likely to be from $A$ than from $B$, and also to find the probability that a random sequence is more likely to be from $B$ than from $A$. Whether those two probabilities sum to 1 tells you whether there exists a sequence that is exactly equally likely to come from either distribution.
Suppose that $A$ is a uniform distribution on the integers $1, ..., n$. Then every sequence taking values on those integers has probability $\frac{1}{n^k}$ of being drawn from $A$.
Suppose that $b_m$ is the probability of drawing $m$ from the distribution $B$.
Then an exact solution would tell us whether there exist $1 \le m_1 \le ... \le m_k \le n$ such that $\prod_i b_{m_i} = \frac{1}{n^k}$. Or equivalently, whether $\sum_i -\log b_{m_i} = k \log n$.
This is essentially the sum-subset problem with fixed size constraint, for which there is no known efficient algorithm (except for small $k$).
