19
$\begingroup$

Zeus has decreed that Sisyphus must spend each day removing all the rocks in a certain valley and transferring them to Mount Olympus. Each night, each rock Sisyphus places on Mount Olympus is subject to the whims of Zeus: it will either be vaporized (with probability 10%), be rolled back down into the valley (with probability 50% ), or be split by a thunderbolt into two rocks that are both rolled down into the valley (with probability 40%). When the sun rises, Sisyphus returns to work, delivering rocks to Olympus. At sunrise on the first day of his punishment, there is only one rock in the valley and there are no rocks on Mount Olympus. What is the probability that Sisyphus must labor forever?

I tried approaching this problem as a random walk, but the fact that if Sisyphus has more than one rock in the valley then there is a chance of increasing the number of rocks by more than one is throwing me off. Does anyone have any insight as to how to approch this kind of problem? Thanks!

$\endgroup$

2 Answers 2

Reset to default
20
$\begingroup$

This is a Galton-Watson process with offspring distribution having the probability generating function $P(s) = \frac1{10} + \frac12 s+\frac25 s^2$. The mean of the offspring distribution is $$\mu := P'(1) = \frac{13}{10} > 1, $$ and hence the extinction probability is the unique solution to $P(s)=s$ in $[0,1)$. As the solutions to $\frac1{10} + \frac12 s+\frac25 s^2=s$ are $s=\frac14$ and $s=1$, it follows that the probability of no extinction is $1-\frac14=\frac34$.

$\endgroup$
2
  • $\begingroup$ If I am not mistaken this also tells you that only the ratio of the splitting probability to the vaporizing probability matters, which is interesting to me. It is almost like adding a holding time to a simple asymmetric random walk. $\endgroup$
    – Ian
    May 30 at 18:20
  • 1
    $\begingroup$ Filling in the details: $P(s)=p+(1-(r+1)p)s+rps^2,P'(1)-1=1-(r+1)p+2rp-1=(r-1)p$ (sign only depends on $r-1$ not explicitly on $p$). Then $P(s)-s=p-(r+1)ps+rps^2=0$ which can be divided through by $p$ to get $1-(r+1)s+rs^2=0$. $\endgroup$
    – Ian
    May 30 at 18:28
0
$\begingroup$

Is this a trick question, and the answer is zero?

There is a non-zero probability every day that all rocks will be vaporized, however many there are (0.1^n). And "forever" implies he will eventually get lucky.

$\endgroup$
3
  • 2
    $\begingroup$ The problem is that the probability that everything gets vaporized at time $t$ ($t=1,2,\dots$) is not just $0.1^t$, it is $0.1^{N(t)}$ where $N$ is the number on the mountain now. And $N(t)$ can be potentially as large as $2^{t-1}$. $\endgroup$
    – Ian
    May 30 at 18:07
  • $\begingroup$ @Ian Isn't that only a "problem" for workers with finite lifetimes? 0.1^(2^t-1) is still greater than zero. To assign a non-zero probability to "labor forever" don't you need to show that there is a way for the probability of all stones vanishing overnight to become real zero not just close to zero? $\endgroup$
    – Darren Cook
    May 30 at 19:19
  • 4
    $\begingroup$ This case where each rock can do one of three different things independently is somewhat complicated to think about explicitly, so consider a simpler case, where everything dies with probability $p^N$ and otherwise everything doubles. Then the probability to work for at least $t$ days is $\prod_{n=1}^t (1-p^{2^{n-1}})$. This product does not go to $0$ as $t$ gets large. The routine method to prove that is to take the logarithm, linearize the logarithm, and then use the ratio test. $\endgroup$
    – Ian
    May 30 at 19:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .