# probability and average output

I have a question about a homework problem. Basically, let's say we have 100 transactions, and we want to run as many as we possibly can at the same time. We have 20% contention.

I want to find out how many out of the 100 we can run in parallel, on average. I went about it this way:

Say we run the first transaction. Then there are 20 transactions we can't run. Say we run the 2nd transaction as well. At worst, there are 16 others (20% of 100 - 20) that we can't add. So after 2 transactions added to the "run set," we have 62 options to choose from and we keep going.

I don't think that works, and I wanted a mathematical way to do it. Any help would be greatly appreciated.

-
As I understand your question, right at the start we can run 80 of the transactions at the same time, and the other 20 conflict in some unknown way. Is this correct? – Patrick Feb 27 '12 at 23:43
@Patrick - Sorry I clarified my problem. Essentially, 20% contention suggests that each element conflicts with 20% of the elements. – John Doe Feb 27 '12 at 23:49
Suggests, or is defined as? Let $E_{ij}$ be the event that transaction $i$ conflicts with transaction $j$. What, precisely, do you know or can you assume about these events? For example, are they independent? – Robert Israel Feb 28 '12 at 0:02
It is precise. We can create the transactions, and we create 100 active transactions, so we are guaranteed that every transaction will conflict with 20 others. Conflicting transactions can't run at the same time, but that's the only limitation. – John Doe Feb 28 '12 at 0:07
It depends on the pattern of mutual contention. In the worst case, you can only run five at a time, where the $100$ come for example in five groups of $20$ mutually exclusive transactions. – Henry Feb 28 '12 at 0:18