2
$\begingroup$

I understand the basics of conditional probability. Intuitively it should be possible to calculate some form of average for a simple conditional probability series. In the following example:

There is a bag with 10 marbles (1 red and 9 blue), on average how many blue marbles would one draw from the bag before a red one is drawn?

10% of the time it will be no marbles, because $\frac{1}{10}$ will be red.

I think I can work out the probability of drawing $n$ blue balls: $P(\{n\ blue\}) = \frac{9}{10} \times \frac{9-1}{10-1} \times \cdots \times \frac{9-n}{10-n}$

Now I can work out any desired probability, say 50%: $$0.5 = P(\{n\ blue\}), \therefore n=5$$

Does this 50% equate to some typical case? Or how would I work out the typical case for this series?

I wrote some python code to find the mean of 100'000 simulations of this, and got an answer of approximately 4.5. Which is not what I calculated.

$\endgroup$
1
  • 1
    $\begingroup$ The problem you are solving far exceeds basic conditional probabilities. This is a problem from the subject called Markov Chains (AKA Random Walks). Have a look at the classical problem called Gambler's ruin. By googling you can find tons of courses that explain this problem in detail and how to solve it $\endgroup$ Commented Oct 2, 2020 at 15:44

2 Answers 2

1
$\begingroup$

Let $A_n$ be a random variable, describing how many draws you will have to make until you draw a red marble, given that there are still $n$ blue marbles left in the bag. We can write a recursive relation between this random variable and the previous one:

$$ A_n = \begin{cases} 0, \;\;\;\;\;\; p = \frac{1}{n+1} \\ A_{n-1} + 1, \; p = \frac{n}{n+1} \end{cases} $$

The relationship literally says that if we draw a red one (with probability 1/n+1), we will need 0 draws, and if we draw a blue one, then we have already made 1 draw, and we now have to solve another problem of the same type, but now there is 1 less blue marble.

What we actually want is the expected number of draws we will need to make. Let's call it $E_n$. Thus

$$E_n = \langle A_n \rangle = 0 \cdot \frac{1}{n+1} + \langle A_{n-1} + 1\rangle \frac{n}{n+1} $$

So, we need to solve the recursive problem

$$E_n = (E_{n-1} + 1) \frac{n}{n+1}$$

Together with the initial condition

$$E_0 = \langle A_0 \rangle = 0$$

Plugging this into a basic python script

E = [0]
for i in range(1, 10):
    E += [i/(i+1) * (1 + E[-1])]
    
print(E)

Yields the first 10 values of this series: [0, 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5]

So, if there is 1 red and 9 blue marbles, the correct answer is $E_9 = 4.5$

Now, it seems fascinating that this complicated looking recursive relationship actually looks like an arithmetic progression. I am not quite sure why yet, but I will have a closer look and finish this answer later

EDIT: I confirm that the relationship is indeed the arithmetic progression. One can easily verify that the recursive relation is satisfied by $E_n = n/2$, and since the problem is completely fixed by the initial condition, it is the only possible solution.

The extremely weird thing about this recursive relation is that it is only linear if the initial condition $E_0 = 0$. For all other initial conditions it the sequence is non-linear

$\endgroup$
1
  • $\begingroup$ Thank you so much, this was very clearly explained. $\endgroup$
    – Morgoth
    Commented Oct 2, 2020 at 20:14
0
$\begingroup$

So let $N$ be the number of blue marbles drawn. Firstly, your expression for $\Pr(N)$ is wrong. Remember that to stop drawing marbles you must draw a red one. So the last probability in your product must be the probability of drawing a red marble, which gives

$$ \Pr(N) = \frac{9}{10}\frac{9-1}{10-1}\dots\frac{9-N+1}{10-N+1}\frac{1}{10-N} $$

The value of $N$ for which $\Pr(N)=0.5$ doesn't mean much to me. You can try to compute the expected value of $N$, but I don't know if you'll be able to do this analytically.

One alternative I can think of is to compute the most likely $N$, that is, the one for which $\Pr(N)$ is maximized. In fact, due to the product in the expression for $\Pr(N)$ and the fact that logarithms are monotonically increasing, we can equivalently try to maximize $\log\Pr(N)$ which is much easier. We have

$$ \log\Pr(N) = \sum_{n=0}^{N-1}\log(9-n) -\sum_{n=0}^{N}\log(10-n) $$

Setting the derivative to 0,

$$ 0 = -\sum_{n=1}^{N-1}\frac{1}{9-n} + \sum_{n=1}^{N}\frac{1}{10-n} $$

Then

$$ 0 = -\sum_{n=1}^{N-1}\frac{1}{(9-n)(10-n)} + \frac{1}{10-N} $$

Unfortunately I'm not sure how to proceed analytically from here. What you can do instead is estimate the most likely $N$ by stochastic gradient descent. That is,

  1. Start by guessing $N$
  2. Repeat until convergence:
    1. Compute the derivative of $\log\Pr(N)$ as $\delta = \frac{1}{10-N} - \sum_{n=1}^{N-1}\frac{1}{(9-n)(10-n)}$
    2. Update your estimate of $N$ with an exponential weighted average: $N\leftarrow N+\alpha\delta$, where $\alpha\in(0,1)$ is the step size.
$\endgroup$
2
  • 1
    $\begingroup$ Cool approach. However, I'm not sure that in its current state it answers the problem. The most likely number of draws is not the same as the expected number of draws $\endgroup$ Commented Oct 2, 2020 at 15:57
  • $\begingroup$ Yes, that's true. But he asked for the typical case, so I thought this would be better than expected value if anything. $\endgroup$
    – harwiltz
    Commented Oct 2, 2020 at 22:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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