Can mean be less than half of median if all numbers are non-negative? I feel like I might be missing something dumb, but in a set of non-negative numbers, is it possible for the mean to be less than half of the median?
Example: there are 999 numbers and we are told that the median is 10. This means that the sum of the numbers cannot be any less than 5,000. The configuration to achieve that sum is: 500 numbers are equal to 10, 499 are equal to 0. This makes the mean 5,000 / 999 = (slightly more than) 5. Since 5,000 is the lowest possible sum, (slightly more than) 5 is the lowest possible mean. Therefore the lowest possible mean is more than one half of the median.
Am I wrong?
 A: You are correct.  This is one example of a general result called Markov's inequality, which says that for a non-negative random variable $X$ and number $a$,
$$P(X\geq a)\leq \frac{E[X]}{a}$$
If you plug in the median of $X$ for $a$ you get
$$P(X\geq \text{median})\leq \frac{E[X]}{\text{median}}$$
so
$$0.5\leq \frac{E[X]}{\text{median}}$$
and
$$ 0.5\times\text{median}\leq \text{mean}$$
Your argument is also roughly how Markov's inequality is proved.
A: 
in a set of non-negative numbers, is it possible for the mean to be less than half of the median?

No. In fact, the mean cannot even be equal to half of the median (except if every value in the set is $0$).

the lowest possible mean is more than one half of the median

This is correct (again, assuming that not all values are $0$).
Here are two simple (yet rigorous) proofs. (These proofs ignore the case where every value in the set is $0$.)
Proof 1
Let $n$ be the number of values.
If $n$ is even, then the upper $n / 2$ values must all be at least the median. If they are all equal to the median, then the value just below the midpoint must also be equal to the median.
If $n$ is odd, then the values above the median, as well as the median itself, must all be at least the median; the number of such values is:
\begin{equation*}
\frac{n - 1}{2} + 1 = \frac{n + 1}{2} > \frac{n}{2}.
\end{equation*}
Either way, there are at least $n / 2$ values that are at least the median; the sum of these values, and therefore the sum of all the values, is at least:
\begin{equation*}
\frac{n}{2} \times \text{median}.
\end{equation*}
In fact, either there are more than $n / 2$ values, or at least some of the values are greater than the median (or both), so the sum is greater than the value of this expression.
Dividing this by $n$, we find that the mean is greater than:
\begin{equation*}
\frac{1}{2} \times \text{median}.
\end{equation*}
Proof 2
We will choose an arbitrary $m$, then construct a set with median $m$ and the minimum possible mean.
We start by doing one of the following:

*

*(set has an odd number of values) Add $m$ to the set.

*(set has an even number of values) Add two values, with mean $m$, to the set. Any two values with mean $m$ make the same contribution to the mean of the set, but for maximum flexibility when adding other values later, we should set both values to $m$.

We then choose an arbitrary $n$ and:

*

*Add $n$ values that are at most $m$ to the set. To minimise the mean, we should set all these values to $0$.

*Add $n$ values that are at least $m$ to the set. To minimise the mean, we should set all these values to $m$.

Note that these steps can construct a set of any size, with any median, and the constructed set has the minimum possible mean within these constraints.
If the set has an odd number of values, the mean of the set is:
\begin{equation*}
\frac{m + nm}{1 + 2n} = \frac{1 + n}{1 + 2n} m > \frac{1}{2} m.
\end{equation*}
If the set has an even number of values, the mean of the set is:
\begin{equation*}
\frac{2m + nm}{2 + 2n} = \frac{2 + n}{2 + 2n} m > \frac{1}{2} m.
\end{equation*}
This proof is designed to emphasise the role of the $0$, building on Carl Witthoft’s comment on another answer (emphasis added):

Interesting, since naively I'd think that shifting your dataset uniformly by a value $X$ would not affect median vs. mean. What's hidden here (if I get it right) is that a non-negative dataset is asymmetric, being bounded on one end only.

