## Partial orders and expectations

Arrangements, sorting, packing, partitions, critical path analysis, networks, graphs, ...
Bubbler
Posts: 28
Joined: Sat Feb 23, 2013 6:12 am

### Partial orders and expectations

There are n cards numbered 1 to n, and you have a machine that will pick orderings between k pairs of cards.
For example, if n = 5 and k = 3, you might see something like this:
1 -> 3
4 -> 1
5 -> 2
(left -> right: place "right" somewhere on the right side of "left")
In this case, you have 10 possible options to place 5 cards following the 3 given orderings.
One such option is 4 -> 1 -> 5 -> 3 -> 2.

The machine picks each number completely randomly, so you may get duplicate orderings or reversed orderings (you have no options for this case), but not both number being the same (such as 1 -> 1).

Define E(n,k) as the expected number of possible arrangements of n cards, following k random orderings produced by the machine.
For example, E(2,1) = 1, E(3,1) = 3, E(3,2) = 3/2 (this can be verified by brute force by hand).

Give the values of E(5,3) and E(10,5).

Edit: I made a mistake counting the number of ones in my hand-drawn table. Oops.
Last edited by Bubbler on Fri Jan 23, 2015 10:09 am, edited 1 time in total. mpiotte
Posts: 1914
Joined: Tue May 08, 2012 4:40 pm

### Re: Partial orders and expectations

Bubbler wrote:...
Define E(n,k) as the expected number of possible arrangements of n cards, following k random orderings produced by the machine.
For example, E(2,1) = 1, E(3,1) = 3, E(3,2) = 4/3 (this can be verified by brute force by hand).
...
Let's see if I understand correctly.

Take the case E(3, 2). Assume the first random pair is (a, b), with c = 6 - a - b, the remaining number.
The second pair can be:
(a, b): 3 arrangements c - a - b, a - c- b, a - b - c.
(b, a): 0 arrangement
(a, c): 2 arrangements a - b - c, a - c - b
(c, a): 1 arrangement c - a - b
(b, c): 1 arrangement a - b - c
(c, b): 2 arrangements c - a - b, a - c - b
So E(3,2) = (3 + 0 + 2 + 1 + 1 + 2)/6 = 3/2.

I haven't worked all the details, but I suspect E(n, k) = n!/2k. Bubbler
Posts: 28
Joined: Sat Feb 23, 2013 6:12 am

### Re: Partial orders and expectations

Yes, the correct value of E(3,2) is 3/2, not 4/3. I edited the original post. Bubbler
Posts: 28
Joined: Sat Feb 23, 2013 6:12 am

### Re: Partial orders and expectations

mpiotte wrote:... but I suspect E(n, k) = n!/2k.
While coding a brute-force counting algorithm to check some more values, I think I found a proof to this:

The expected value E(n,k) is N = (the total number of the tuple (one of n! permutations and its k matching orderings)) divided by D = (the total number of k orderings).
Each ordering can be one of n(n-1) possible orderings, and each total ordering satisfies exactly n(n-1)/2 of them.
Therefore, N = n! * (n(n-1)/2)^k and D = (n(n-1))^k, so E(n,k) = N / D = n!/(2^k). 