Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Imagine a "risk only" slot machine that takes 'coins' corresponding to some real number fraction of a dollar $p$, returns the coin with probability $p$, and eats the coin with probability $(1-p)$. For example, a dime would be eaten with a probability of 90%, a nickel with probability 95%, and so forth.

So let's keep feeding the machine two kinds of coins, $A$ and $B$, with fractional dollar values of $p_A$ and $p_B$, respectively. I have $n_A$ coins of type $A$ and $n_B$ coins of type $B$. Each time I use the slot machine, I randomly select a coin, ignoring its type, and place it in the machine. I stop feeding coins into the machine when I run out of either type.

CLARIFICATION - By "randomly select a coin" I mean that we select a coin from the population of all coins uniformly and randomly. For instance, if we have $100$ dimes and $567$ nickels, we'd draw a dime with probability $\frac{100}{667}$.

At this stopping point, what is the probability of ending with only coins of type A or only coins of type B? Provided we end with coins of one type / denomination, what probability distribution and expectation do we have for the number of remaining coins of this type / denomination?

I'd also be curious on the number of coins of either type we needed to feed to the machine to reach this end-state? E.g. how many times did we feed the machine a dime, and how many times did we feed the machine a nickel before stopping?

(Important Note) - I asked this question over at math.stackexchange about a week ago (http://math.stackexchange.com/questions/579894/ruin-time-for-a-two-input-risk-only-slot-machine) and never recieved any answers. I hesitate to post it here, because it seems too low level, so please provide me feedback if I've erred, and I'll delete the question.


This kind of Polya's urn problem naturally arises in any situation where we sequentially and uniformly select elements from a population, run a test to decide whether to keep an element or discard it, and where the test has some probability of failing that is specific to the element being tested. For example, maybe we're sequentially and uniformly selecting cells from a population, testing to see if they're cancerous at the single cell level, and then killing or replacing the cells depending on the outcome of the test.

A very specific example of this scenerio can occur in the context of Fluorescence Activated Cell Sorting (FACS) (http://www.bio.davidson.edu/courses/genomics/method/facs.html), where cells are irradiated and imaged one-by-one, and an on-the-fly decision must be made for how the cell should be sorted (depending on some criterion related to fluorescent markers). To be careful though, sorting cells into two bins and then running one of the bins through the sorting procedure again is a distinct process from the one we describe and care about in the above problem description! To stay true to the above problem description, we'd need to have a single rejection bin and immediately return cells that are not discarded to the general population s.t. they have the same chance of being selected during the next test cycle as any other cell.


On Douglas Zare's suggestion, and if it helps, I can provide some simulation data (based on Mathematica's PRNG). For example, starting with $100$ dimes and $100$ nickels:

$n_A = 100$

$n_B = 100$

$p_A = 0.10$

$p_B = 0.05$

We achieve the following results for $10^4$ trials:

The mean number of times we place a dime in the machine $= 109.721$ (Median $ = 110$)

The mean number of times we place a nickel in the machine $= 104.42$ (Median $ = 104$)

The number of times we end with only dimes: $5669$

The number of times we end with only nickels: $4331$

The average number of dimes at the end state (conditioned on running out of nickels first): $2.18328$ (Median $= 2$)

The average number of nickels at the end state (conditioned on running out of dimes first): $1.80513$ (Median $= 1$)

**

Let's do another simulation starting with $82$ copies of hypothetical 75 cent coins and $432$ copies of 5 cent nickels, and again perform $10^4$ trials:

$n_A = 82$

$n_B = 432$

$p_A = 0.75$

$p_B = 0.05$

We achieve the following results for $10^4$ trials:

The mean number of times we place a 75 cent coin in the machine $= 268.213$ (Median $ = 267$)

The mean number of times we place a 5 cent nickel in the machine $= 454.734$ (Median $ = 455$)

The number of times we end with only 75 cent pieces: $9999$

The number of times we end with only 5 cent nickels: $1$

The average number of 75 cent coins at the end state (conditioned on running out of 5 cent nickels first): $14.9384$ (Median $= 15$)

The average number of nickels at the end state (conditioned on running out of dimes first): $1$ (Median $= 1$)

share|improve this question
1  
I don't see a research angle here -- to me this looks like an arbitrary exercise from a probability class. Therefore I have voted to send this back to Math.SE. –  Stefan Kohl Dec 2 '13 at 23:35
    
@StefanKohl As I said, no hurt feelings here. This isn't however from a probability class, but the research angle is not from pure mathematics (pretty clearly). :) –  Harrison Dec 2 '13 at 23:48
3  
This may resemble an exercise, but it also resembles some interesting urn models which were posted on MO in the past, with many upvotes and answers giving nontrivial perspectives. Without trying to do it, I can't tell whether it is a straightforward exercise, or much more interesting. So, I would not vote to close. –  Douglas Zare Dec 2 '13 at 23:49
    
@Harrison: I suggest describing more of the connection to the original problem, and including some of the simulation data. –  Douglas Zare Dec 2 '13 at 23:55
    
For finite coins you can use well known calculations with Markov chain matrices to compute the distribution over the absorbing states (the states with only one coin type) given your initial state (your initial amounts of each coin type). –  guest Dec 3 '13 at 0:09

2 Answers 2

This isn't an answer so please vote it down, but if you want a closed-form approximation then you can say that you begin with some finite distribution of coin amounts, so instead of saying you start with 100 of each of two types of coins say that you start with 0.5 of each. The amounts of coins decreases according to some kind of stochastic differential equation, and you want the probability that type A vs. type B reaches zero first, and a distribution over type B coin amount given that the type A coin amount has reached zero. Someone who knows about stochastic differential equations (I don't) could probably do something with this.

Edit:

I added a dynamic programming (well, memoized recursion) implementation to compute the exact probabilities for the cases that were explored using simulation in your examples.

$ python3 dynam.py 100 100 0.10 0.05
(0.565953327653153, 0.4340466723468455)
$ python3 dynam.py 82 432 0.75 0.05
(0.9996341756920857, 0.00036582430791369064)

Here is the code with comments:

from functools import lru_cache
import sys
sys.setrecursionlimit(10000)

def dot(a, b):
    return sum(u*v for u, v in zip(a, b))

@lru_cache(maxsize=None)
def get_absorbing_distn(count, prob):

    # Terminate memoized recursion if only one type remains.
    occupied = tuple(1 if c else 0 for c in count)
    if sum(occupied) == 1:
        return occupied

    # Compute probability of discard of each coin per time step,
    # then condition on a coin being discarded
    # (in other words keep drawing coins until one is discarded).
    n = sum(count)
    pdisc_per_step = tuple(c*p/n for c, p in zip(count, prob))
    pdisc_total = sum(pdisc_per_step)
    pdiscard = tuple(p / pdisc_total for p in pdisc_per_step)

    # For each potential outcome compute the next absorbing distribution.
    ntypes = len(count)
    next_distns = []
    for i in range(ntypes):
        next_count = tuple(c - (i==j) for j, c in enumerate(count))
        next_distns.append(get_absorbing_distn(next_count, prob))

    # Return the weighted sum of distributions for the next states.
    return tuple(dot(pdiscard, pabsorb) for pabsorb in zip(*next_distns))

na, nb = [int(v) for v in sys.argv[1:3]]
pa, pb = [float(v) for v in sys.argv[3:5]]

print(get_absorbing_distn((na, nb), (1-pa, 1-pb)))
share|improve this answer
    
Thanks for the very helpful check on my simulation results. However: "It roughly agrees with your simulations, except that I think there is a p vs. 1-p inconsistency in your notation." Could you post your results? I don't think I made a mistake? –  Harrison Dec 3 '13 at 17:54
    
Yeah you are right, I was wrong about your question having a notation inconsistency. –  guest Dec 3 '13 at 18:00
    
Still, its very helpful to have in independent confirmation of the simulation - it's not hard to write, but requires enough code to allow for mistakes. –  Harrison Dec 3 '13 at 18:06
    
Great! You probably already know this but just in case it isn't clear, this code computes the exact probabilities without using simulation. –  guest Dec 3 '13 at 18:10
    
Sorry, I didn't mean to suggest that this was a simulation result. I just meant that this calculation was a helpful check on my simulation. :) –  Harrison Dec 3 '13 at 18:12

The lifetimes of the coins can be modeled by independent exponential variables of rate $1-p$ (that is, mean $1/(1-p)$). It might be easier to think of the coin as being repeatedly eaten at the events of a rate $1-p$ Poisson point process. Such a process can be generated from a rate 1 process by discarding events with probability $p$. Discarding will correspond to returning the coin. By memorylessness of the Poisson process, at any time, each uneaten coin is equally likely to have an event in its rate 1 process, but the larger coins will more likely survive by having the event discarded. Therefore the order in which the coins disappear will be distributed as in the original model.

The probability that a nickel survives 100 dimes and 99 other nickels is equal to $$\int_0^\infty 0.95\cdot e^{-0.95t}\cdot (1-e^{-0.9t})^{100}\cdot(1-e^{-0.95t})^{99}\, dt.$$ Here the factor $0.95\cdot e^{-0.95t}$ is the density of the lifetime of the particular nickel, and the rest is the probability that all other coins have been eaten by time $t$. Multiply by 100 to get the probability that the last coin is a nickel. Remove the factor $(1-e^{-0.95t})^{99}$ in the integral to get the expected number of nickels surviving all dimes, etc.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.