story identification - Protagonist finds coin from a parallel universe, lets it guide him via flipping heads/tails

This is a short story that I read several (5?) years ago. I don't believe it was new, but I don't remember how old it was, either. If I had to guess based on style, I would say that it was probably written sometime in the 80s or 90s.

The protagonist comes across an old coin that isn't from anywhere -- at least, not from anywhere that he or coin dealers or historians can identify. Somehow, he gets the idea that the coin is from another, parallel reality, and he decides that it would "want" to go home, if it could. He starts to travel, and whenever he comes to a decision about where to go next, he lets a coin toss (using that coin) decide the issue. The transition from one reality to another is gradual, not sudden like going through a portal, more like elements of reality being gradually replaced as he goes from one place to another.

Eventually, he does get to the place where the coin originated, at which point the plot (if I'm recalling correctly) devolves into a rescue-the-princess-from-the-clutches-of-the-evil-king/sorcerer/vizier scenario.

The parallel universe that the coin came from is full of deserts and has an "Arabian Nights" flavor. I think the protagonist meets a djinn/genie in the desert when he first gets to the right universe, but that could be something I'm mixing in from a different tale.

I'm drawing blanks on more specific details, but hopefully someone will recognize it from the above.

Answer

You're thinking of Gateway to Elsewhere (1954), aka Journey to Barkut, by Murray Leinster.

The protagonist, Tony Gregg, has a gold coin which he considers to be a good luck charm. An inscription on the coin indicates it's from the apparently non-existent land of Barkut. Tony gets in the habit of flipping the coin to make small decisions, and one day it leads him to meet a man who recognizes the coin and tells Tony that it came from another world.

Tony figures the coin wants to go home, so he uses coin flips to guide himself on a long journey which eventually leads back to Barkut. He learns that Barkut is inhabited by men and Djinn, who are at odds with each other. He has further adventures with the Djinn.

Gateway was reprinted in the 2005 collection A Logic Named Joe. Google Books has a page for Logic which lets you view parts of the book. I have an electronic copy of Logic which I think I downloaded from the Baen Free Library, but it's not available for download there at the moment.

Baen also distributed CDs with electronic copies of their books. The CDs are apparently freely distributable, and I was able to find a site with several CDs for download. Logic appears to be available on some of the CDs. Some googling should lead you to other sites where the CDs and their contents can be downloaded.

Edit: @sean-duggan found a complete copy of A Logic Named Joe freely accessible in HTML form on Baen's websubscriptions site. Gateway to Elsewhere is included.