MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let's say I have some number of individuals who are single, $(b_1, ..., b_N) \in B$, and for every possible pairing of two individuals, $b_i$ and $b_j$, I happen to know the exact probability that the two will irreversibly become married if they happen to meet. With this in mind, I select $k$ of the individuals in $B$ for a dating party, where each person randomly meets with others until all $k$ individuals are married (assuming that there are an even number of participants and only non-zero probabilities for marriage).

Knowing the probabilities that each potential couple become married, and assuming that pairings at the dating party are truly random, how do I optimally select the $k$ individuals to maximize the probability that the same pairings occur over multiple independent trials? How might I calculate the probability that one or a set of couplings occur in each trial?

Note: Strictly for the sake of this problem, pairings may occur between any two individuals without regard to gender.

share|cite|improve this question
Please define "the outcome of the party is most likely to be the same over multiple independent trials". – Brendan McKay Sep 18 '11 at 15:06
@Brendan, hopefully my rephrasing clarified the issue. I would like to optimize the probability that the same set of couple pairings occur over multiple independent trials of the 'dating party' where the 'k' individuals are randomly introduced to one-another. For example, if k=4 and 'A' marries 'B' and 'C' marries 'D' in one trial, I want to maximize the probability that this occurs in a successive independent trial and minimize other possibilities (such as 'A' marries 'C' and 'B' marries 'D'). – D. Strong Sep 18 '11 at 16:34
I don't believe your problem is quite well-defined. Suppose A is compatible with α and β, and B is compatible with β and γ, and C is compatible with γ. You have a party with A, B, C, α, β and γ. (So I seem to be assuming everybody is straight.) If the probability that two mutually compatible individuals get married is $p$, I assume the probability that A marries both α and β is not $p^2$. – Peter Shor Sep 18 '11 at 16:57
Shooting from the hip here, I suspect the answer will be something like picking those k entities so that the resulting kxk probability matrix will look most like the identity. How much most is, I don't know, but I would think it to be substochastic with the diagonal at least (k-1)/k to ensure repeated pairings. I think simulating some 4x4 cases should be feasible and enlightening. Gerhard "Double Entendre Is More Meaningful" Paseman, 2011.09.18 – Gerhard Paseman Sep 18 '11 at 18:02
Rereading my comment above, I realize I spoke hastily. Let K be the 2x2 matrix [0 1,1 0]; Instead of identity I should talk about a block matrix with K's along the diagonal, or something that is equivalent to it up to a relabeling. Add a small symmetric error matrix to that block matrix, and you may end up with a probability matrix which might give you your desired outcome. Gerhard "Ask Me Not About Direction" Paseman, 2011.09.18 – Gerhard Paseman Sep 18 '11 at 23:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.