How many coins do I need to get all the characters in Crossy Road?

To be 95% certain of getting the last character you need from the Crossy Road vending machine, you’ll need 26,800 coins.  (Jump to the full table.)
Let me explain.
Crossy Road is a game for iOS and Android. It’s been described as ‘endless frogger‘. You begin playing as a chicken, and you have to cross a road and other obstacles.
For extra fun, the game offers additional characters to replace the chicken. At the time of writing there are 72 104 characters: farm-yard animals, jungle frogs, ghosts, zombies, robots, aliens and fauna from the Australian outback. You can even play as humans in the form of the game’s three creators.

Eight Fourteen of these characters are only unlockable by playing the game. The rest can either be purchased for 99 cents each, or else won for free via an 8-bit animated vending machine. As you play the game, you amass coins, and these can be spent in the virtual vending machine at 100 coins per spin. The reasons why the game is set up like this is set out in an interesting interview with the Matt Hall and Andy Sum, who made the game.
The little characters drop randomly from the machine, so initially, every spin pretty much guarantees a new character to play with. But as the player collects more of these characters, the chances of receiving one you already have increases. By the time you have, say, 50 or 60 of the characters, winning a new one is a rarity.  Watch Sam Boyer spend 7,300 in game coins, winning some new characters in the process.
So, when I already have a large collection, how many coins do I need to be sure of getting a new character from the machine?
This is a mathematical problem. The chance of getting a new character on any given spin is simply the number of remaining characters, divided by the total number available. So, if you still need 16 animals, that is a 1 in 4 chance of success. But if you have all but 2 of the characters (my situation at the time of writing) then it’s a 1 in 32 chance of getting a new one when you spin the wheel.
Now a 1 in 32 chance to win might suggest that if only you made 32 spins of the wheel (which would cost 3,200 in-game coins) you would be certain of victory. But that is not how the laws of probability work. Each spin is an independent event. It’s possible that the vending machine may yield 32 robots in a row. So accruing 3,200 coins does not guarantee success, merely a better chance of it.
How many coins would we need to give ourselves, say, a 95% chance of a new toy?
We could draw up a complex probability tree, with all possible combinations of win-and-lose. This is time-consuming.
A simpler way to get at the answer is to consider the chances of abject failure. What if every spin of the wheel resulted in a duplicate prize? A 95% chance of success is the same as a 5% chance of failure. So if we work out how many failed pulls of the lever it takes before the probability drops below 5% or 0.05, we are also working out the number of spins it would take to be 95% confident that one of those spins would deliver a new toy.
If success on a single spin is a 2 in 64 chance, then failure is a 62 in 64 chance, or 0.96875 probability (quite high, but not certain). Failure on two consecutive spins is 0.96875 x 0.96875, or 0.96875²  = 0.9384765625. Failure on 3 consecutive spins is 0.96875³ or 0.909149169921875. Still a likely occurrence. We’ll need many more attempts before continued failure becomes unlikely.
How many spins (s) do we need to get the probability of constant failure all the way down to 0.05? The equation we need to solve looks like this:

To solve s, you need to rearrange the equation using logarithms.

The answer to this is 94.357640867. This means that if you do between 94 and 95 spins of the vending machine, there is a 95% probability that you will get at least one new toy.
Remember, this is for when you only need 2 more fluffy characters to complete the set. But it may be that you need more or less than that. In the future the developers, Hipster Whale, will probably add more characters. Finally, you may wish to do the calculation with a higher or lower probability than the 95% figure I chose. So all the numbers in the equation can be replaced with algebraic unknowns.

Where t is the total number of characters available; n is the number of characters you already have; p is the certainty that you would like to calculate (a number between 0 and 1); then s will be the number of spins required.
To make the answers meaningful, you have to round up whatever you calculate for s to a whole number, since you cannot have a fraction of a spin. And of course the number of coins you require is the number of spins, multiplied by 100.
I’ve used the equation above to determine the required number of coins to get a new character for a 50%, 95% and 99% probability. The results are tabulated below. I have omitted results when more than 30 characters are still required because at that point you will still be getting a new character at least every three or four spins.
I imagine that most people will consult this table when they are nearing a full complement of characters. Scroll down to the bottom to see the incredibly large number of coins required to give yourselves a sporting chance of actually getting those elusive final few cute pixellated characters.

Table last updated: 28 June 2015 (Korean update, 90 possible characters)

Here is a video I made showing off the fact I managed to get all the characters via the vending machine.  Since then two updates (UK & Ireland, Korea) have added many more characters to the game.