Assume there is a task pool which has $m$ unprocessed tasks. There are $n$ processors to process the tasks.
The rules of processing tasks are:
- The processors pick up tasks in the task pool randomly.
- At each round, all the processors will get a chance to pick up tasks and they are capable of finishing processing the tasks before they get the next chance.
- A processor has no idea about the choice of the other processors. This means that each time a task could be chosen by multiple processors, and there will be multiple copies of the same result after processing.
- A processor does not keep a history of the processed tasks. This means it could choose a task which has been processed by itself before.
Note that the number of tasks in the task pool does not change: a processed task stays in the pool and could be picked up again. (although unnecessary)
Let $x$ denote the number of rounds needed to finish picking up all tasks and processing them. The questions are:
- What is the probability distribution of $x$?
- What is the mathematical expectation of $x$?
In addition, what if a processor can pick up $p$ tasks and process them in parallel at each round? This time the $p$ tasks are different from each other.
