I have a question like this:
Consider $N$ samples $X\_1, X\_2, ..., X\_N$ that uniformly random generated from standard basis $\{e\_i, i=1,2,...,d\}$, i.e. $(1,0,0,\cdots,0),(0,1,0,\cdots,0),(0,0,1,0,\cdots,0),\cdots,(0,0,0,\cdots,1)$. Dimension $d$. My question is how can I get an upper bound on $\|\sum\_{i=1}^N X\_i\|$. I know $\mathbb{E}\|\sum\_{i=1}^N X\_i\|=\frac{N}{\sqrt{d}}$. In other word, what concentration inequality should I use to get something like
$$
P(|\|\sum\_{i=1}^N X\_i\|-\mathbb{E}\|\sum\_{i=1}^N X\_i\||>\epsilon)\leq \delta
$$


so that I can rewrite $\epsilon$ as a form contains $\delta, d, N $ and upper bound $\|\sum\_{i=1}^N X\_i\|$ with probability $1-\delta$.


Thanks!



Bound the norm of sum of random vector that generated from standard basis
Let $n:=N$ and $V:=\|\sum\_{i=1}^n X\_i\|$.


Using [Talagrand's concentration inequality](https://en.wikipedia.org/wiki/Talagrand%27s_concentration_inequality) as applied to linear functions in [Section 2.2](https://ocw.mit.edu/courses/sloan-school-of-management/15-070j-advanced-stochastic-processes-fall-2013/lecture-notes/MIT15_070JF13_Lec13.pdf), we can get  

$$P(|V-EV\,|\ge x)\le5\exp\Big(-\frac{x^2}{16n}\Big)$$
for all real $x\ge0$. One can see that this bound does not depend on $d$.


I will not provide details on this, because in this situation one can get better constants using McDiarmid's inequality, and this can be done almost immediately. Indeed, letting $g(x\_1,\dots,x\_n):=\|\sum\_{i=1}^n x\_i\|$ for $(x\_1,\dots,x\_n)\in\{e\_1,\dots,e\_d\}^n$, we see that $g(X\_1,\dots,X\_n)=V$ and [condition (18)](http://maxim.ece.illinois.edu/teaching/fall13/notes/concentration.pdf) holds with $c\_i=\sqrt2$ for all $i=1,\dots,n$. So, by [inequalities (19)--(20) in the same lecture notes](http://maxim.ece.illinois.edu/teaching/fall13/notes/concentration.pdf),
$$P(|V-EV\,|\ge x)\le2\exp\Big(-\frac{x^2}{n}\Big)$$
for all real $x\ge0$.


