That's not actually the technique the authors are using. Catching 100 fish would be analogous to "sample 100 YouTube videos at random", but they don't have a direct method of doing so. Instead, they're guessing
possible YouTube video links at random and seeing how many resolve to videos.
In the "100 fish" example, the formula for approximating the total number of fish is:
total ~= caught / tagged
(where caught=100 in the example)
In their YouTube sampling method, the formula for approximating the total number of videos is:
total ~= (valid / tried) * 2^64
Notice that this is flipped: in the fish example the main measurement is "tagged" (the number of fish that were tagged the second time you caught them), which is in the denominator. But when counting YouTube videos, the main measurement is "valid" (the number of urls that resolved to videos), which is in the numerator.
In the "100 fish" example, the formula for approximating the total number of fish is:
In their YouTube sampling method, the formula for approximating the total number of videos is: Notice that this is flipped: in the fish example the main measurement is "tagged" (the number of fish that were tagged the second time you caught them), which is in the denominator. But when counting YouTube videos, the main measurement is "valid" (the number of urls that resolved to videos), which is in the numerator.