> (*) For the math challenged: imagine that you have x pages, and y of those
> pages are free. What is the likelihood of not finding a single contiguous
> two-page area?
>
> This boils down to how to place the free pages. It's essentially:
>
> x * (x-2) * (x-4) * (x-8) * .. (y factors)
> -----------------------------
> x * x * x * .. (y factors - ie x^y)
>
> and the rate at which point this likelihood shrinks is very fast indeed.
The math isn't quite right. Consider:
1st hole placed on 1st page.
2nd hole placed on 4th page.
There are now x-5 places to place the 3rd hole, not x-4.
Did you program just count all combinations (so that the numbers you
posted are correct even if the above is off)?
The easy way to look at it is that you have y free pages in a row, and
you want to know the number of ways to place u=x-y used pages so that no
two free pages are adjacent. So, one places 1 used page between each
of the y free pages, using up y-1 of the used pages, and then one
counts the number of ways of distributing the remaining u-(y-1) dirty
pages. That'd just be the number of ways of placing u-(y-1) balls in
y+1 boxes - i.e. - you can place pages between pairs of dirty pages,
or before the 1st page, or after the last page. This is:
/ u-(y-1) + y+1 - 1 \ / u + 1 \ (u+1)!
| | = | | = ------------
\ u-(y-1) / \ u-y+1 / (u-y+1)!(y)!
(i.e. - (# of balls + # of boxes - 1) choose (# of balls)).
The total # of ways to place the free pages is x choose y, so the
probablility of having no free adjacent pages is the quotient.
Checking the formula against the numbers gives almost the same
results. I guess you wrote a program to count the combinations, but
have a small bug in it? Or you computed the above expression & it's
close enough when x is much bigger than y?
-- Harvey J. Stein BFM Financial Research hjstein@bfr.co.il- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.altern.org/andrebalsa/doc/lkml-faq.html