# Complexity class of a problem asking for a chance of receiving an item

I have asked a question on math.SE about if there is a way to do it better than by brute force, but this time I am interested in the complexity of the problem itself. I will repeat the problem, with a slight change to it:

Suppose, you have a box $$B$$ with $$n$$ items and you pull $$k items out of it. Items have different (positive integer) sizes $$s_i$$, with larger items being more probable to get pulled out: $$p(i) = \frac{s_i}{\sum_{\forall j\in B}{s_j}}$$ Is the expected probability that an item $$i$$ will be among the $$k$$ items you will have pulled out of the box greater than (a finite decimal number) $$x$$?

I could not find a straightforward way to even show that it's in $$\mathsf{MA}$$. On the other hand, I also could not find a way to show $$\mathsf{NP}$$-hardness.

• I assume the probability adjusts every time an item is pulled? So it gets bigger if a very large item gets removed? I'd first try to figure out how to calculate the probability at all. Commented Nov 24, 2023 at 15:55
• Yes, the probability is just the weight of the item divided by the weight of all items remaining in the box at the moment you pull it out. That way removing an item from a box creates a problem instance of a smaller size, like as if you assigned one variable in SAT. Commented Nov 24, 2023 at 16:31
• @D.W. Clarified it, though whether it's a decimal or a binary fraction should not affect the complexity. Basically, it's just a decision variant (so you could use the binary search) of computing $O(n)$ first digits of the probability that $i$ will be among the $k$ items. Commented Nov 25, 2023 at 0:12