Statistics problem, minimum sample size for accurate estimate A friend of mine recently had a problem at work, and needs to get an estimate for his boss, this is what he sent me:

Assume I work at a food shipping company.
A bunch of our crates of oranges were exposed to freezing
  temperatures, and many of the oranges are now destroyed. However,
  those near the center of the pallets are still mostly intact, but are
  lightly damaged on the rind--they can still be used for some purposes,
  but not others. What's more, there's a variable number of oranges per
  crate, in a non-even and random distribution. Some have 1 orange, some
  have 40 (and there's been an upper boundary of 80, but anything past
  50 is an anomaly). My boss needs to know how many oranges we should
  expect to regard as lightly frost-burnt, which means I need a way to
  estimate an average number of oranges per crate, and .
Now, we've got a BIG warehouse. If I have to open every crate and
  count how many oranges are in each one in the 'frostburnt' category,
  they'll rot before I'm done anyway. So I need to do a sampling to get
  a faster estimate.
So, given:
C = # Crates A range of 0 - 50 oranges per crate, unevenly distributed
  (but not in a known way)
How many randomly selected crates, as a proportion of C, must I get a
  count on to get a reliable average?

Can anyone help me out?
 A: Your situation is tailor-made for Hoeffding's Inequality, though this will give a high theoretical bound that you may wish to ignore for practical reasons.
Hoeffding's Inequality (or rather a special case thereof):
$$p\left(\left|\overline{X} - E(\overline{X})\right| \geq \epsilon\right) \leq 2\, \mathrm{exp}\left(-\frac{2 n \epsilon^2}{L^2}\right)$$
Where $\overline{X} = \frac{X_1+\ldots+X_n}{n}$, where $X_i$ are independent or are sampled without replacement (that's what we'll use here) and $X_i$ takes values in $[0,L]$.
Let $X_i$ be the probability distribution for the number spoiled in the $i^{\mathrm{th}}$ randomly selected box.
The inequality tells us that no matter what the probability distributions are for number of bad oranges, if we have a given error tolerance, there exists a number $n$ of crates we should open to have the probability that our observed average is within some chosen $\epsilon$ of the true average within that error tolerance.
At this point it's just choosing your error tolerance, your $\epsilon$, and plugging in $L = 80$ (or something higher to be conservative) and finding $n$, the number of crates. Interestingly, this is not a proportion of $C$, but rather some absolute number depending on your tolerances. (There is actually a better bound incorporating $C$, but if $C$ is very large it won't help much.)

Plugging in some numbers:
Say you want to get the number spoilt per box to within $\epsilon = 5$, and you want the probability you are off by more than that to be less than $.05$ (i.e. 5%). Then you should open $n = 473$ randomly selected boxes and take the average number spoilt, for then the RHS is $.0497$.
Something more lax: Suppose you want the number spoilt per box to within $\epsilon = 10$ and you want the probability you are off by more than that to be less than $.1 = 10\%$ (you don't need to change $\epsilon$ and the probability you're wrong together, this is just an example). Then you should open $n = 96$ randomly selected boxes for then the RHS is $.0996$.
A: You could use a sample size of one crate and still get a sensible point estimate.  The way a minimum sample size comes into play is if you want to put confidence limits on your estimate; e.g., "I want to be 95% confident that the estimated proportion of frost-burnt oranges is within, say, +/- 5% of the true proportion."  But in order to answer that  question, you also have to place some kind of distributional assumption on the random variables of interest (here, the number of oranges per crate, and the conditional distribution of the proportion of frost-burnt oranges given the number of oranges in the crate).
And the problem with this is that because you do not have any reasonable assumptions, imposing some would not necessarily lead you to a "correct" or reasonable sample size:  you could still be off.
So, the simplest thing to do is to just choose random crates, open them up, and start counting.  You do it for as many crates that you can, and you collect data on the observed number of oranges in each crate, and the observed proportion of those oranges that are frost burnt in each crate.  Then, on the basis of this collected data, you could have enough information to impose distributional assumptions (Poisson?  Binomial?  Exponential?  Gamma?  Normal?), from which you could then determine retrospectively whether the sample size is sufficient for your desired precision.
