# How sensitive are probability distributions to noise?

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!

• In 2 dimensions this can be calculated numerically and visualized, e.g. as below with $x=(2,3)$, $k=10$, $E=0.025$. wolframalpha.com/input/… If $f(\eta)$ is the norm, then $f=0$ when $\eta$ is proportional to $(1,1)$ or to $(-1,-1)$. So $f$ can be approximated by two parabolas, and $E[f]\simeq (1/3)(f((1,-1)/k\sqrt{2})+f((-1,1)/k\sqrt{2}))$. In the example, that gives $0.026$. Jan 22 '19 at 17:31
• Thank you! do you know a way to show the same thing in more dimensions? I'm trying to get an answer but I have no idea how to keep going. Thanks again! Jan 25 '19 at 18:10
• My next step would be numerical experimentation. Jan 25 '19 at 20:03
• There is one thing I don't understand from your example: $x = (2,3)$ doesn't have norm one. Did you take care of it in the Wolfram alpha experimentation? Thanks again Jan 25 '19 at 21:23
• You can see what I did in WolframAlpha and redo it with $x=(0.6,0.8)$ if you like Jan 26 '19 at 0:05

$$\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)$$
• In the first example above, the $\sigma$ coordinates are $0.27$ and $0.73$, so this gives $\frac{1}{10\sqrt{2}}\sqrt{.61 + .37 - 2(.41)} + O(1/100) \simeq .028$ Jan 31 '19 at 12:26