I'm trying to prove a result but I'm stuck at the very end of it: I'm having troubles understanding how noise propagates when considering a probability distribution. In other words, if I inject some noise in a vector, how does it change its probability distribution? Let's give some notation:


Let $\sigma: \mathbb{R}^d \rightarrow (0,1)^d$ be the softmax operator which maps $x$ to the manifold of the probability distributions on $d$ variables defined in the following way:
$$\sigma(x)\_i = \frac{e^{x\_i}}{\sum\_j e^{x\_j}}$$
I have a vector $x \in \mathbb{R}^d$ with norm one. I also have random noise vector $\eta \in \mathbb{R}^d$ with norm $1/k$ taken uniformely at random from the sphere $S^{d-1}$ of radius 1/k, where k is a large natural number. 


I need to compute an upper bound of the following expected value, which is the norm of the difference between the vector without noise and the one with injected noise $\eta$:


$$ \mathbb{E}[||\sigma(x) - \sigma(x+\eta)||]$$


I gave a bounty to this question because I really need to understand this problem (I will have to solve several problems of this kind).


Thank you very much!



How sensitive are probability distributions to noise?
$$\mathbb{E}(|\sigma(x+\eta)-\sigma(x)|)=\mathbb{E}(|J\_\sigma\eta|)+O(|\eta|^2)$$where $J\_\sigma$ is the Jacobi matrix $$ (J\_\sigma)\_{i,j}=\frac{e^{x\_i}}{\sum\_k e^{x\_k}}\delta\_{i,j} - \frac{e^{x\_i+x\_j}}{(\sum\_k e^{x\_k})^2}$$ and $$\mathbb{E}(|J\_\sigma\eta|)^2\leq \mathbb{E}(|J\_\sigma\eta|^2)=\mathbb{E}(\langle \eta J\_\sigma^2\eta\rangle)=\frac{|\eta|^2}{d}\text{Tr}(J\_\sigma^2)$$with $$\text{Tr}(J\_\sigma^2 )=\sum\_i \frac{e^{2x\_i}}{(\sum\_k e^{x\_k})^2}+\sum\_{i,j} \frac{e^{2x\_i}e^{2x\_j}}{(\sum\_k e^{x\_k})^4} -2\sum\_{i}\frac{e^{3x\_i}}{(\sum\_k e^{x\_k})^3} \\ = \sum\_i (\sigma(x)\_i)^2+\big(\sum\_i (\sigma(x)\_i)^2\big)^2-2\sum\_i (\sigma(x)\_i)^3$$


Conclusion : $$\mathbb{E}(|\sigma(x+\eta)-\sigma(x)|)\leq \frac{\eta}{\sqrt{d}}\sqrt{\sum\_i (\sigma(x)\_i)^2+\big(\sum\_i (\sigma(x)\_i)^2\big)^2-2\sum\_i (\sigma(x)\_i)^3
}+O(|\eta|^2)$$


