How do you decide the sample size when polling a large population? Australia is currently having an election and understandably the media reports new political poll results daily. In a country of 22 million what percentage of the population would need to be sampled to get a statistically valid result?
Is it possible that using too large a sample could affect the results, or does statistical validity monotonically increase with sample size?
 A: Suppose that you want to know what percentage of people would vote for a particular candidate (say, $\pi$, note that by definition $\pi$ is between 0 and 100). You sample $N$ voters at random to find out how they would vote and your survey of these $N$ voters tells you that the percentage is $p$. So, you would like to establish a confidence interval for the true percentage. 
If you assume that $p$ is normally distributed (an assumption that may or may not be justified depending on how 'big' $N$ is) then your confidence interval for $\pi$ would be of the following form:
$$
CI = [ p - k * sd(p),~~ p + k * sd(p)]
$$
where $k$ is a constant that depends on the extent of confidence you want (i.e., 95% or 99% etc).
From a polling perspective, you want the width of your confidence interval to be 'low'. Usually, pollsters work with the margin of error which is basically one-half of the CI. In other words, $\text{MoE} = k * sd(p)$.  
Here is how we would go about calculating $sd(p)$: By definition, $p = \sum X_i / N$ where, $X_i = 1$ if voter $i$ votes for candidate and $0$ otherwise.
Since, we sampled the voters at random, we could assume that $X_i$ is a i.i.d Bernoulli random variable. Therefore, 
$$
Var(P) =  V\left( \sum\frac{X_i}{N}\right) = \frac{\sum V(X_i)}{N^2} = \frac{N \pi (1-\pi)}{N^2} = \frac{\pi  (1-\pi)}{N}.
$$
Thus,
$$
sd(p) = \sqrt{\frac{\pi * (1-\pi)}{N}}
$$
Now to estimate margin of error we need to know $\pi$ which we do not know obviously. But, an inspection of the numerator suggests that the 'worst' estimate for $sd(p)$ in the sense that we get the 'largest' standard deviation is when $\pi = 0.5$. Therefore, the worst possible standard deviation is:
$$
sd(p) = \sqrt{0.5 * 0.5 / N } = 0.5 / \sqrt{N}
$$
So, you see that the margin of error falls off exponentially with $N$ and thus you really do not need very big samples to reduce your margin of error, or in other words $N$ need not be very large for you to obtain a narrow confidence interval.
For example, for a 95 % confidence interval (i.e., $k= 1.96$) and $N = 1000$, the confidence interval is: 
$$
\left[p - 1.96 \frac{0.5}{\sqrt{1000}},~~ p + 1.96 \frac{0.5}{\sqrt{1000}}\right] = [p - 0.03,~~ p + 0.03] 
$$
As we increase $N$ the costs of polling go up linearly but the gains go down exponentially. That is the reason why pollsters usually cap $N$ at 1000 as that gives them a reasonable error of margin under the worst possible assumption of $\pi = 50\%$.  
A: As a rough generalization, any time you sample a fraction of the people in a population, you're going to get a different answer than if you sample the same number again (but possibly different people).
So if you want to find out how many people in Australia are >= 30 years old, and if the true fraction (God told us) just happened to be precisely 0.4, and if we ask 100 people, the average number we can expect to say they are >= 30 is 100 x 0.4 = 40, and the standard deviation of that number is +/- sqrt(100 * 0.4 * 0.6) = sqrt(24) ~ 4.9 or 4.9% (Binomial distribution).
Since that square root is in there, when the sample size goes up by 100 times, the standard deviation goes down by 10 times. So in general, to reduce the uncertainty of a measurement like this by a factor of 10, you need to sample 100 times as many people. So if you ask 100 x 100 = 10000 people, the standard deviation would go up to 49 or, as a percent, down to 0.49%.
A: Sample size doesn't much depend on the population size, which is counter-intuitive to many.
Most polling companies use 400 or 1000 people in their samples.
There is a reason for this:
A sample size of 400 will give you a confidence interval of +/-5% 19 times out of 20 (95%)
A sample size of 1000 will give you a confidence interval of +/-3% 19 times out of 20 (95%)
When you are measuring a proportion near 50% anyways. 
This calculator isn't bad:
http://www.raosoft.com/samplesize.html
