SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
perico
Topic Author
Posts: 16
Joined: July 14th, 2002, 3:00 am

Secret Santa

June 24th, 2015, 10:34 am

Hi, guys, an easy problem for you:We have 10 people. Each one of them has to make a present to somebody else (not to himself), so that everyone will end up with one present from another guy from the group. After a valid draw in which everybody will get a present, which is the probability that at least one couple will share a present, that is A will give a present to B and B to A?. Which is the answer for n people?Note that the probability is AFTER a valid draw (in which nobody gives away to himself), which by the way is a different problem.
 
User avatar
wileysw
Posts: 593
Joined: December 9th, 2006, 6:13 pm

Secret Santa

June 27th, 2015, 6:54 am

perico,essentially one needs to count the number of permutations without certain types of cycles. to calculate the probability (assuming all the valid draws are equally possible), denominator: the ones with no fixed point, which is known as 'derangement' (e.g., here is one hard version); numerator: denominator less the ones with no fixed point and no 2-cycles. one could write down the recurrence relation, but a simpler way is to consider the exponential generating function: starts with the one for all cycles: 1/(1-z) and sequentially removing the fixed point then the two cycles, i.e., denominator: the coefficients of exp(-z)/(1-z) and numerator: [exp(-z)-exp(-z-z^2/2)]/(1-z).for reference when n=10, one gets: 525105/1334961, which is already close to the limit of 1-1/sqrt(e) when n -> infty
Last edited by wileysw on June 26th, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
riccardox
Posts: 2
Joined: February 25th, 2016, 2:29 pm

Secret Santa

March 11th, 2016, 9:28 am

this is solved in a book Mosteller with an elementary method "straight from the book" let's say.
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On