We may have seven billion people or so on this planet, but how closely related are we? Is it possible somewhere down the family tree of a person selected from a random sample of the American population to be a minor direct descendant of an English nobleman? Is it possible for anyone to track down his or her family tree, even though one must understand that not everyone’s ancestors were literate?
Examples from your family history would be helpful in this discussion. 
Kind of a generality, but I read years ago that all humans are no further than 14[sup]th[/sup] cousins from each other. Though that may be a little misleading, a 14[sup]th[/sup] cousin is a very, very, *VERY *distant relation…
Any “European” is certainly descended from Charlemagne, but most of us wouldn’t be able to state any specific chain of links back to Charlemagne. For most of us, just to trace ancestry back to the 18th century is difficult, let alone the “English nobleman” who would lead us to Charlemagne and other Kings. Be aware that a large portion of pedigrees shown on the Internet are erroneous.
In my own case, I can trace ancestry back to several early American immigrants (though none on the Mayflower 
) including one with surname Campbell who was banished to America in 1685 during the Monmouth Rebellion. I’ve searched lists of Monmouth prisoners and deportees and been unable to identify him, but even if he were actually the son of a land-owning Campbell it wouldn’t give me a clear descent from Kings unless he were an actual descendant of the Earls of Argyll. (The 1st Earl was gt gt grandson of Robert II King of Scots.)
Questions about inter-relatedness are discussed at Wikipedia, complicated scientific models (pdf) and other SDMB threads including Is Julius Caesar’s bloodline traceable to present day?, Geneology. Anyone famous in your ancestry ?, My most distant human relation, Oldest Extant family in the World, and Prince William marrying a distant cousin
This may be right in the vast majority of cases, but fail between extremely isolated groups. Is it really likely that a Kalahari Bushman and a Sentinelese have a post-Columbian common ancestor?
Very very roughly, one can expect to have a few thousand living 5th cousins, perhaps a million living 11th cousins, and so on. I seem to be 6th cousin of Brad Pitt, the best I’ve come up with among famous living persons.
I wouldn’t put money on it, but it wouldn’t be astonishing if they did.
San almost certainly have a post-Columbian ancestor in common with Europeans. They haven’t been isolated in any meaningful sense for at least the past 400 years, since intermarriage with the Bantu peoples has been commonplace. The Andamanese are a bit more tricky, but they also have not been perfectly isolated for a very long time and they are a very, very small population, just a couple of hundred people. So a single Indian or English ancestor would be sufficient to guarantee commonality with the rest of humanity.
I agree that all San probably have a post-Columbian Eurasian ancestor, call him A; and that the Andamanese may as well, call him B. But do A and B share a common post-Columbian ancestor?, which would be required for the San and Andamanese to be 14th cousins. Possible, but very unlikely IMO.
(ETA: I’ve overstated the requirement, since there will be multiple A’s and B’s. … I think we’re in agreement except for the actual probability estimate which I would guess to be somewhat lower than “wouldn’t be astonishing”. 
)