0
$\begingroup$

I've been using the Stanford Algorithms (1) Coursera course, and in a description of a problem, the lecturer said that in the problem of allocating n processes to n servers at random, the sample space of allocations is n^n, and each has equal probability.

Intuitively this seems unlikely to me: if you imagine each server having a number and that number being the number of processes assigned, you wouldn't have the case of two servers being assigned n processes; yet the n^n -- as far as I can see -- assumes that such allocations are possible.

Am I missing something?

$\endgroup$
3
$\begingroup$

The number $n^n$ can be easily obtained if you think the problem in the other direction: each process has $n$ choices and therefore $n$ processes has $n^n$ possible choices in total. Of course it is impossible that two servers have $n$ processes. If a process can be assigned to more than one server, the number of possible assignments is far more than $n^n$.

$\endgroup$
0
$\begingroup$

"you wouldn't have the case of two servers being assigned n processes"

No, you certainly cannot have two servers, each being assigned $n$ processes, as that would require a total of $2n$ processes -- whereas there are in fact only $n$ processes.

"yet the n^n -- as far as I can see -- assumes that such allocations are possible."

There's the source of your misconception. I'm not sure why you think this is true. (In the future, if you spell out your reasoning in the question, it's more likely someone can give you a helpful explanation.) No, the $n^n$ answer does not assume that such an allocation is possible.

One way to help you think about this is try thinking about the case $n=2$. Write down the sample space: try writing down all possible outcomes, and the probability of each. I think that will help you see what's going on.

Here's the other way to think about it: for each process, there are $n$ places it can go (independent of all other processes). For two processes, that means $n^2$ ways where to assign them. For $n$ processes, there are $n^n$ ways to assign them.

But try the example with $n=2$ and see what happens. If that's not enough, next try the example with $n=3$ and see what happens. In general, if you are confused, working through special cases and small examples is often extremely helpful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.