Actually the 'Gambler's Fallacy' is an example of Cognitive Dissonance. You are holding two 'truths/fallacies' in your head at the same time.

Truth/Fallacy 1: There is a 50/50 probability that the next flip will be either Heads or Tails.

Truth/Fallacy 2: In the long string of flips, the probability is that there will be a 50:50 distribution of Heads and Tails, so the next flip be a value which will tend to regress the overall value to the mean of 50:50.

If you hold to Truth No. 1, you have no difficulty in believing that 1000 flips can come up 1000 Tails just as easily as the 50:50 result.

If you hold to Truth No. 2 you are guilty of subscribing to the 'Gambler's Fallacy'.

Which way do you jump? :)

> If you hold to Truth No. 1, you have no difficulty in believing that 1000 flips can come up 1000 Tails just as easily as the 50:50 result.

There are (1000 choose 500) ways to an equal number of heads/tails and 1 way to get all tails. If you get all tails, you should probably question the correctness of your model.