The gambler's fallacy can be illustrated by a game in which a coin is tossed over and over again. Suppose that the coin is in fact fair, so that the chances of it coming up heads are exactly 0.5 (a half). Then the chances of it coming up heads twice in succession are 0.5×0.5=0.25 (a quarter); three times in succession, they are 0.125 (an eighth) and so on. In general, long 'runs' consisting of an unbroken succession of heads are more and more unlikely.
Nothing fallacious so far; but suppose that we are in one of these states where, say, four heads have just come up in a row, and someone argues as follows: a run of five successive heads is very unlikely (the probability is in fact one-thirtysecond, or 0.03125), so it is more likely that the next toss will be a tail than a head. That is the fallacy: the idea that a run of luck in the past somehow influences the odds of a bet in the future. Related fallacious ideas are inherent in such phrases as "a lucky streak" or "a winning streak" or a "break".
Since the odds of a run of five heads are indeed very low, one might wonder where the fallacy lies. The point is that those odds are low given no prior information. But at the point when the fallacy is formulated, four of those heads are already tossed; there is no uncertainty about them at all. Given that we are already in a state which itself had a probability of only one-sixteenth (the odds of getting four heads in a row), we can be sure that the next state will in fact have an uncertainty of one-thirtysecond no matter what the next toss is. The odds of a heads on the next toss (for a fair coin) are even, no matter what the past history of the gamble has been.
Sometimes, gamblers argue like this: "I just lost four times. Since the coin is fair and therefore in the long run everything has to even out, if I just keep playing, I will eventually win my money back." The probability is indeed equal to one that the gambler will eventually win his money back; however, the expected number of times he has to play is infinite, and so is the expected amount of capital he will need! A similar argument shows that the popular doubling strategy (start with $1, if you lose, bet $2, then $4 etc., until you win) does not work. Situations like these are investigated in the mathematical theory of random walks.
Notice that the gambler's fallacy is quite different from the following path of reasoning (which comes to the opposite conclusion): the coin comes up heads more often than tails, so it is not a fair coin, so I will bet that the next toss will be heads also. This is not fallacious, though the first step - the argument from a finite number of observations to a statement of likelihood - is a very delicate matter, and is itself prone to fallacies of its own peculiar kind.
See also: inverse gambler's fallacy