10
$\begingroup$

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?

**

If it helps, I can provide some simulation data. 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$)

$\endgroup$
  • $\begingroup$ Hi regarding the coin selection process. Is it random in the way that I "uniformly" draw from the bag of coins left, or do I choose a coin A or B using a bernoulli trial of probability 1/2 ? $\endgroup$ – TheBridge Nov 26 '13 at 9:30
  • $\begingroup$ @TheBridge It's random in the sense that we uniformly draw from the bag of coins without considering the type of coin. For example, if we have 100 dimes and 567 nickels, we'd draw a dime with probability $\frac{100}{667}$. $\endgroup$ – Harrison Nov 26 '13 at 9:53
  • $\begingroup$ Ok that makes the problem more complex and more interesting ;-) $\endgroup$ – TheBridge Nov 26 '13 at 11:49
  • $\begingroup$ @TheBridge Thanks! I'm of course glad to hear that this is an interesting problem. $\endgroup$ – Harrison Nov 26 '13 at 15:14
  • $\begingroup$ Sounds like a Markov process... the setup is probably a mess. $\endgroup$ – vonbrand Feb 6 '14 at 0:16
1
$\begingroup$

The setting is ripe for Poissonization... First consider the path followed by the system, that is, denoting by $X$ the number of coins of type A left and by $Y$ the number of coins of type B left, the set of states visited by the process $(X,Y)$.

Assume that $(X,Y)=(x,y)$. One draws a coin of type A with probability $x/(x+y)$ and the machine eats it with probability $$a=1-p_A,$$ hence $(X,Y)$ moves to $(x-1,y)$ in one step with probability $ax/(x+y)$. Likewise, $(X,Y)$ moves to $(x,y-1)$ in one step with probability $by/(x+y)$, where $$b=1-p_B,$$ otherwise $(X,Y)$ stays at $(x,y)$ in one step. Thus, the next state visited by $(X,Y)$ is $(x-1,y)$ or $(x,y-1)$ with probabilities proportional to $(ax)$ and $(by)$ respectively.

Here is a process in continuous time with the same paths. Assume that each coin $i$ of type A has a lifetime $T_i$, exponential with parameter $a$, and that each coin $j$ of type B has a lifetime $S_j$, exponential with parameter $b$. All the lifetimes are independent. At any given time, assuming that $(x,y)$ coins are still alive, the next coin to die is of type A with probability proportional to $(ax)$ and of type B with probability proportional to $(by)$.

Thus, both processes starting from $(x,y)$ hit the line $Y=0$ (no coin of type B left) before hitting the line $X=0$ (no coin of type A left) when $T\gt S$, with $$ T=\max\{T_i\mid1\leqslant i\leqslant x\},\qquad S=\max\{S_j\mid1\leqslant j\leqslant y\}. $$ To compute $P(T\gt S)$, note that $P(S_j\lt t)=1-\mathrm e^{-bt}$ for every $t\gt0$ and every $j$, hence $$P(S\lt t)=(1-\mathrm e^{-bt})^y.$$ Likewise, $$P(T\lt t)=(1-\mathrm e^{-at})^x.$$ This allows to compute the density of $T$, which yields $$ P(T\gt S)=\int_0^\infty xa\mathrm e^{-at}(1-\mathrm e^{-at})^{x-1}(1-\mathrm e^{-bt})^y\mathrm dt. $$ Equivalent formulas are $$ P_{x,y}(\text{last coin of type A})=\int_0^1 x(1-u)^{x-1}(1-u^{b/a})^y\mathrm du, $$ and $$ P_{x,y}(\text{last coin of type A})=\int_0^1(1-(1-u^{1/x})^{b/a})^y\mathrm du. $$ The first example in the question is when $x=y=100$, $a=0.9$, $b=0.95$, then $P(\text{last coin of type A})\approx0.565953$.

The second example in the question is when $x=82$, $y=432$, $a=0.25$, $b=0.95$, then $P(\text{last coin of type A})\approx0.999634$.

One can continue with this approach to get the distribution of the number of coins at the end and of the number of times one places a coin in the machine. A useful remark to do so is that the continuous time processes $(X_t)$ and $(Y_t)$ describing the numbers of coins of each type still alive at time $t$ are actually independent, $X_t$ jumping from state $x$ to state $x-1$ at rate $(ax)$ and $Y_t$ jumping from state $y$ to state $y-1$ at rate $(by)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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