exercise:6d2d2af699: Difference between revisions
(Created page with "<div class="d-none"><math> \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}</math></div> The letters between Pascal and Fermat, which are often credited with having started probability theory, dealt mostly with the ''problem of points'' described in Exercise Exercise. Pascal and Fermat considered the problem...") |
No edit summary |
||
| Line 1: | Line 1: | ||
The letters between Pascal and Fermat, which are often credited with having started probability theory, dealt mostly with the ''problem of points'' described in Exercise [[exercise:D1d037085a |Exercise]]. Pascal and Fermat considered the problem of finding a fair division of stakes if the game must be called off when the first player has won <math>r</math> games and the second player has won <math>s</math> games, with <math>r < N</math> and <math>s < N</math>. Let <math>P(r,s)</math> be the probability that player A wins the game if he has already won <math>r</math> points and player B has won | |||
are often credited with having started probability theory, dealt mostly with the ''problem of | |||
points'' described in Exercise [[exercise:D1d037085a |Exercise]]. Pascal and Fermat considered the problem of | |||
finding a fair division of stakes if the game must be called off when the first player has won | |||
<math>r</math> games and the second player has won <math>s</math> games, with <math>r < N</math> and <math>s < N</math>. Let <math>P(r,s)</math> be the | |||
probability that player A wins the game if he has already won <math>r</math> points and player B has won | |||
<math>s</math> points. Then | <math>s</math> points. Then | ||
<ul><li> <math>P(r,N) = 0</math> if <math>r < N</math>, | |||
<ul style="list-style-type:lower-alpha"><li> <math>P(r,N) = 0</math> if <math>r < N</math>, | |||
</li> | </li> | ||
<li> <math>P(N,s) = 1</math> if <math>s < N</math>, | <li> <math>P(N,s) = 1</math> if <math>s < N</math>, | ||
| Line 18: | Line 8: | ||
<li> <math>P(r,s) = pP(r + 1,s) + qP(r,s + 1)</math> if <math>r < N</math> and <math>s < N</math>; | <li> <math>P(r,s) = pP(r + 1,s) + qP(r,s + 1)</math> if <math>r < N</math> and <math>s < N</math>; | ||
</li> | </li> | ||
</ul> and (1), (2), and (3) determine <math>P(r,s)</math> for <math>r \leq N</math> and <math>s \leq N</math>. Pascal | </ul> and (1), (2), and (3) determine <math>P(r,s)</math> for <math>r \leq N</math> and <math>s \leq N</math>. Pascal used these facts to find <math>P(r,s)</math> by working backward: He first obtained <math>P(N - 1,j)</math> for <math>j = | ||
used these facts to find <math>P(r,s)</math> by working backward: He first obtained <math>P(N - 1,j)</math> for <math>j = | N - 1,N - 2, \ldots, 0</math>; then, from these values, he obtained | ||
N - 1 | <math>P(N - 2,j)</math> for <math>j = N - 1, N - 2, \ldots, 0</math> and, continuing backward, obtained all the | ||
<math>P(N - 2,j)</math> for <math>j = N - 1 | values <math>P(r,s)</math>. Write a program to compute <math>P(r,s)</math> for given <math>N</math>, <math>a</math>, <math>b</math>, and <math>p</math>. | ||
values <math>P(r,s)</math>. Write a program to compute <math>P(r,s)</math> for given <math>N</math>, <math>a</math>, <math>b</math>, and <math>p</math>. | |||
{{alert-warning| Follow Pascal and you will be able to run <math>N = 100</math>; use recursion and you will | |||
not be able to run <math>N = 20</math>. | not be able to run <math>N = 20</math>.}} | ||
Revision as of 00:10, 13 June 2024
The letters between Pascal and Fermat, which are often credited with having started probability theory, dealt mostly with the problem of points described in Exercise Exercise. Pascal and Fermat considered the problem of finding a fair division of stakes if the game must be called off when the first player has won [math]r[/math] games and the second player has won [math]s[/math] games, with [math]r \lt N[/math] and [math]s \lt N[/math]. Let [math]P(r,s)[/math] be the probability that player A wins the game if he has already won [math]r[/math] points and player B has won [math]s[/math] points. Then
- [math]P(r,N) = 0[/math] if [math]r \lt N[/math],
- [math]P(N,s) = 1[/math] if [math]s \lt N[/math],
- [math]P(r,s) = pP(r + 1,s) + qP(r,s + 1)[/math] if [math]r \lt N[/math] and [math]s \lt N[/math];
and (1), (2), and (3) determine [math]P(r,s)[/math] for [math]r \leq N[/math] and [math]s \leq N[/math]. Pascal used these facts to find [math]P(r,s)[/math] by working backward: He first obtained [math]P(N - 1,j)[/math] for [math]j = N - 1,N - 2, \ldots, 0[/math]; then, from these values, he obtained
[math]P(N - 2,j)[/math] for [math]j = N - 1, N - 2, \ldots, 0[/math] and, continuing backward, obtained all the values [math]P(r,s)[/math]. Write a program to compute [math]P(r,s)[/math] for given [math]N[/math], [math]a[/math], [math]b[/math], and [math]p[/math].