Partial orders and expectations

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

Partial orders and expectations

Post by Bubbler » Thu Jan 22, 2015 10:53 am

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

User avatar
mpiotte
Administrator
Posts: 1914
Joined: Tue May 08, 2012 4:40 pm
Location: Montréal, Canada

Re: Partial orders and expectations

Post by mpiotte » Thu Jan 22, 2015 11:48 pm

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

Bubbler
Posts: 28
Joined: Sat Feb 23, 2013 6:12 am

Re: Partial orders and expectations

Post by Bubbler » Fri Jan 23, 2015 10:11 am

Yes, the correct value of E(3,2) is 3/2, not 4/3. I edited the original post.
Image

Bubbler
Posts: 28
Joined: Sat Feb 23, 2013 6:12 am

Re: Partial orders and expectations

Post by Bubbler » Sat Jan 24, 2015 10:12 am

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).
Image

Post Reply