Sheldon Ross 10: Exercise 3.23

Sheldon Ross 10 Exercise 3.23_coins pattern-01.jpg

Question: A coin having probability p of coming up heads is successively flipped until two of most recent three flips are heads. Let N denote the number of flips. (Note that the first two flips are heads, then N = 2.) Find E[N].


Analytical Solution

We will look at this problem in steps. Firstly let break this problem. Considering what the problem asks about obtaining two heads out of the last three trials. If we think about it, we do not have anything to say or predict unless a head occurs at-least once. This means that the E[N] is dependent on the first occurrence of the head and the first position of H is distributed as a geometric random variable.

If the first occurrence of the heads can be denoted by H1, then the next two ones could be

  • H H
  • T T
  • H T
  • T H

Since the iterations could theoretically go on forever, we need to observe the system from the standpoint of what the next outcomes are when we affix position of the first time the event happens. This means that E[N] can be found by conditioning on the next two flips given that we found a starting point H1

E[N] = E[ N|H1 ]

⇒ E[ N|H1 ] = E[ N|H1, T T] P{ T, T } + E[ N|H1, H, T] P{ H, T } + E[ N|H1, T, H] P{ T, H } + E[ N|H1, H, H] P{ H, H }

⇒ E[ N|H1 ] = E[ N|H1, T T] q2 + E[ N|H1, H, T] p q + E[ N|H1, T, H] q p + E[ N|H1, H, H] p2

We can examine each of expectations from the above step to simplify further.

  • E[ N|H1, T T]
    • Here, the two successive terms after the first head are both tails
    • This term then becomes H+ 2 + E[N]
  • E[ N|H1, H, T]
    • Since we have the two required heads here, the number becomes H1 + 1
  • E[ N|H1, T, H]
    • Since we have the two required heads here, the number becomes H1 + 2
    • the +2 being the case because the second trial after the first occurrence is heads
  • E[ N|H1, H, H]
    • Since we have both the heads, this would also be the H1 + 1

⇒ E[ N|H1 ] = (H+ 2 + E[N]) q2 + (H1 + 1) p q + (H1 + 2) q p + (H1 + 1) p2

⇒ E[E[ N|H1 ]] = E[(H+ 2 + E[N])] q2 + E[(H1 + 1)] p q + E[(H1 + 2)] q p + E[(H1 + 1)] p2

⇒ E[ N ] = (H+ 2 + E[N]) q2 + (H1 + 1) p q + (H1 + 2) q p + (H1 + 1) p2

⇒ E[ N ] = ( 1p + 2 + E[N]) q2 + (1p+ 1) p q + (1p + 2) q p + (1p + 1) p2

In order to simplify, use the relation p + q = 1 and we end up with the following

⇒ E[ N ] = (2 + 2q + q2p)(1 – q2)


Simulation Solution

The simulation needs some tweaks as in starting with a padded list so that the first iteration of the triplet check has a length of 3. The code is presented below. Drop me a line if you have any questions. The results are also shown as a plot right below.

Some observations to be made.

  • Due to the nature of the problem, see that there a great skewness to the simulation (which is the first plot).
  • The second plot is the theoretical distribution of the expected value
    • the expected value jumps to infinity as the q approaches 1 ( or p approaches 0)

 


Code

This time I have made all the coding in Mathematica. The function called randomizer is purely for aesthetic purposes and takes a number and randomizes its value around the actual value so that we do not get the clumped together.

ClearAll[randomizer];

randomizer[number_, percentage_ : 1] :=
    number + RandomReal[0.01 percentage {-number, number}];

Module[{data},
  data = KeySort@
      Association@
          Table[
            {p ->
                Module[{megaList = {}},
                  Module[{list = {0} ~ Join ~ RandomChoice[{p, 1 - p} -> {0, 1}, 2]},
                    While[True,
                      If[Count[list[[-3 ;; -1]], 1] == 2,
                        AppendTo[megaList, list]; Break[],
                        AppendTo[list, RandomChoice[{p, 1 - p} -> {0, 1}]]]]
                  ]; & /@ Range[1000];
                  Length /@ megaList
                ]}
            , {p, 0.05, 0.80, 0.05}];

  DistributionChart[
    randomizer[#, 5] & /@ # & /@ data,
    ChartLabels -> Keys@data,
    ChartElementFunction -> "PointDensity",
    ImageSize -> 788,
    GridLines -> {None, Mean /@ (Values@data)},
    AspectRatio -> 1,
    PlotRange -> {All, All}
  ]
]

End of the post 😀


.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.