I have following question I can't get fully behind.
Suppose we have $n$ black balls and each ball independently has a probability of $\frac{1}{n^\frac{1}{3}}$ to turn red. Show that with a probability of at least $1-\frac{1}{n}$, that the number of red balls is at the most $O(n^\frac{2}{3})$.
I tried making a random variable $X_b$ for each ball $b$ that is $1$, if it turned red, and $0$ else. For these, it holds that $Pr[X_b=1]=\frac{1}{n^\frac{1}{3}}$. Then, since we have independent binary random variables, we can define $X:=\sum_{b} X_b$ for the number of red balls, which then in turn is binomially distributed. But now I'm stuck on what to do. Is this even the right approach?
Recall that $X_b=1$, if ball $b$ turned up red, and $0$ else. Then $p=P[X_b=1]= n^{-1/3}\ $ and $X:=\sum_{b=1}^n X_b$ is Bin$(n,p)$ distributed, with mean $\mu=np=n^{2/3}$.
The relevant Chernoff bound [1] to apply is the upper bound: $$P [X > (1+\delta)\mu] < \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu.$$ Applying this with $\delta=1$, say, gives $$P[X>2n^{2/3}] <(e/4)^{n^{2/3}} =o(1/n) \,.$$
[1] https://en.wikipedia.org/wiki/Chernoff_bound#Multiplicative_form_(relative_error)