8
$\begingroup$

I am learning about the St Petersburg Paradox https://en.wikipedia.org/wiki/St._Petersburg_paradox - here is my attempt to summarize it:

  • A fair coin is tossed at each stage.
  • The initial stake begins at 2 dollars and is doubled every time tails appears.
  • The first time heads appears, the game ends and the player wins whatever is the current stake

As we can see, this game will have an expected reward of infinite dollars:

$$E(X) = \sum_{i=1}^{\infty} x_i \cdot p_i$$

$$E = \sum_{n=1}^{\infty} \frac{1}{2^n} \cdot 2^n = \frac{1}{2} \cdot 2 + \frac{1}{4} \cdot 4 + \frac{1}{8} \cdot 8 + \frac{1}{16} \cdot 16 + ... = 1 + 1 + 1 + 1 + ... = \sum_{n=1}^{\infty} 1 = \infty$$

The paradox is that even though the game has an infinite reward, in real life simulations, the game usually ends up with a finite reward. Although seemingly counterintuitive, this does seem logical. Even more, we can write computer simulations to see that large number of games will have finite rewards.

My question is about applying the insights of the St Petersburg Paradox to the first passage/first hitting times of Brownian Motions.

For example, consider the generic Brownian Motion:

$$Y_t = y_0 + \mu t + \sigma W_t$$

  • $Y_t$ is the value of the process at time $t$.
  • $y_0$ is the initial value of the process at time $t=0$.
  • $\mu$ is the drift rate, representing the deterministic trend.
  • $\sigma$ is the diffusion coefficient, scaling the Brownian motion $W_t$.
  • $W_t$ is a standard Brownian motion.

Now, consider the following situations (all with 1 dimensional continuous Brownian Motions):

  • Situation 1: An unconstrained Brownian Motion without Drift starting at $y=1$ at time $t=0$ : When will it be expected to first reach the point $y=5$?
  • Situation 2: A Brownian Motion without Drift starting at $y=1$ at time $t=0$ : If the stopping condition is when it reaches the point $y=5$ or $y=-5$ for the first time - when will it be expected to stop?
  • Situation 3: A Brownian Motion without Drift starting at $y=1$ at time $t=0$: If it can only go between the points $y=5$ or $y=-5$ , when will it be expected to first reach the point $y=3$? (i.e. if it reaches $y=-5$, it "bounces back" - however I am not sure how to mathematically encapsulate this "bouncing back" behavior)
  • Situation 4: How will the first passage times for Situations 1,2,3 change if we use Brownian Motions with Drift? (i.e. I know that the Inverse Gaussian Distribution is used here)
  • Situation 5: How will the first passage times for Situations 1,2,3,4 change if the Brownian Motion can only take discrete values? (i.e. a random walk)

Naively, using the logic from the St Petersburg Paradox, I could argue that the expected stopping times for the above 5 questions will all be infinite. That is, technically, there are very small probabilities that all these Brownian Motions can get stuck in an infinite loop of going back and forth, and never reach their stopping conditions. Thus, each of these infinitely long paths are weighted with infinitely small probabilities - and since there are an infinite number of these paths : the expected value would be infinite. Is the St Petersburg Paradox fundamentally at odds with the concept of First Passage/Hitting Times?

Yet this is clearly not the case. I can repeatedly simulate any of the above situations and see that all of them have finite stopping times (even though some of them might be long). However, now it seems to me that in theory, the more simulations you do, the probability of encountering a very long simulation increases, thus the average stopping time would statistically increase as the number of simulations increase?

Can someone please help me understand how to mathematically analyze the probability distributions and expected first passage/hitting times of the above situations? Why will some of them be finite and some of them be infinite? In situations where there is an infinite answer - is it wrong to just simulate the situation many times and take the expectation of the empirical distribution of these simulations as the average hitting time?

It seems to me that by virtue of the St Petersburg Paradox, all hitting time distributions should be infinite - yet this is clearly not the case?

Note:

$\endgroup$
9
  • 2
    $\begingroup$ Situation 1 has an infinite expected time. 2 and 3 are finite (and there’s no difference with a discrete random walk, though drift does make a difference). The Saint Petersburg game has a finite payoff with probability 1, not merely “usually”. $\endgroup$ Feb 18 at 4:52
  • $\begingroup$ thank you! I think that any Brownian motion with drift also has finite times? $\endgroup$ Feb 18 at 4:53
  • $\begingroup$ btw even though some of the situations might be infinite ... they still have a probability distribution (i.e. probability distribution of hitting time)? $\endgroup$ Feb 18 at 4:54
  • $\begingroup$ Added comments to that effect. If the drift is the same direction as the barrier, the expected time becomes finite. If it’s away, it stays infinite and we lose the fact that it will cross the barrier with probability 1. Yes, they still have a distribution, it just is too far-tailed to have a mean (or in the case where it drifts away we get a nonzero probability of it being infinity, ie a discrete point mass added at infinity). $\endgroup$ Feb 18 at 4:55
  • $\begingroup$ thank you... I posted this question yesterday: math.stackexchange.com/questions/4864377/… . I was trying to understand why the first passage time follows an inverse gaussian to begin with ... $\endgroup$ Feb 18 at 4:56

3 Answers 3

6
$\begingroup$

The St Petersberg game and the first passage time to a barrier do have the similarity that in the first case, the mean payoff is infinite while the probability of an infinite payoff is zero, and in the second case (for a driftless random walk/brownian motion) the mean first passage time is infinite while the probability of it being infinite is zero.

In both cases the idea is the same. There is nonzero probability of unbounded large payoffs/passage times, and while they are increasingly unlikely as they get large, the probabilities don't go down fast enough for there to be a finite mean. In the first case the probability goes down like the inverse payoff (the payoff for lasting $n$ rounds is $2^n$ and the probability is $\frac{1}{2^{n}}$) and in the second case the probability goes down asymptotically as $\tau^{-3/2},$ as you can see from the inverse gaussian distribution in your other question. In order for there to be a finite mean, the probability would have to decay faster than inverse square.

When we add another barrier on the other side of the starting point in the random walk (say we start at zero and have barriers at $1$ and $-5$), the expected passage time is no longer infinite. Even though it is "possible" for the particle to meander between the barriers forever, we could even see in the one-barrier case that that doesn't contribute a positive probability. What changes with regard to the expected value is now there can't be arbitrarily long excursions away from the barrier (since there is another barrier on the other side that contains it). As we move the barrier at $-5$ further and further away from the starting point, to $-10$, to $-1000,$ to $-1000000,$ etc, the expected time diverges to infinity (and the probability that you will end by hitting the left barrier and not the right barrier at 1 goes to zero).

We could similarly alter the St. Petersberg game with a cap, which would render the expected value finite. For instance, if we said there could only be 30 rounds, then the mean payoff would be 31. (Note as a practical matter, 30 rounds is still rather fantastic, as the max payoff is 2^30 which is just a shade over a trillion dollars, albeit occuring with only a 2 in a trillion chance). Note if you paid 31 to play the game, you'd only come out ahead if you lasted 5 rounds, which only has a $1/32$ chance of happening, and only by 1 dollar at that. So still seems intuitively not a great deal, since we are still having some very unlikely very large payoffs contribute to that expected value.

When you add drift to the random walk, things change for the one barrier problem. If the drift is toward the barrier, the expected hitting time becomes finite. If it is away from the barrier then the expected time remains infinite and there is a nonzero probability that the particle never hits the barrier.

In answer to your last question what will happen if you simulate is that the empirical mean will keep increasing as you do more and more simulations, not stabilizing as usual. (And as this inherently involves arbitrarily large numbers if you keep going, you will certainly run into numerical difficulties and/or simulations that won't finish in a practical amount of time.)

$\endgroup$
8
  • $\begingroup$ thank you so much! is it possible to write mathematical formulas to demonstrate why some of these are finite and why some are infinite? $\endgroup$ Feb 18 at 16:50
  • $\begingroup$ @pnaxso There are too many different things to give a calculation for, is there any one in particular? $\endgroup$ Feb 21 at 3:08
  • $\begingroup$ @ spaceisdarkgreen: thank you for your reply! Perhaps you can pick some of them and choose whichever you like? $\endgroup$ Feb 23 at 4:51
  • $\begingroup$ @pnaxso For the two-barrier problem, say, starting at $0$, with barriers at $-a$ and $b$, there is probability 1 of crossing the barrier since it suffices to travel to the right an amount $(b-a)$ once. There is a duration $T$ such that the probability that the particle moves to the right $(b-a)$ by time $T$ is nonzero (e.g. in a discrete walk the probability of doing it in time $T=(b-a)$ is $1/2^{b-a}$). So by Borel-Cantelli / infinite monkeys+typewriters/whatever, the particle eventually crosses the barrier with probability 1. $\endgroup$ Feb 26 at 3:37
  • $\begingroup$ @pnaxso Once we have that, we can figure the probability it will end by hitting barrier at $b$ by Martingale considerations. If we play a fair game with stopping rule that we stop playing and walk away at the barriers, the optional stopping time theorem says we need to have expected earnings $0$, i.e. $bP(b) - a(1-P(b)) = 0,$ which gives $P(b) = a/(a+b).$ $\endgroup$ Feb 26 at 3:42
1
+25
$\begingroup$

Others have commented on the technical details of random walks and brownian motions, but IMHO the OP's main confusion seems to be in this sentence:

Thus, each of these infinitely long paths are weighted with infinitely small probabilities - and since there are an infinite number of these paths : the expected value would be infinite.

This logic is like saying $\frac{1}{\infty} \times \infty = \infty$ (or perhaps $\frac{1}{\infty} \times \infty \times \infty = \infty$) when in fact it can be pretty much anything.

Lets say you play a modified St Pete game where the payoff after $n$ flips is $a_n$. Then the expected value is

$$ E = \sum_{n=1}^{\infty} {1 \over 2^n} \times a_n $$

The $a_n$'s can diverge to $\infty$ ("infinitely large payout"), but the sum can still be finite, e.g. when $a_n = (1.5)^n$, even though you might think "there is always an infinitely small chance to have infinite payout". There is no mystery to this at all. This expected value is an infinite sum and just like any infinite sum it can converge or diverge.

Perhaps you are taking the literal meaning of "expectation", as in, if the expected value is infinite you "expect" to get infinite dollars, so you're surprised when you don't? Similarly in those random walk problems with infinite hitting time, you "expect" to wait forever (i.e. never hit)? That's not what an infinite expected value mean.

$\endgroup$
3
  • $\begingroup$ thank you so much for your answer! Do you know how to calculate the expected hitting times for any of the situations I described? $\endgroup$ Feb 25 at 1:43
  • $\begingroup$ Divergence occurs for some $a_n\in o(2^n)$, e.g. $2^n/n$. Famously, no divergent series are "extremal", nor are any convergent ones. It may be best to focus the answer on a sufficient condition for convergence. $\endgroup$
    – J.G.
    Feb 25 at 2:35
  • $\begingroup$ @J.G. - thanks for pointing out my mistake! Fixed with a simpler example. $\endgroup$
    – antkam
    Feb 25 at 2:50
1
$\begingroup$

As others have noted, your main confusion seems to be that an infinite sum can have either a finite answer or an infinite answer depending on the specifics.

Finite example: If you make $n$ dollars for $n$ heads, you get $\sum_{n=1} n/2^n=1/2+2/4+3/8+4/16\dots=2$

Infinite example: If you make $2^n$ for $n$ heads, you get $\sum_{n=1} 2^n/2^n=1+1+1+\dots\rightarrow \infty$.

Both of them have some possibility of making arbitrarily large amounts of money, but the first example has the payouts increase in size slowly enough that it doesn’t matter.

Standard approaches to the St. Petersburg paradox are that super large $10^{30}$ payouts are infeasible and so meaningless and should be ignored and that after a certain point, you have enough money to satisfy your needs, so more money doesn’t actually matter.

For your Brownian motion examples, it’s well known that if you start at $0$ and stop when you hit $+a$ or $-b$, then it’ll take $ab$ steps on average. This makes sense because half the time you move up, half the time you move down, and $ab=1+(a-1)(b+1)/2+(a+1)(b-1)/2$. You could derive this in the first place using that $Y$ and $Y^2-t$ are martingales.

Having no bottom is like letting $b$ go to negative infinity, so in expectancy, you take infinite time to stop.

Stopping at $\pm 5$ takes $25$ steps on average.

If you pretend that going through $-5$ just keeps going, then you need to stop at $+3$ and it’s reflection $-5-(3+5)=-13$, so this takes an average of $3\times13=39$ steps.

Drift makes everything much more complicated.

Brownian motion with variance $1$ per unit time and discrete random walks of step $1$ have all the same dynamics (as long as your stopping points are integers). This is because both $Y$ and $Y^2-T$ are martingales, so all the same math that you would use to derive stopping times applies to both of them.

$\endgroup$

You must log in to answer this question.

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