Gift Exchange Problem Question.
Patrick D. Rockwell
http://www.research.att.com/~njas/sequences/A102262
----------------------------------------------------------------------
OFFSET 2,3
COMMENT n friends organize a gift exchange. The n names are put into
a hat,
and the first person draws one. If she picks her own name, then she
returns
it to the bag and draws again, repeating until she has a name that is
not
her own. Then the second person draws, again returning his own name if
it
is drawn. This continues down the line. What is the probability p(n)
that
when the n-th person draws, only her own name will be left in the
bag?
I heard about the problem from Gary Thompson at Grove City College in
PA.
As n increases, p(n) approaches 1/(n + log(n) + EulerGamma), where
EulerGamma = .5772156649015... (the Euler-Mascheroni constant).
- Jon E. Schoenfield (jonscho(AT)hiwaay.net), Sep 30 2006
FORMULA p(n) = Sum_{ i = 1..n-2 } t(n,i) / (n-1)!^2,
where t(n,i) = (n-2)*i^2/(i-1)*t(n-1,i-1)-(n-i-2)*t(n-1,i) for
1<i<n-1; <---Is this right???
t(n,1) = (-1)^(n-1)*(n-1)!/2 for i=1 and n>2;
t(n,i) = 0 otherwise. - Jon E. Schoenfield (jonscho(AT)hiwaay.net),
Sep 30 2006
EXAMPLE p(2) through p(10) are 0, 1/4, 5/36, 19/144, 203/1800,
4343/43200, 63853/705600, 58129/705600, 160127/2116800.
----------------------------------------------------------------------
The comment above isn't mine. I didn't submit this to the On-Line
Encyclopedia of Integer sequences.
Just below the word "Formula" I typed in the question "Is this
right???"
I ask because,I"m wondering if there is a missing parenthesis. The
line
in question says,
"where t(n,i) = (n-2)*i^2/(i-1)*t(n-1,i-1)-(n-i-2)*t(n-1,i) for
1<i<n-1;"
Should there be an extra pair of parenthesis paranthesis around
(n-2)*i^2 ??
Harry Tuttle
in the hat, and that the probability that the last person to draw gets stuck
with her own name is therefore 1/n.
"Patrick D. Rockwell" <proc...@thegrid.net> wrote in message
news:fb78f344-1f7d-4b1f...@j1g2000prb.googlegroups.com...
Mike Terry
news:nIU5k.4509$WH.4195@trndny05...
> It seems to me that any name has an equal probability of being the last
name
> in the hat, and that the probability that the last person to draw gets
stuck
> with her own name is therefore 1/n.
>
This can't be right - consider a couple of easy cases where n is small...
Mike.
Barry Schwarz
<news.dead.p...@darjeeling.plus.com> wrote:
>"Harry Tuttle" <No...@someplace.net> wrote in message
>news:nIU5k.4509$WH.4195@trndny05...
>> It seems to me that any name has an equal probability of being the last
>name
>> in the hat, and that the probability that the last person to draw gets
>stuck
>> with her own name is therefore 1/n.
>>
>
>This can't be right - consider a couple of easy cases where n is small...
>
OK - three people named A, B, and C with C drawing last.
There are six possible ways for the names to be drawn from the hat:
ABC ACB BAC BCA CAB CBA.
C draws his own name two out of the six or 1/3
Four people A, B, C, D with D drawing last:
ABCD ABDC ACBD ACDB ADBC ADCB
BACD BADC BCAD BCDA BDAC BDCA
CABD CADB CBAD CBDA CDAB CDBA
DABC DACB DBAC DBCA DCAB DCBA
D draws his own name 6 out of 24 or 1/4.
For n people, there are n! ways to draw the names out of the hat. The
person drawing last can draw his own name after the previous n-1
people have drawn names in (n-1)! possible ways.
(n-1)!/n! is 1/n
Remove del for email
Tim Little
> There are six possible ways for the names to be drawn from the hat:
> ABC ACB BAC BCA CAB CBA.
ABC, ACB, and CBA can't happen, since any but the last person will
keep drawing until they get a name other than their own. (This is
equivalent to removing their own name from the hat before they draw,
if present, and returning it after they draw)
The weightings of each of the valid possibilities (BAC, BCA, CAB) are
not the same: BAC has probability 1/4, BCA also has probability 1/4,
but CAB has probability 1/2 since after A picks C, B can only pick A.
So C has probability 1/4 of being stuck with C.
- Tim
Virgil
Barry Schwarz <schw...@dqel.com> wrote:
> On Wed, 18 Jun 2008 01:06:18 +0100, "Mike Terry"
> <news.dead.p...@darjeeling.plus.com> wrote:
>
> >"Harry Tuttle" <No...@someplace.net> wrote in message
> >news:nIU5k.4509$WH.4195@trndny05...
> >> It seems to me that any name has an equal probability of being the last
> >name
> >> in the hat, and that the probability that the last person to draw gets
> >stuck
> >> with her own name is therefore 1/n.
In such drawings, there is usually some arrangement made to prevent any
but the last person from being stuck with his or her name, should he or
she draw it.
Perhaps after each draw, except the last, if a person draws his or her
own name, he or she draws again and then returns his or her name to the
hat.
--CELKO--
write up on the formulas at:
http://mathworld.wolfram.com/Derangement.html
It is a subset of permutations of (n) items in which no element is in
its original position. The first few terms are 0, 1, 2, 9, 44, 265,
1854, etc. So the odds of a bad drawing would be the number of
permutations minus the number of derangements, divided by the number
of permutations.
The best procedure I can think of would be to generate all of the
derangements, then pick one at random.
Mike Terry
news:73d408b5-5754-4d7c...@m44g2000hsc.googlegroups.com...
> This is called a derangement or sub-factorial and there is a short
> write up on the formulas at:
>
> http://mathworld.wolfram.com/Derangement.html
>
> It is a subset of permutations of (n) items in which no element is in
> its original position. The first few terms are 0, 1, 2, 9, 44, 265,
> 1854, etc. So the odds of a bad drawing would be the number of
> permutations minus the number of derangements, divided by the number
> of permutations.
This can't be right - consider a couple of easy cases where n is small...
Mike.
ps. it's helpful if you quote the text to which you're replying, as then
people will know what you're refering to even after the original posts have
been deleted from servers...
Harry Tuttle
Verizon.net, has decided not to carry alt. Usenet groups any more. This is
part of their crackdown on kiddie porn, so all you mathematicians out there
who post kiddie porn discretely and continuously had better watch out.
Cheers
"Mike Terry" <news.dead.p...@darjeeling.plus.com> wrote in message
news:EtWdnbMKPbxHz8HV...@posted.plusnet...
Mike Terry
> I would love to continue to participate in this discussion, but my ISP,
> Verizon.net, has decided not to carry alt. Usenet groups any more. This
is
> part of their crackdown on kiddie porn, so all you mathematicians out
there
> who post kiddie porn discretely and continuously had better watch out.
>
> Cheers
If my ISP did that I would consider changing ISPs. The only reason I
wouldn't do it straight away is that I believe there are some free news
servers out there I could use, and I would look into this first, as my ISP
is generally OK.
(Also, one could post from Google Groups I suppose, but I personally
wouldn't.)
Anyway I hope you find a way to continue posting!
Mike.
--CELKO--
Looks good to me:
1 person = 0 ways to exchange
2 persons = 1 way (a,b) -> (b,a)
3 person = 2 ways (a,b,c) -> (b,c,a), (c,a,b)
etc.
Chip Eastham
No, you've not read the original post (or missed an
important part of it). Due to the trimming of the
context, I'll restore the missing description:
> COMMENT n friends organize a gift exchange. The n
> names are put into a hat, and the first person draws
> one. If she picks her own name, then she returns it
> to the bag and draws again, repeating until she has
> a name that is not her own. Then the second person
> draws, again returning his own name if it is drawn.
> This continues down the line. What is the probability
> p(n) that when the n-th person draws, only her own
> name will be left in the bag?
So because if someone (prior to the last draw) gets
their own name, that name is returned to the hat and
drawing continues until a different name is drawn.
Thus for n=2 it is guaranteed that the last person
will not draw their own name, despite the chance of
a derangement of two items being 1/2.
The original poster was not asking generally for a
formula to find p(n), the probability that the last
person gets "her own name", but rather about the
possible absence of needed parentheses in the
formula given:
http://www.research.att.com/~njas/sequences/A102262
for an apparent recurrence relation of terms t(n,i)
that allow p(n) to be represented as a sum.
regards, chip