What is a probabilistic function and where can I learn more about them?
The definition you give is essentially the one you need. A probabilistic function from $X$ to $Y$ assigns to each $x\in X$ a subdistribution of elements of $Y$ (rather than a single $y\in Y$). Such a subdistribution is a function $\delta:Y\to[0,1]$ such that

$\sum_{y\in Y}\delta(y)\leq 1$.

In other words, a probabilistic function $X\to Y$ is a function $f:X\to(Y\to [0,1])$, i.e. $f:X\times Y\to [0,1]$, such that for all $x\in X,$

$\sum_{y\in Y}f(x,y)\leq 1$.

In your case, both domain and codomain are $X^M$; a probabilistic function from $X^M$ to $X^M$ then is a function $f:X^M\times X^M\to [0,1]$ such that for all $x\in X^M$,

$\sum_{y\in X^M} f(x,y)\leq 1$.

The intended meaning of this is that the function still returns a single point when given some input, but this point is chosen randomly according to the relevant distribution. For example, if $M=2$, and $f(1,2) = \{(1,1)\mapsto 0.5,(2,2)\mapsto 0.5\}$ (all others being $0$), then when you call $f(1,2)$, you will get $(1,1)$ or $(2,2)$ each with probability $0.5$.