3
$\begingroup$

So a valid state is when there are both $X$ and $Y$ in the roll sequence, and the lowest index of an $X$ is smaller than the biggest index of a $Y$.

In particular, if after $N$ rolls, there is no $X$ or no $Y$, this does not count as a success.

For example

$N = 5$, $X = 1$, $Y = 2$ (Roll dice 5 times, 1 appearing before 2)

  • 1 4 2 3 1

  • 2 1 3 4 2

I would like the formula such that we can calculate the probability given $N$, $p_X$ and $p_Y$.

The closest I got is this :

def prob(N,pX,pY):
    res = 0
    for i in range(0,N):
        res+=((1-pX)**i)*pX*(N-i-1)*pY
    return res
$\endgroup$
  • 2
    $\begingroup$ Is your condition fulfilled if (1) X appears, but not Y, or if (2) Y appears, but not X, or if (3) neither one appears? $\endgroup$ – Stephan Kolassa Aug 24 at 23:16
  • 1
    $\begingroup$ All 3 conditions are not fullfilled. X and Y should appear atleast once. $\endgroup$ – Bertb Aug 24 at 23:19
  • 2
    $\begingroup$ @MichaelChernick: given that $P(X)$ and $P(Y)$ are inputs, I do not expect the die to be six sided or fair. $\endgroup$ – Stephan Kolassa Aug 24 at 23:47
  • 1
    $\begingroup$ I'll assume the die rolls are independent, as die rolls typically are, and write up the answer for this case. Can we all please hold off on the close-voting until I'm done? Thanks! $\endgroup$ – Stephan Kolassa Aug 25 at 0:09
  • 1
    $\begingroup$ for large $N$ I think it should be $\frac{P(X)}{P(X)+P(Y)}$ $\endgroup$ – probabilityislogic Aug 25 at 0:16
5
$\begingroup$

Here you go:

$$ \sum_{k=1}^{N-1}(1-p_Y)^{k-1}p_Y\big(1-(1-p_X)^{N-k}\big). $$

I sure hope that makes you happy. probabilityislogic turned this into the following only-slightly-less-intimidating closed form:

$$ 1-(1-p_X)^{N-1}-p_X\big[(1-p_Y)^{N-1}-(1-p_X)^{N-1}\big]\frac{1-p_Y}{p_X-p_Y} \quad\text{if }p_X\neq p_Y $$

$$ 1-(1-p+Np)(1-p)^{N-1}\quad\text{if }p_X=p_Y=:p. $$ The first idea is that the probability of a "successful" outcome ("both $X$ and $Y$ are present in the roll, and an $X$ appears before the last $Y$") is equivalent to "both $X$ and $Y$ are present in the roll, and an $X$ appears after the first $Y$". The equivalence lies simply in counting from the back instead of from the front. (This just simplifies the summation indices above, you can easily work with the original formulation, it's just a little messier.)

Let's work with this equivalent formulation. It can be disentangled as:

  • there is some index $k\in\{1, \dots, N-1\}$ (this is what we sum over) such that:
  • there is no $Y$ for the $k-1$ first rolls (this is the $(1-p_Y)^{k-1}$ term) and
  • the $k$-th roll is $Y$ (with probability $p_Y$) and
  • there is at least one $X$ roll after that (this is the $\big(1-(1-p_X)^{N-k}\big)$ term: it's the complement of there being no $X$ in $N-k$ rolls).

The formula seems to work in simulations, where I played around with the nn, px and py parameters (in R):

nn <- 2
px <- .3
py <- .3

n_sims <- 1e4
n_x_before_y <- 0

for ( ii in 1:n_sims ) {
    roll <- sample(x=c("x","y","z"),size=nn,replace=TRUE,prob=c(px,py,1-px-py))
    if ( "x" %in% roll & "y" %in% roll) {
        if ( min(which(roll=="x"))<max(which(roll=="y")) ) {
            n_x_before_y <- n_x_before_y+1
        }
    }
}

n_x_before_y/n_sims


sum((1-py)^(0:(nn-2))*py*(1-(1-px)^((nn-1):1)))

if ( isTRUE(all.equal(px,py)) ) {
    cat(1-(1-px+nn*px)*(1-px)^(nn-1),"\n")
} else {
    cat(1-(1-px)^(nn-1)-px*((1-py)^(nn-1)-(1-px)^(nn-1))*(1-py)/(px-py),"\n")
}

This has been giving me the correct result, both for the sum form and for the closed form probabilityislogic proposed.

Of course, it does not matter whether the die is 3-, 6- or 27-sided - all we care about is the probabilities of the two events in question and "everything else", so for our purposes, we can collapse "everything else".

An interesting aspect that stumped me for a while is that the specific probabilities $p_X$ and $p_Y$ have a different impact for small and large $N$. If $N$ is small, e.g., $N=2$, then all we care is whether both $X$ and $Y$ are present in the roll at all. Conditional on that, $(X,Y)$ and $(Y,X)$ are equally likely, no matter how different $p_X$ and $p_Y$ are! But if $N$ grows, then both $X$ and $Y$ are more and more certainly present in the overall roll, and which one appears first depends of course on the ratio between $p_X$ and $p_Y$.

Overall, a nice little problem. Thanks!

$\endgroup$
  • 1
    $\begingroup$ note, you can simplify that formula a bit further by analytically evaluating the summation. The result is $$\frac{p_X}{p_Y+p_X}\left[1-(1-p_Y-p_X)^{N-1}\right] - (1-p_Y)^N\left[1-(1-\frac{p_X}{1-p_Y})^{N-1}\right]$$ The limit as $N\to\infty$ is $\frac{p_X}{p_Y+p_X}$ $\endgroup$ – probabilityislogic Aug 25 at 0:59
  • 1
    $\begingroup$ Ah, thank you. I was misled by "a symbol X appearing before symbol Y". I'll take a look and see whether I can salvage my idea, but only later today; I am a bit sleep-deprived. (Actually, I think I can simply turn everything around, counting from the back and exchanging $X$ and $Y$. Let me see...) $\endgroup$ – Stephan Kolassa Aug 25 at 6:57
  • 1
    $\begingroup$ @MichaelChernick: the conditioning is handled implicitly by the second term (there must be an $X$) and the third one (there must be a $Y$ later on). I did play around with conditioning first and then writing out the conditional probability, but I didn't get anywhere - this is what I mean in my second-to-last paragraph. $\endgroup$ – Stephan Kolassa Aug 25 at 6:59
  • 1
    $\begingroup$ I think if you allow the $k-1$ trials to include $Y$, your answer should account for the op's comment. Updating the expression gives $$1-(1-p_X)^{N-1} - p_X\left[(1-p_Y)^{N-1}-(1-p_X)^{N-1}\right]\frac{1-p_Y}{p_X-p_Y}$$ if $p_X\neq p_Y$ and value equal to $1-(1-p+Np)(1-p)^{N-1}$ if $p_X=p_Y=p$. In both cases the limiting value is $1$ as $N\to\infty$ (makes sense). note, posting as a comment because you essentially have the answer already. happy for you to copy this in if you want :) $\endgroup$ – probabilityislogic Aug 25 at 10:02
  • 1
    $\begingroup$ @probabilityislogic: if the first $k-1$ trials are allowed to include a $Y$, then the different events whose probability we sum over are not disjoint any more, so the sum would not be correct. Thanks for the updated closed form! $\endgroup$ – Stephan Kolassa Aug 25 at 10:07

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.