I'm trying to perform some calculations regarding expectation value of a minimization problem. Specifically, I'm tackling the following inequality using McDiarmid inequality: $$ \mathbb{P}\left(\left|f(X_1,\ldots,X_n)-\mathbb{E}(f(X_1,\ldots,X_n))\right|>\epsilon \right)\leq2e^{-\frac{2\epsilon^{2}}{\sum\limits_{i=0}^{n}c_i}} $$ Where $c_i=\sup_{x_{i'}}\left|f(x_1,\ldots,x_{i'},\ldots,x_n)-f(x_1,\ldots,x_i,\ldots,x_n)\right|$ (as in here).
In my problem, $f(x_1,\ldots,x_n)=\arg\min\limits _{x\in\mathbb{R}}\sum\limits _{x_j\in \left[0,1\right],j=1\ldots n}\left|x-x_{j}\right|^{p}$ (to be more specific, $x_i$ are actually taken from a uniform distribution over $[0,1]$).
I've managed to show, using symmetry, that $\mathbb{E}\left(f(X_1,\ldots,X_n)\right)=\frac{1}{2}$.
The immediate bound, $$
\mathbb{P}\left(\left|f(X_1,\ldots,X_n)-\mathbb{E}(f(X_1,\ldots,X_n))\right|>\epsilon \right)\leq2e^{-\frac{2\epsilon^{2}}{n}}
$$ is not quite enough for me, as it cannot be bounded from above when $n$ is high. I wish to sharpen this bound using a more delicate bound on the bounded difference of the arg min function in hand, but I do not see quite a way to do so (I have managed to achieve some bound in the form of $2e^{-\frac{2\epsilon^{2}}{n^{1-\frac{1}{p}}}}$, but it still does not suffice).
Thank you for any help!