exercise:18da878882: Difference between revisions

From Stochiki
(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> A coin is tossed repeatedly. We are interested in finding the expected number of tosses until a particular pattern, say B = HTH, occurs for the first time. If, for example, the outcomes of the tosses are HHTTHTH we say that the pattern B has occ...")
 
No edit summary
 
Line 5: Line 5:
\newcommand{\secstoprocess}{\all}
\newcommand{\secstoprocess}{\all}
\newcommand{\NA}{{\rm NA}}
\newcommand{\NA}{{\rm NA}}
\newcommand{\mathds}{\mathbb}</math></div> A coin is tossed repeatedly.  We are
\newcommand{\mathds}{\mathbb}</math></div> A coin is tossed repeatedly.  We are interested in finding the expected number of tosses until a particular pattern, say B = HTH, occurs for the first time.  If, for example, the outcomes of the tosses are HHTTHTH we say that the pattern B has occurred for the first time after 7 tosses.  Let <math>T^B</math> be the time to obtain pattern B for the first time.  Li<ref group="Notes" >S-Y. R. Li, “A Martingale Approach to the Study of Occurrence of Sequence Patterns in Repeated Experiments,'' ''Annals of Probability,'' vol. 8 (1980), pp. 1171--1176.</ref> gives the following method for determining <math>E(T^B)</math>. We are in a casino and, before each toss of the coin, a gambler enters, pays 1 dollar to play, and bets that the pattern B = HTH will occur on the next three tosses.  If H occurs, he wins 2 dollars and bets this amount that the next outcome will be T.  If he wins, he wins 4 dollars and bets this amount that H will come up next time.  If he wins, he wins 8 dollars and the pattern has occurred.  If at any time he loses, he leaves with no winnings. Let A and B be two patterns.  Let AB be the amount the gamblers win who arrive while the pattern A occurs and bet that B will occur. For example, if A = HT and B = HTH then AB = 2 + 4 = 6 since the first gambler bet on H and won 2 dollars and then bet on T and won 4
interested in finding the expected number of tosses until a particular pattern,
dollars more. The second gambler bet on H and lost. If A = HH and B = HTH, then AB = 2 since the first gambler bet on H and won
say B = HTH, occurs for the first time.  If, for example, the outcomes of the
but then bet on T and lost and the second gambler bet on H and won. If A = B = HTH then AB = BB = 8 + 2 = 10.
tosses are HHTTHTH we say that the pattern B has occurred for the first time
after 7 tosses.  Let <math>T^B</math> be the time to obtain pattern B for the first
time.  Li<ref group="Notes" >S-Y. R. Li, “A Martingale Approach to the Study of
Occurrence of Sequence Patterns in Repeated Experiments,'' ''Annals of
Probability,'' vol. 8 (1980), pp. 1171--1176.</ref> gives the following method for
determining <math>E(T^B)</math>.  
We are in a casino and, before
each toss of the coin, a gambler enters, pays 1 dollar to play, and bets that
the pattern B = HTH will occur on the next three tosses.  If H occurs, he wins
2 dollars and bets this amount that the next outcome will be T.  If he wins, he
wins 4 dollars and bets this amount that H will come up next time.  If he wins,
he wins 8 dollars and the pattern has occurred.  If at any time he loses, he
leaves with no winnings.
Let A and B be two patterns.  Let AB be the amount the gamblers win who
arrive while the pattern A occurs and bet that B will occur.
For example, if A = HT and B = HTH then AB = 2 + 4 = 6 since
the first gambler bet on H and won 2 dollars and then bet on T and won 4
dollars more. The
second gambler bet on H and lost.
If A = HH and B = HTH, then AB = 2 since the first gambler bet on H and won
but then  
bet on T and lost and the second gambler bet on H and won. If A = B = HTH
then AB = BB = 8 + 2 = 10.


 
Now for each gambler coming in, the casino takes in 1 dollar. Thus the casino takes in <math>T^B</math> dollars.  How much does it
Now for each gambler coming in, the casino takes in 1 dollar.  
pay out? The only gamblers who go off with any money are those who arrive during the time the pattern B occurs and they win the amount BB.  
Thus the casino takes in <math>T^B</math> dollars.  How much does it
But since all the bets made are perfectly fair bets, it seems quite intuitive that the expected amount the casino takes in should equal  
pay out? The only gamblers who go off with any money are those who arrive
during the time the pattern B occurs and they win the amount BB.  
But since all the bets made are perfectly fair bets, it seems quite
intuitive that the expected amount the casino takes in should equal  
the expected amount that it pays out.  That is, <math>E(T^B)</math> = BB.
the expected amount that it pays out.  That is, <math>E(T^B)</math> = BB.


Since we have seen that for B = HTH,  BB = 10, the expected time to reach the pattern HTH for the first time is 10. If we had been
trying to get the pattern B = HHH, then  BB <math>= 8 + 4 + 2 = 14</math> since all the last three gamblers are paid off in this case. Thus the expected time to get the pattern HHH is 14. To justify this argument, Li used a theorem from the theory of martingales (fair games).


Since we have seen that for B = HTH,  BB = 10, the
We can obtain these expectations by considering a Markov chain whose states are the possible initial segments of the sequence HTH; these states are   
expected time to reach the pattern HTH for the first time is 10. If we had been
HTH, HT, H, and <math>\emptyset</math>, where <math>\emptyset</math> is the empty set.  Then, for this example, the transition matrix
trying to get the pattern B = HHH, then  BB <math>= 8 + 4 + 2 = 14</math> since all the
last three gamblers are paid off in this case. Thus the expected time
to get the pattern HHH is 14. To justify this argument, Li
used a theorem from the theory of martingales (fair games).
 
 
We can obtain these expectations by considering a Markov chain whose states
are the possible initial segments of the sequence HTH; these states are   
HTH, HT, H, and <math>\emptyset</math>, where
<math>\emptyset</math> is the empty set.  Then, for this example, the transition matrix
is
is


Latest revision as of 00:35, 16 June 2024

[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]

A coin is tossed repeatedly. We are interested in finding the expected number of tosses until a particular pattern, say B = HTH, occurs for the first time. If, for example, the outcomes of the tosses are HHTTHTH we say that the pattern B has occurred for the first time after 7 tosses. Let [math]T^B[/math] be the time to obtain pattern B for the first time. Li[Notes 1] gives the following method for determining [math]E(T^B)[/math]. We are in a casino and, before each toss of the coin, a gambler enters, pays 1 dollar to play, and bets that the pattern B = HTH will occur on the next three tosses. If H occurs, he wins 2 dollars and bets this amount that the next outcome will be T. If he wins, he wins 4 dollars and bets this amount that H will come up next time. If he wins, he wins 8 dollars and the pattern has occurred. If at any time he loses, he leaves with no winnings. Let A and B be two patterns. Let AB be the amount the gamblers win who arrive while the pattern A occurs and bet that B will occur. For example, if A = HT and B = HTH then AB = 2 + 4 = 6 since the first gambler bet on H and won 2 dollars and then bet on T and won 4

dollars more. The second gambler bet on H and lost. If A = HH and B = HTH, then AB = 2 since the first gambler bet on H and won but then bet on T and lost and the second gambler bet on H and won. If A = B = HTH then AB = BB = 8 + 2 = 10.

Now for each gambler coming in, the casino takes in 1 dollar. Thus the casino takes in [math]T^B[/math] dollars. How much does it pay out? The only gamblers who go off with any money are those who arrive during the time the pattern B occurs and they win the amount BB. But since all the bets made are perfectly fair bets, it seems quite intuitive that the expected amount the casino takes in should equal the expected amount that it pays out. That is, [math]E(T^B)[/math] = BB.

Since we have seen that for B = HTH, BB = 10, the expected time to reach the pattern HTH for the first time is 10. If we had been trying to get the pattern B = HHH, then BB [math]= 8 + 4 + 2 = 14[/math] since all the last three gamblers are paid off in this case. Thus the expected time to get the pattern HHH is 14. To justify this argument, Li used a theorem from the theory of martingales (fair games).

We can obtain these expectations by considering a Markov chain whose states are the possible initial segments of the sequence HTH; these states are HTH, HT, H, and [math]\emptyset[/math], where [math]\emptyset[/math] is the empty set. Then, for this example, the transition matrix is

[[math]] \bordermatrix{ &\mbox{HTH} & \mbox{HT} & \mbox{H} & \emptyset \cr \mbox{HTH} & 1 & 0 & 0 & 0 \cr \mbox{HT} & .5 & 0 & 0 & .5 \cr \mbox{H} & 0 & .5 & .5 & 0 \cr \emptyset & 0 & 0 & .5 & .5 }\ , [[/math]]

and if B = HTH, [math]E(T^B)[/math] is the expected time to absorption for this chain started in state [math]\emptyset[/math].


Show, using the associated Markov chain, that the values [math]E(T^B)[/math] = 10 and [math]E(T^B)[/math] = 14 are correct for the expected time to reach the patterns HTH and HHH, respectively.

Notes

  1. S-Y. R. Li, “A Martingale Approach to the Study of Occurrence of Sequence Patterns in Repeated Experiments, Annals of Probability, vol. 8 (1980), pp. 1171--1176.
Retrieved from "http://www.stochiki.com/w/index.php?title=exercise:18da878882&oldid=10408"