Operator in the presence of noise 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 at random from the sphere $S^{d-1}$ of radius 1/k, where k is a large natural number. 
Let's now define the softmax function $\sigma: \mathbb{R}^d \rightarrow \mathbb{R}^d$ defined in the following way:
$\sigma(x)_i  = \frac{e^{x_i}}{\sum_j e^{x_j}}$
I need to compute the following expected value, but in the comments people made me realize that it's not possible.
$$ \mathbb{E}[||\sigma(x) - \sigma(x+\eta)||]?$$
Which means i have to look for a reasonable upper bound. Any suggestions?
Thank you!
 A: I think it is not possible analytically.
As a very simplified version of your problem, I have tried to calculate the expected value of the exponent of your random variable in 2D.
$$\langle e^{\eta_1} \rangle = \frac{1}{2 \pi} \int_0^{2\pi} e^{\frac{\cos(\theta)}{k}}d\theta$$
According to WolframAlpha, there is no closed-form solution to this integral in terms of basic functions. In order to solve your problem analytically, an integral of a more complicated integrand needs to be performed over $d-1$ dimensional sphere.
This is not unusual. Expected value is just an integral, and not all integrals have nice analytic solutions. However, it should be rather simple to compute your expected value numerically by uniformly sampling points on a sphere and taking the average of the computed norm.
$$ \mathbb{E}[||\sigma(\vec{x}) - \sigma(\vec{x}+\vec{\eta})||] \approx \frac{1}{n}\sum_{j=1}^n ||\sigma(\vec{x}) - \sigma(\vec{x}+\vec{\eta}_j)||$$
where $\vec{\eta}_j$ is a sample from your spherical distribution.
