What is the minimum sample size for an exact binomial test of goodness of fit (two-tailed)? I am doing a two tailed exact binomial goodness of fit test, see, e.g., here. I am looking for something similar as for Chi-square tests, which, as a rule of thumb, require a frequency of 5 for each cell in the table. So, what is the minimum sample size for an exact binomial test of goodness of fit (two-tailed)?
 A: *

*You have the "rule of thumb" wrong. It doesn't say you need a frequency of 5 in each cell. It relates to expected frequency under the null hypothesis. You could have 10 in one cell and 0 in the other, but if $p_0=\frac12$ then the expected frequencies are both 5.

*The point of the rule of thumb is that then the discrete distribution of the chi-squared statistic should be reasonably close to the continuous chi-squared distribution you're looking up when you do a chi-squared test.
Here's the null distribution (i.e. cdf) of the (discrete) chi-square statistic in the above situation (n=10,p=$\frac{_1}{^2}$) (blue) and the continuous chi-square distribution that approximates it:

[If combined with Yates' continuity correction that would give a better approximation.]

*With the exact binomial test you're looking up what will be* the exact discrete distribution of the count in one cell, so there's no minimum sample size at which it applies, since you're not dealing with an approximation.
* under the assumptions of independence and constant probability per trial
