1
$\begingroup$

Conjecture: Let $N$ be a non-empty and finite set. There exists a probability distribution $p$ on the set of all partitions of $N$, $Z(N)$, such that $$\sum_{P\in Z(N):S\in P}p(P)= {1 \over n\cdot \binom{n-1}{s-1}}$$ for all $S\subseteq N:S\ne \emptyset$, where $p(P)$ denotes the probability of partition $P$, $n=|N|$, $s=|S|$.

Trivial? Known? Drops from deeper results? Any idea?

$\endgroup$
2
  • 5
    $\begingroup$ Can you elaborate on why this statement is of interest? $\endgroup$ Jun 13, 2014 at 6:55
  • $\begingroup$ I don't know whether this is particulary interesting from a purely mathematical perspective. I posted this on a whim mainly as a brain teaser. But there is some serious background. Actually, I had proved this conjecture in a working paper on the potential of the Shapley value due to Hart and Mas-Colell (1989, Potential, value, and consistency, Econometrica 57, 589-614). And I was wondering whether this already was shown elsewhere or whether there is an interesting proof other than mine. $\endgroup$
    – 2nd2god
    Sep 9, 2014 at 4:42

1 Answer 1

5
$\begingroup$

Recall that the number of permutations $\sigma$ of a set $N$ of cardinality $n$
for which a given non-empty subset $S\subset N$ of cardinality $s$ is an orbit (that is a $\sigma$-invariant subset generated by some element $x\in N$, whose complement is also $\sigma$-invariant) is, of course, just $(s-1)!(n-s)! $.

So we may interpret the ratio $$\frac{1} {n {n-1 \choose s-1}}=\frac{(s-1)!(n-s)!}{n!}\qquad\qquad{\bf (1)}$$ as the probability that the subset $S$ be an orbit of a permutation of $N$, uniformly chosen at random.

Therefore, a probability distribution on $Z(N)$ that fulfills your requirement is just the law of the map $\operatorname{Orb}: {\frak S}(N)\to Z(N)$ (that takes a permutation into its orbit partition) seen as a random variable based on ${\frak S}(N)$, with its uniform probability distribution. In particular we have, for $ P\in Z(N)$ $$p(P)=\frac{1}{n!} \prod_{S\in P}(|S|-1)! \qquad\qquad{\bf (2)}$$

Also note that $p$ is unique, under the obvious independence and symmetry assumptions that allow to deduce formula (2) .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.