I am trying to upper bound the variance of a centered tree and I would like to get an upper bound which would look like : $$\sum\limits\_{\substack{ (l\_1, ..., l\_d) \neq (k\_1, ..., k\_d), \\ \sum\_{j=1}^d l\_{j} = \sum\_{j=1}^d k\_{j} = k } } \frac{k!}{k\_{1}! ... k\_{d} !} \frac{k!}{l\_{1}!... l\_{d} !} \left(\frac{1}{2} \right)^{\sum\_{j=1}^d \mathbb{1}\_{l\_j \neq k\_j}} \leq C\_d d^{2k} \varepsilon(k)$$
where $C\_d$ is any constant depending only on $d$ and $\varepsilon(k)$ tends to $0$ as $k$ tends to infinity. We are summing over both $l\_j$s and $k\_j$s. We know that a single sum of multinomial coefficients equals $d^k$. Therefore, writing $k =qd+r$, I tried to distinguish two parts of the sum, a part $A$ where $\left(1/2\right)^{\sum\_{j=1}^d \mathbb{1}\_{l\_j \neq k\_j}} \leq (1/2)^q$ and we have $$A \leq \left(\frac{1}{2}\right)^q d^{2k}, $$ and another part $B$ which contains much less terms (only the terms where $\sum\_{j=1}^d \mathbb{1}\_{l\_j \neq k\_j} \leq q-1$) with something polynomial in $k$ (i.e $k^d+...$) but I've been unsuccessful so far.


The overall sum comes from, with $x \in [0,1]^d$ a given point and $X$ a uniform random variable on $[0,1]^d$, $$\mathbb{E} \left[ \left( \sum\limits\_{\substack{(k\_1, ..., k\_d), \\ \sum\_{j=1}^d k\_{j} = k } } \frac{k!}{k\_{1}! ... k\_{d} !} \left(\frac{1}{d}\right)^k \prod\_{j=1}^d \mathbb{1}\_{\lceil 2^{k\_j} x\_j\rceil = \lceil 2^{k\_j} X\_j\rceil} \right)^2\right] $$
where $\lceil y \rceil$ corresponds to the first integer $m$ such that $m \geq y$.


I welcome any suggestions or ideas and would be happy to discuss this problem with you !



Upper bound for the crossed-terms of a sum of multinomial coefficients
I think that you cannot hope for $\epsilon(k)$ going to zero. Using the identity
$$(x\_1+\ldots+x\_d)^k=\sum\_{0\leq k\_1,k\_2,\ldots,k\_d\leq k\_1+\ldots+k\_d=k}\frac{k!x\_1^{k\_1}\cdots x\_d^{k\_d}}{k\_1!\cdots k\_d!}$$
we get the lower bound
$$2^{-d}d^{2k}-\sum\_{0\leq k\_1,\ldots,k\_d\leq k\_1+\ldots+k\_d=d}\left(\frac{k!}{k\_1!\cdots k\_d!}\right)^2$$ (take the square of the above identity and set $x\_1=\ldots=x\_d=1$) on your quantity.


We have yet to show that the
correction
$$C=\sum\_{0\leq k\_1,\ldots,k\_d\leq k\_1+\ldots+k\_d=d}\left(\frac{k!}{k\_1!\cdots k\_d!}\right)^2$$
is $o(d^{2k})$.


Since contributions to
$$A=\sum\_{0\leq k\_1,\ldots,k\_d\leq k\_1+\ldots+k\_d=d}\frac{k!}{k\_1!\cdots k\_d!}$$
behave roughly like a multiple of a Gaussian centered at $\frac{1}{d}(k,k,\ldots,k)$ with variance of order $\sqrt{k}$, the size of $C$ is roughly (up to a constant asymptotically) given by
$$\frac{A^2}{\sqrt{k}^d}=d^{2k}\sqrt{k}^{-d}$$ which ends the proof.


