I am reading a paper on privacy that says we can model something as an arbitrary probabilistic function from $X^M \to X^M$. I'm trying to figure out what exactly that means. I saw another paper that defined a probabilistic function as a function $\mathcal{F}:X \times Y \to [0, 1]$ that satisfied the condition $$\forall x \in X: \sum_{y \in Y} \mathcal{F}(x, y) \leq 1.$$ But that definition doesn't seem to make sense if the function can take on values in the space $X^M$ where $X$ is an arbitrary set of objects. So what exactly are probabilistic functions?

Thanks so much!

• Can you provide a little bit more context or an example? Possibly it means a function on random variables? – Joe Bebel Mar 18 '15 at 3:28
• I imagine it's either a probability distributions over functions from $X^M$ to $X^M$, or (more or less equivalently) a function $F:X^M \times \{0,1\}^r \to X^M$. The interpretation of the latter is that for each choice of $b \in \{0,1\}^r$, $F(\cdot, b)$ is function from $X^M$ to $X^M$, and when we pick $b$ uniformly at random, we get a probability distribution over such functions. But as Joe said, please give context, ideally a link to the paper. – Sasho Nikolov Mar 18 '15 at 4:46
• Thanks @JoeBebel and @SashoNikolov! It's this paper, "Robust Deanonymization of Large Datasets": myspew.com/gallery/1/… I'm looking at page 4, and the arbitrary probabilistic function Aux. – Kristin Mar 18 '15 at 18:26

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$.

• Cool, that is interesting. I thought it would output a point in $X^M$, but I guess it actually outputs a function from $X^M$ to $[0, 1]$. Thanks for the clarification! – Kristin Mar 18 '15 at 18:24
• Actually strictly speaking it will output a point, but randomly chosen according to the distribution associated with $x$. I'll update the answer. – Klaus Draeger Mar 18 '15 at 19:14