Skip to main content
added 23 characters in body
Source Link
Adrian
  • 4.4k
  • 3
  • 24
  • 38

There is a fun way to answer this problem using martingales, and in particular using https://en.wikipedia.org/wiki/Optional_stopping_theorem. I first saw this trick in the book A First Look at Rigorous Probability Theory by Jeffrey S. Rosenthal, in the martingale chapter. (I don't have the book in front of me at the moment but I'll edit and add a page or equation number when I do.)

Imagine that at each time step $t$ a person arrives and places a bet on the outcome of the next coin toss. The payoff to their first bet is:

$\begin{equation} \begin{cases} -1 &\mbox{if toss } t \mbox{ is T} \\ +19 &\mbox{if toss } t \mbox{ is H} \\ \end{cases} \end{equation}$

If they are wrong (i.e. lose money) on this bet, they stop betting. Note that their net gain if they exit at this point is $-1$. If they are correct, they continue to betting on toss $t+1$ and receive the following payoff:

$\begin{equation} \begin{cases} +\frac{20}{19} &\mbox{if toss } t+1 \mbox{ is T} \\ -20 &\mbox{if toss } t+1 \mbox{ is H} \\ \end{cases} \end{equation}$

If they are wrong on this second bet, they stop betting. Again, note that their net gain if they exit at this point is (by design) $19-20 = -1$. If they were correct for this second bet, they proceed to betting on the outcome of toss $t+2$ and receive:

$\begin{equation} \begin{cases} -\frac{400}{19} &\mbox{if toss } t+2 \mbox{ is T} \\ +400 &\mbox{if toss } t+2 \mbox{ is H} \\ \end{cases} \end{equation}$

If they are incorrect, they exit with a net gain of $19 + \frac{20}{19} - \frac{400}{19} = -1$. If they are correct, everything stops: we have just seen a HTH sequence, and the person who started betting at the beginning of that sequence has just won $19 + \frac{20}{19} + 400 = 420.0526$.

Note that two people have started betting after this big winner: one person whose first bet was incorrect (they exit with $-1$), and a second person whose first bet was correct (they win $19$ but nothing more because the process stops).

Let $\tau$ denote the stopping time, and let $X_t$ denote the totalcumulative net amount won by all gamblers up untilto and including time $t$. Let $X_0 = 0$, and note that $X_t$ is a martingale because all bets are (by construction) fair, with an expected payoff of $0$. This will let us use https://en.wikipedia.org/wiki/Optional_stopping_theorem and in particular $\mathbf{E}[X_\tau] = \mathbf{E}[X_0] = 0$.

$X_\tau$ is the total amount won when we reach the stopping time. At this point $\tau - 3$ people will have lost their bets and exited with a net gain of $-1$, one person will have won $420.0526$, and we also have to account for the last two people who start betting after the winner. We have:

$\begin{equation} \mathbf{E}[X_\tau] = 0 = (\mathbf{E}[\tau]-3)*(-1) + 420.0526 + (-1) + 19 \end{equation}$

Which leads to $\mathbf{E}[\tau] = 420.0526 + 3 + 18 = 441.0526$, which agrees with the answers posted earlier.

There is a fun way to answer this problem using martingales, and in particular using https://en.wikipedia.org/wiki/Optional_stopping_theorem. I first saw this trick in the book A First Look at Rigorous Probability Theory by Jeffrey S. Rosenthal, in the martingale chapter. (I don't have the book in front of me at the moment but I'll edit and add a page or equation number when I do.)

Imagine that at each time step $t$ a person arrives and places a bet on the outcome of the next coin toss. The payoff to their first bet is:

$\begin{equation} \begin{cases} -1 &\mbox{if toss } t \mbox{ is T} \\ +19 &\mbox{if toss } t \mbox{ is H} \\ \end{cases} \end{equation}$

If they are wrong (i.e. lose money) on this bet, they stop betting. Note that their net gain if they exit at this point is $-1$. If they are correct, they continue to betting on toss $t+1$ and receive the following payoff:

$\begin{equation} \begin{cases} +\frac{20}{19} &\mbox{if toss } t+1 \mbox{ is T} \\ -20 &\mbox{if toss } t+1 \mbox{ is H} \\ \end{cases} \end{equation}$

If they are wrong on this second bet, they stop betting. Again, note that their net gain if they exit at this point is (by design) $19-20 = -1$. If they were correct for this second bet, they proceed to betting on the outcome of toss $t+2$ and receive:

$\begin{equation} \begin{cases} -\frac{400}{19} &\mbox{if toss } t+2 \mbox{ is T} \\ +400 &\mbox{if toss } t+2 \mbox{ is H} \\ \end{cases} \end{equation}$

If they are incorrect, they exit with a net gain of $19 + \frac{20}{19} - \frac{400}{19} = -1$. If they are correct, everything stops: we have just seen a HTH sequence, and the person who started betting at the beginning of that sequence has just won $19 + \frac{20}{19} + 400 = 420.0526$.

Note that two people have started betting after this big winner: one person whose first bet was incorrect (they exit with $-1$), and a second person whose first bet was correct (they win $19$ but nothing more because the process stops).

Let $\tau$ denote the stopping time, and let $X_t$ the total net amount won by all gamblers up until time $t$. Let $X_0 = 0$, and note that $X_t$ is a martingale because all bets are (by construction) fair, with an expected payoff of $0$. This will let us use https://en.wikipedia.org/wiki/Optional_stopping_theorem and in particular $\mathbf{E}[X_\tau] = \mathbf{E}[X_0] = 0$.

$X_\tau$ is the total amount won when we reach the stopping time. At this point $\tau - 3$ people will have lost their bets and exited with a net gain of $-1$, one person will have won $420.0526$, and we also have to account for the last two people who start betting after the winner. We have:

$\begin{equation} \mathbf{E}[X_\tau] = 0 = (\mathbf{E}[\tau]-3)*(-1) + 420.0526 + (-1) + 19 \end{equation}$

Which leads to $\mathbf{E}[\tau] = 420.0526 + 3 + 18 = 441.0526$, which agrees with the answers posted earlier.

There is a fun way to answer this problem using martingales, and in particular using https://en.wikipedia.org/wiki/Optional_stopping_theorem. I first saw this trick in the book A First Look at Rigorous Probability Theory by Jeffrey S. Rosenthal, in the martingale chapter. (I don't have the book in front of me at the moment but I'll edit and add a page or equation number when I do.)

Imagine that at each time step $t$ a person arrives and places a bet on the outcome of the next coin toss. The payoff to their first bet is:

$\begin{equation} \begin{cases} -1 &\mbox{if toss } t \mbox{ is T} \\ +19 &\mbox{if toss } t \mbox{ is H} \\ \end{cases} \end{equation}$

If they are wrong (i.e. lose money) on this bet, they stop betting. Note that their net gain if they exit at this point is $-1$. If they are correct, they continue to betting on toss $t+1$ and receive the following payoff:

$\begin{equation} \begin{cases} +\frac{20}{19} &\mbox{if toss } t+1 \mbox{ is T} \\ -20 &\mbox{if toss } t+1 \mbox{ is H} \\ \end{cases} \end{equation}$

If they are wrong on this second bet, they stop betting. Again, note that their net gain if they exit at this point is (by design) $19-20 = -1$. If they were correct for this second bet, they proceed to betting on the outcome of toss $t+2$ and receive:

$\begin{equation} \begin{cases} -\frac{400}{19} &\mbox{if toss } t+2 \mbox{ is T} \\ +400 &\mbox{if toss } t+2 \mbox{ is H} \\ \end{cases} \end{equation}$

If they are incorrect, they exit with a net gain of $19 + \frac{20}{19} - \frac{400}{19} = -1$. If they are correct, everything stops: we have just seen a HTH sequence, and the person who started betting at the beginning of that sequence has just won $19 + \frac{20}{19} + 400 = 420.0526$.

Note that two people have started betting after this big winner: one person whose first bet was incorrect (they exit with $-1$), and a second person whose first bet was correct (they win $19$ but nothing more because the process stops).

Let $\tau$ denote the stopping time, and let $X_t$ denote the cumulative net amount won by all gamblers up to and including time $t$. Let $X_0 = 0$, and note that $X_t$ is a martingale because all bets are (by construction) fair, with an expected payoff of $0$. This will let us use https://en.wikipedia.org/wiki/Optional_stopping_theorem and in particular $\mathbf{E}[X_\tau] = \mathbf{E}[X_0] = 0$.

$X_\tau$ is the total amount won when we reach the stopping time. At this point $\tau - 3$ people will have lost their bets and exited with a net gain of $-1$, one person will have won $420.0526$, and we also have to account for the last two people who start betting after the winner. We have:

$\begin{equation} \mathbf{E}[X_\tau] = 0 = (\mathbf{E}[\tau]-3)*(-1) + 420.0526 + (-1) + 19 \end{equation}$

Which leads to $\mathbf{E}[\tau] = 420.0526 + 3 + 18 = 441.0526$, which agrees with the answers posted earlier.

Source Link
Adrian
  • 4.4k
  • 3
  • 24
  • 38

There is a fun way to answer this problem using martingales, and in particular using https://en.wikipedia.org/wiki/Optional_stopping_theorem. I first saw this trick in the book A First Look at Rigorous Probability Theory by Jeffrey S. Rosenthal, in the martingale chapter. (I don't have the book in front of me at the moment but I'll edit and add a page or equation number when I do.)

Imagine that at each time step $t$ a person arrives and places a bet on the outcome of the next coin toss. The payoff to their first bet is:

$\begin{equation} \begin{cases} -1 &\mbox{if toss } t \mbox{ is T} \\ +19 &\mbox{if toss } t \mbox{ is H} \\ \end{cases} \end{equation}$

If they are wrong (i.e. lose money) on this bet, they stop betting. Note that their net gain if they exit at this point is $-1$. If they are correct, they continue to betting on toss $t+1$ and receive the following payoff:

$\begin{equation} \begin{cases} +\frac{20}{19} &\mbox{if toss } t+1 \mbox{ is T} \\ -20 &\mbox{if toss } t+1 \mbox{ is H} \\ \end{cases} \end{equation}$

If they are wrong on this second bet, they stop betting. Again, note that their net gain if they exit at this point is (by design) $19-20 = -1$. If they were correct for this second bet, they proceed to betting on the outcome of toss $t+2$ and receive:

$\begin{equation} \begin{cases} -\frac{400}{19} &\mbox{if toss } t+2 \mbox{ is T} \\ +400 &\mbox{if toss } t+2 \mbox{ is H} \\ \end{cases} \end{equation}$

If they are incorrect, they exit with a net gain of $19 + \frac{20}{19} - \frac{400}{19} = -1$. If they are correct, everything stops: we have just seen a HTH sequence, and the person who started betting at the beginning of that sequence has just won $19 + \frac{20}{19} + 400 = 420.0526$.

Note that two people have started betting after this big winner: one person whose first bet was incorrect (they exit with $-1$), and a second person whose first bet was correct (they win $19$ but nothing more because the process stops).

Let $\tau$ denote the stopping time, and let $X_t$ the total net amount won by all gamblers up until time $t$. Let $X_0 = 0$, and note that $X_t$ is a martingale because all bets are (by construction) fair, with an expected payoff of $0$. This will let us use https://en.wikipedia.org/wiki/Optional_stopping_theorem and in particular $\mathbf{E}[X_\tau] = \mathbf{E}[X_0] = 0$.

$X_\tau$ is the total amount won when we reach the stopping time. At this point $\tau - 3$ people will have lost their bets and exited with a net gain of $-1$, one person will have won $420.0526$, and we also have to account for the last two people who start betting after the winner. We have:

$\begin{equation} \mathbf{E}[X_\tau] = 0 = (\mathbf{E}[\tau]-3)*(-1) + 420.0526 + (-1) + 19 \end{equation}$

Which leads to $\mathbf{E}[\tau] = 420.0526 + 3 + 18 = 441.0526$, which agrees with the answers posted earlier.