[bushindo]

This is a followup to Bonanova's killville problem. I'll quote his statement of the problem here

"You live in Killville - a town populated by 10 killers and 10 pacifists.

When a pacifist meets a pacifist, nothing happens.

When a pacifist meets a killer, the pacifist is killed.

When two killers meet, both die.

Assume meetings always occur between exactly two persons

and the pairs involved are completely random."

These meetings continue until all killers are dead.

Now, you are an insurance underwriter. One of the pacifists come to you before joining Killville, and ask for a 1 million dollars insurance policy. In order to set the premium, you need to compute his chance of surviving Killville.

1) Compute the pacifist's chance of survival.

2) Compute the pacifist's chance of survival exactly ( simulation and approximation methods are not allowed) .

Edited August 11, 2009 by bushindo

[Guest]

i get

i get the chance of survival is 1/19

logic is you have

round p

1--- (9/19)--- 1/19 chance of being paired with anyone

2 --- (9-x)/(9) --- x=pacifists that died last turn

3 --- (9-x-z)/(9-z-u) --- z=pacifists died this turn u equals killers dead but z+u=x because there are x badies left so that many people die

3 still --- (9-x-z)/(9-x)---

4--- (9-x-z-q)/(9-x-q-v)--- q=pacifists died v equals others q+v=z

4 still --- (9-x-z-q)/(9-x-z)

so on so on giving

(9/19)((9-x)/9)((9-x-z)/(9-x))((9-x-z-q)/(9-x-z)).....

all the variables cancel out leaving

think this works but the number does seem too simple

[bushindo]

i get

i get the chance of survival is 1/19

logic is you have

round p

1--- (9/19)--- 1/19 chance of being paired with anyone

2 --- (9-x)/(9) --- x=pacifists that died last turn

3 --- (9-x-z)/(9-z-u) --- z=pacifists died this turn u equals killers dead but z+u=x because there are x badies left so that many people die

3 still --- (9-x-z)/(9-x)---

4--- (9-x-z-q)/(9-x-q-v)--- q=pacifists died v equals others q+v=z

4 still --- (9-x-z-q)/(9-x-z)

so on so on giving

(9/19)((9-x)/9)((9-x-z)/(9-x))((9-x-z-q)/(9-x-z)).....

all the variables cancel out leaving

think this works but the number does seem too simple

I got a higher value of p after some simulation

[Guest]

100% Survival Chance. "These meetings continue until all killers are dead."

" 'Now', you are an insurance underwriter."

[Guest]

wow that program was vaguely annoying to write but your right i got a significantly different answer and i dont know if you just werent going to hint at my mistake or didnt catch it but here it is (still unsolved tho)

i get the chance of survival is 1/19

logic is you have

round p

1--- (9/19)--- 1/19 chance of being paired with anyone

2 --- (9-x)/(9) --- x=pacifists that died last turn

3 --- (9-x-z)/(9-z-u) --- z=pacifists died this turn u equals killers dead but z+u=x because there are x badies left so that many people die

3 still --- (9-x-z)/(9-x)---

4--- (9-x-z-q)/(9-x-q-v)--- q=pacifists died v equals others q+v=z

4 still --- (9-x-z-q)/(9-x-z)

so on so on giving

(9/19)((9-x)/9)((9-x-z)/(9-x))((9-x-z-q)/(9-x-z)).....

all the variables cancel out leaving

i think this is almost true the thing is this is the probability he wins on the infinith try or something that doesnt make any sense the answer should be (P(x)=chance it ends on x turn)

p(0)+9/19p(1)+p(2)(9-x)/19+p(3)(9-x-z)/19+p(4)(9-x-z-q)/(19)

these are something like

p(0)=(9*7*5*3)/(19*17*15*13*....*1)

p(1)=(x-1)(x-3)....(x-(x-1))/((9-a)*(7-a)*(5-a)*(3-a)*(1-a)) a=0

with

p(2)=p(1) plug in z for x and x+z for a

my mind is not sure of the immediatiely above right now my brain had one of those "where am i" moments where your only chance to ever understand math again is sleep so tommorow

i also had something else to say that was going towards the answer but ...

oh also bushindo did u get

.0929

?

[bonanova]

1/11

The pacifist survival expectation is P/(K+1).

Divide that by P to get individual pacifist's survival probability: p=1/(K+1).

[bonanova]

For K killers and P pacifists, and N = K+P, when two of them meet at random,

p(KK) = K(K-1)/N(N-1)

p(KP) = KP/N(N-1)

p(PK) = PK/N(N-1)

p(PP) = P(P-1)/N(N-1)

Nothing happens in the PP meetings.

So consider only the relative probability r of (KK) and (mixed KP) meetings:

r(KK) = p(KK)/[p(KP) + p(PK) + p(KK)] = K(K-1)/[KP + PK + K(K-1)] = (K-1)/[2P + (K-1)]

r(mix) = [p(KP) + p(PK)]/[p(KP) + p(PK) + p(KK)] = 2KP/[KP + PK + K(K-1)] = 2P/[2P + (K-1)]

Note that r(KK) + r(mix) = 1.

Beginning with state {K, P} we go with probability r(KK) to state {K-2, P}

and with probability r(mix) to state {K, P-1}

Continuing the process along a binary decision tree we eventually reach

either a state {0, y} which has y surviving pacifists, or a state {x, 0}

with no surviving pacifists.

We are only interested in the {0, y} terminal states, where y>0.

To compute the expected pacifist survival population, for each {0, y} state

multiply y by the product of the probabilities of the meetings sequence that

led to that state. Then add the results for all {0, y} states.

To get the survival probability for any one pacifist (they are all the same)

divide by P, the original number of pacifists.

The decision tree for an initial state of {10, 10} has many branches, so it

makes sense to calculate survival expectations for simpler cases first.

It's trivial to find that {2, 2}'s survival expectation is 2/3, and in the process

find that {2, 1} expectation is 1/3. Then construct the decision tree for {4, 4}

to find its expectation of .8; along with {2, 3} of 1, {2, 4} 0f 4/3, {4, 1} of .2,

{4, 2} of .4, and {4,3} of .6.

In each case the expectation is a fraction whose numerator is just P and

whose denominator is K+1.

The decision trees for {6, 6}, {8, 8} and {10, 10} get increasingly large,

but you eventually are convinced of the P/(K+1) result. It would be cool

to work out a recursion formula for {K, P} in terms of smaller K and P values,

but I think it's unavoidable to just work through the decision trees, and that's

a lot of work. I stopped at the {6, 6} case.

All the results given above agree with simulation.

[bushindo]

For K killers and P pacifists, and N = K+P, when two of them meet at random,

p(KK) = K(K-1)/N(N-1)

p(KP) = KP/N(N-1)

p(PK) = PK/N(N-1)

p(PP) = P(P-1)/N(N-1)

Nothing happens in the PP meetings.

So consider only the relative probability r of (KK) and (mixed KP) meetings:

r(KK) = p(KK)/[p(KP) + p(PK) + p(KK)] = K(K-1)/[KP + PK + K(K-1)] = (K-1)/[2P + (K-1)]

r(mix) = [p(KP) + p(PK)]/[p(KP) + p(PK) + p(KK)] = 2KP/[KP + PK + K(K-1)] = 2P/[2P + (K-1)]

Note that r(KK) + r(mix) = 1.

Beginning with state {K, P} we go with probability r(KK) to state {K-2, P}

and with probability r(mix) to state {K, P-1}

Continuing the process along a binary decision tree we eventually reach

either a state {0, y} which has y surviving pacifists, or a state {x, 0}

with no surviving pacifists.

We are only interested in the {0, y} terminal states, where y>0.

To compute the expected pacifist survival population, for each {0, y} state

multiply y by the product of the probabilities of the meetings sequence that

led to that state. Then add the results for all {0, y} states.

To get the survival probability for any one pacifist (they are all the same)

divide by P, the original number of pacifists.

The decision tree for an initial state of {10, 10} has many branches, so it

makes sense to calculate survival expectations for simpler cases first.

It's trivial to find that {2, 2}'s survival expectation is 2/3, and in the process

find that {2, 1} expectation is 1/3. Then construct the decision tree for {4, 4}

to find its expectation of .8; along with {2, 3} of 1, {2, 4} 0f 4/3, {4, 1} of .2,

{4, 2} of .4, and {4,3} of .6.

In each case the expectation is a fraction whose numerator is just P and

whose denominator is K+1.

The decision trees for {6, 6}, {8, 8} and {10, 10} get increasingly large,

but you eventually are convinced of the P/(K+1) result. It would be cool

to work out a recursion formula for {K, P} in terms of smaller K and P values,

but I think it's unavoidable to just work through the decision trees, and that's

a lot of work. I stopped at the {6, 6} case.

All the results given above agree with simulation.

That's some slick calculations. Very nicely done.

[bonanova]

This solution is from a colleague. I only wish I had seen it.

Consider the case of K killers [K even] and 1 pacifist.

Randomly number the people 1 through K+1, and let them meet in that order: 1 meets 2; 3 meets 4; etc.

If and only if the pacifist is the last on the list does he survive.

The chances of that are 1/(K+1)

Since expectations add, if there are P initial pacifists the expected number of survivors is P/(K+1).