0
$\begingroup$

In The Library of Babel, there are all the possible 410-page books of a certain format and character set.

There is a legendary book, called a total book, which is supposed to be the catalogue of the library. Now, this is clearly absurd, since any catalogue of the library must contain more information than a mere 410-page book could contain. In fact, since the library has 0 information, to merely write down the address of a certain book takes as much information as the amount of information in that book. Thus, in general, the address of any book is as long as the book itself (410 pages long), and such a total book cannot exist.

But let's suppose it does.

In the story, people have searched for such a book, in vain. So they decided to search for the book indirectly:

How could one locate the venerated and secret hexagon which housed Him? Someone proposed a regressive method: To locate book A, consult first book B which indicates A's position; to locate book B, consult first a book C, and so on to infinity ...

I thought "obviously this can't work! It's just self-handicapping an informationless random search, you can't do better that way!"

But then I remembered the 100 prisoners problem, and thought perhaps this method could work.

So here's my problem:

Consider a list (representing the library) of length $N$, and each element (representing a book) is a number between $1$ and $N$ (representing what that book refers to). One of these elements is chosen as special (representing that total book).

Two players are tasked with searching for the book. One player simply searches from the beginning and thus would expect to take $N/2$ steps to find the special element. The other "follows the leads" in each element, and if he finds himself directed to a previously visited element, he would instead search the least unvisited element.

How long would the second player take? I expect it to be $N/2$, since obviously this strategy doesn't work. But then, how is it that this strategy does work in the 100 prisoners problem?

$\endgroup$
  • $\begingroup$ You say "In The Library of Babel, there are all the possible 410-page books of a certain format and character set." That does not mean that it contains only those books! $\endgroup$ – user247327 May 31 at 19:36
  • $\begingroup$ You seem to forget that in the 100 prisoners problem way more than 50 drawers are opened: each prisoner gets to open at most 50 drawers. And they must all locate there own number, not collaborate to find a single "treasure" number. $\endgroup$ – Marc van Leeuwen May 31 at 19:43
1
$\begingroup$

(1) I would also expect the second player to take $N/2$ steps, but I cannot think of any easy proof. EDIT @MikeEarnest gave a great short proof, as always. :) Anyway, this isn't important...

(2) The key interesting aspect of the $100$ prisoners problem is IMHO this line in the wikipedia article:

important observation is that this way [the cycle-following method] the success of one prisoner is not independent of the success of the other prisoners

In the prisoners problem, let $A_i$ be the event that prisoner $i$ finds his own number within $50$ boxes. It is still true that $\forall i: P(A_i) = 1/2$.

However, the magic of the cycle-following method is that $A_i$ are highly-correlated events! And why is this important? Because by the definition of the problem, overall success is defined as $\bigcap_i A_i$.

If each prisoner looks randomly, then $A_i$'s are independent, and $P(\bigcap_i A_i) = ({\frac12})^{100} \approx 0$. But the cycle-following method makes $P(\bigcap_i A_i) \approx 0.31$. In both cases, $\forall i: P(A_i) = 1/2$ individually.

BTW since the prisoners are now correlated so that they likely succeed together, this also means they likely fail together. E.g., in the random method, the number of prisoners who found his own number, call it $K$, would be $K \sim Binomial(100, 1/2)$, which is unimodal around $50$ (mean $50$, standard deviation $5$, you get the idea). In contrast, in the cycle-following method, $K$ would be very bimodal. In both cases $E[K] = 50$. However, by the problem definition, you don't care about the value of $K$ - except whether it is $= 100$ or $<100$. Informally speaking, failing a little is just as bad as failing catastrophically, and that is due to the definition of success as $\bigcap_i A_i$.

$\endgroup$
2
$\begingroup$

It does not matter what order you search the books in; the expected time it takes to find the special book is always $(N+1)/2$. No matter what, the first book you check is equally likely to be any number between $1$ and $N$, and the second book is equally likely to be any number unequal to the first book, and in general the $k^{th}$ book is equally likely to be anything unequal to the first $(k-1)$ books.

$\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.