{"id":393,"date":"2025-04-30T16:59:14","date_gmt":"2025-04-30T16:59:14","guid":{"rendered":"https:\/\/renegrothmann.de\/?p=393"},"modified":"2025-06-30T16:43:25","modified_gmt":"2025-06-30T16:43:25","slug":"average-waiting-times","status":"publish","type":"post","link":"https:\/\/renegrothmann.de\/?p=393","title":{"rendered":"Average Waiting Times and 42"},"content":{"rendered":"\n

Let us start with a simple question. How long does it on average take to throw two times 6 in a row when throwing dice? I have treated average waiting times in one of the examples for Euler Math Toolbox (see here<\/a>). But I want to treat more examples for sequences of random numbers in this posting.<\/p>\n\n\n\n

The probability s(n) to get two consecutive 6 for the first time exactly after n throws can only be expressed recursively. So the usual way to compute the average waiting time as in infinite sum of n*s(n) is not really feasible.<\/p>\n\n\n\n

For the more simple waiting for a single 6, this approach can be used. We have for the probability to get the first 6 after n throws<\/p>\n\n\n\n

s(n) = \\left(\\frac56\\right)^{n-1} \\frac16<\/pre><\/div>\n\n\n\n
Using a well-known formula (which we do not explain here), we get<\/p>\n\n\n\n
\\sum_{n=1}^\\infty n \\left(\\frac56\\right)^{n-1} \\frac16 = 6<\/pre><\/div>\n\n\n\n
Another idea is to compute the average waiting time for two consecutive 6 by computing the average distance of two consecutive 6 in a very large sequence of dice throws This gets complicated due to the fact that there might also be 3 consecutive 6. For the simple waiting for a 6, the average distance between to 6 is obviously 6. So, this case would be easy.<\/p>\n\n\n\n
The most simply idea for waiting times is to represent the dice throws by two states.<\/p>\n\n\n\n
    \n
  • S1: We have just thrown a 6<\/li>\n\n\n\n
  • S2: We have just thrown any other number<\/li>\n<\/ul>\n\n\n\n
    Now, throwing dice is a game that is in one of these states at each point, and switches the states in a random way.<\/p>\n\n\n\n
      \n
    • From S1 to S2 we get with a probability of 5\/6. With probability 1\/6 the game exits from S1.<\/li>\n\n\n\n
    • From S2 to S1 we get with a probability of 1\/6. From S2 to S2 with a probability of 5\/6.<\/li>\n<\/ul>\n\n\n\n
      If W1 is the waiting time for the game to exit when it starts at S1, and W2 the exit time from S2, we get the following equations.<\/p>\n\n\n\n
      W_1 =1 +  \\frac56 W_2 \\\\ W_2 = 1 + \\frac16 W_1 + \\frac56 W_2<\/pre><\/div>\n\n\n\n
      The reasoning is that it takes one more step via S2 on average if we are in S1 to exit the game, and we have to take the detour via S2 on average 5\/6 of all times. This system of equations has the solution<\/p>\n\n\n\n
      W_1 = 36, \\quad W_2 = 42<\/pre><\/div>\n\n\n\n
      The answer to our question is like starting in S2. So the average waiting time is 42, a nice number.<\/p>\n\n\n\n
      If we know that the first throw is a 6, we only have to wait 36 throws on average. The reason for this improvement is that we have a chance of 1\/6 to throw a 6 with our second throw.<\/p>\n\n\n\n
      How would this trick work for a simple wait for a 6? The formula for the average waiting time is clearly<\/p>\n\n\n\n
      W = 1 + \\frac56W<\/pre><\/div>\n\n\n\n
      with the solution W=6. The idea is that we either throw a 6 immediately with probability 1\/6, or another number with probability 5\/6. So we are either done after one throw, or we have to wait another W+1 throws on average, i.e.<\/p>\n\n\n\n
      W = \\frac16 + \\frac56 (W+1) = 1 + \\frac56 W.<\/pre><\/div>\n\n\n\n
       The usual way to represent such problems is using a transition matrix, in our case<\/p>\n\n\n\n
      A = \\begin{pmatrix}0 & 5\/6 \\\\ 1\/6 & 5\/6\\end{pmatrix}<\/pre><\/div>\n\n\n\n
      and write the equations in matrix form as<\/p>\n\n\n\n
      W = {\\bf 1} + AW \\quad\\Longleftrightarrow (I - A)W = {\\bf 1}  <\/pre><\/div>\n\n\n\n
      For another example, we throw a coin (with sides 0 and 1) and ask for the first time when the sequence 1011 is expected to appear. We have the following states this time.<\/p>\n\n\n\n
        \n
      • S0 : We are starting to wait.<\/li>\n\n\n\n
      • S1 : We have a 1<\/li>\n\n\n\n
      • S10 : We have a 10<\/li>\n\n\n\n
      • S101 : We have a 101<\/li>\n<\/ul>\n\n\n\n
        We can only exit from S101. The transition probabilities are as follows.<\/p>\n\n\n\n
          \n
        • S0->S0 (throwing another 0) and S0->S1 (throwing a needed 1) : 1\/2.<\/li>\n\n\n\n
        • S1->S10 (throwing a needed 0) and S1->S1 (throwing another 1) : 1\/2<\/li>\n\n\n\n
        • S10 ->S0 (throwing a useless 0) and S10 -> S101 (throwing a needed 1) : 1\/2<\/li>\n\n\n\n
        • S101 -> S10 (throwing a 0, but still getting the sequence 10) : 1\/2<\/li>\n<\/ul>\n\n\n\n
          The transition matrix is as follows.<\/p>\n\n\n\n
          A = \\begin{pmatrix} \n1\/2 & 1\/2 & 0 & 0 \\\\ \n0 & 1\/2 & 1\/2 & 0 \\\\ \n1\/2 & 0 & 0 & 1\/2 \\\\ \n0 & 0 & 1\/2 & 0  \n\\end{pmatrix}<\/pre><\/div>\n\n\n\n
          Solving the system of equations yields<\/p>\n\n\n\n
          W = \\begin{pmatrix}18 \\\\ 16 \\\\14 \\\\ 8 \\end{pmatrix} <\/pre><\/div>\n\n\n\n
          Thus, the average waiting time turns out to be 18.<\/p>\n\n\n\n
          We can use a Monte-Carlo simulation to confirm this result. The following Java program simulates one million runs.<\/p>\n\n\n\n
          \/**
           * Determine the waiting time for a pattern of random numbers by Monte-Carlo
           * methods.
           *\/
          public class WaitingTimes
          {

              public static void main (String args[])
              {
                  \/\/ pattern to seek for
                  int pattern[] =
                  { 1, 0, 1, 1 };

                  \/\/ random numbers from 0 to range-1
                  int range = 2;

                  \/\/ number of repetitions of the experiment
                  int rep = 1000000;

                  \/\/ sum results for average
                  int sum = 0;

                  \/\/ size of the pattern
                  int size = pattern.length;

                  \/\/ space for the last size random numbers
                  int last[] = new int[size];

                  for (int k = 0; k < rep; k++)
                  \/\/ repeat experiment rep times.
                  {

                      \/\/ fill last[] with random numbers
                      for (int i = 0; i < size; i++)
                          last[i] = getrandom(range);

                      \/\/ count of needed random numbers
                      int count = size;

                      while (true)
                      \/\/ repeat adding a random number until pattern
                      \/\/ is found.
                      {

                          \/\/ check if pattern found
                          boolean found = true;
                          for (int i = 0; i < size; i++)
                              if (last[i] != pattern[i])
                              {
                                  found = false;
                                  break;
                              }
                          if (found) break;

                          \/\/ add a new random number.
                          for (int i = 0; i < size - 1; i++)
                              last[i] = last[i + 1];
                          last[size - 1] = getrandom(range);
                          count++;

                      }

                      \/\/ sum up for average
                      sum += count;
                  }

                  \/\/ pint average.
                  System.out.println((double) sum \/ rep);
              }

              static int getrandom (int range)
              {
                  return (int) (Math.random() * range);
              }

          }<\/pre>\n\n\n\n
          The result of one simulation was 18.020663.<\/p>\n\n\n\n
          Assume, you are playing coin throwing and got a score of +2 already, i.e., two more heads than tails. How long do you have to wait on average until you reach +3?<\/p>\n\n\n\n
          The answer is counter-intuitive. It seems that we are very likely to reach +3 soon. You have a chance of 1\/2 to reach it with one throw. But if you are like me, you can get very worried if you drop down in your score and it does not seem to go up ever again. After all, you were at +2 already, but you just seem to be unable to recover from a bit of bad luck. The fact of life is, however, that your average waiting time is infinite.<\/p>\n\n\n\n
          That does not mean that you cannot reach +3 ever. In fact, you might eventually. Mathematically, you reach it „almost certainly“.<\/p>\n\n\n\n
          But if you average the times on several tries, you will get ever bigger averages the longer you try. <\/p>\n\n\n\n
          Let us try a simulation in Java. For this, we will eventually have to give up after a given number of throws.<\/p>\n\n\n\n
          public class WaitingTimes
          {

              public static void main (String args[])
              {
                  int NMax = 1000000;
                  int Ntries = 100000;

                  double Sum = 0;
                  double Success = 0;

                  for (int i = 0; i < Ntries; i++)
                  {
                      int W = 2;
                      int n;
                      for (n = 1; n <= NMax; n++)
                      {
                          W = W + ((Math.random() < 0.5) ? -1 : 1);
                          if (W >= 3)
                          {
                              Success++;
                              break;
                          }
                      }
                      Sum += n;
                  }

                  System.out.println(\"Average : \" + (Sum \/ Ntries));
                  System.out.println(\"Success Rate : \" + Success \/ Ntries);
              }

          }<\/pre>\n\n\n\n
          I tried 100’000 tries to reach 3 above with a maximal waiting length of 100’000. The average waiting time is about 500 with a success rate of like 99%. If we increase the maximal length before we give up to 1’000’000 the average waiting time increases to 1700 and the success rate is like 99.9%.<\/p>\n\n\n\n
          The question if the score is greater than the score +2 at the beginning after exactly N steps is easy to answer, and approximately 1\/2. But the steps are not independent. Yet, it can be shown that the chance of ever reaching +3 in N steps converges to 1.<\/p>\n\n\n\n
          The average waiting is a completely different question. For the simulation above where we give up after a certain maximal number of throws, it is not easy to compute. So, we use a different approach. We use N states S1,…,SN with wins 3-1, 3-2, …, 3-N. State S1 will exit with probability 1\/2. For state SN, We assume that we stay there with probability 1\/2. This makes it even easier to reach +3, and is therefore an underestimation of the waiting time.<\/p>\n\n\n\n
          For a specific example let us take N=3. We get the following transition matrix, describing the probabilities to go from one state to another state.<\/p>\n\n\n\n
          A = \\begin{pmatrix}0 & 1\/2 & 0 \\\\ 1\/2 & 0 & 1\/2 \\\\ 0 & 1\/2 & 1\/2\\end{pmatrix}<\/pre><\/div>\n\n\n\n
          We can then solve the average waiting times to exit the game if we start in states 1,2,3 as follows.<\/p>\n\n\n\n
          For larger N, it turns out that W1 is always 2N. This is not easy to prove. But here is a computation with Euler Math Toolbox and N=20. <\/p>\n\n\n\n
          >N=20;
          >A=zeros(N,N);
          >A=setdiag(A,1,1\/2);
          >A=setdiag(A,-1,1\/2);
          >A[N,N]=1\/2;
          >A=id(N)-A;
          >short A\\ones(N,1)
                  40 
                  78 
                 114 
                 148 
                 180 
                 ...<\/pre>\n\n\n\n
          If we also exit and give up in state SN (after losing too much), we get a completely symmetrical result with a waiting time for exit when starting in S1 or SN of N. That means that if you decide to give up after reaching something like -100, you will have to wait on average 100 throws before that happens. Let us simulate that.<\/p>\n\n\n\n
          public class WaitingTimesCase2
          {

              public static void main (String args[])
              {
                  int NMax = 100;
                  int Ntries = 100000;

                  double Sum = 0;
                  double Success = 0;
                  double Failures = 0;

                  for (int i = 0; i < Ntries; i++)
                  {
                      int W = -1;
                      int n = 0;
                      while (true)
                      {
                          n++;
                          W = W + ((Math.random() < 0.5) ? -1 : 1);
                          if (W >= 0)
                          {
                              Success++;
                              break;
                          }
                          else if (W < -NMax)
                          {
                              Failures++;
                              break;
                          }
                      }
                      Sum += n;
                  }

                  System.out.println(\"Average : \" + (Sum \/ Ntries));
                  System.out.println(\"Success Rate : \" + Success \/ Ntries);
                  System.out.println(\"Success Rate : \" + Failures \/ Ntries);
              }

          }<\/pre>\n\n\n\n
          The average waiting time will be confirmed to be close to 100. Since we start at the top end, the exit will be far more likely to happen there, and the success rate is like 99%.<\/p>\n\n\n\n
          To be precise, we can compute the probability PN to be in state N if we start at state 1 and do n iterations as<\/p>\n\n\n\n
          P = A^n e_1 <\/pre><\/div>\n\n\n\n
          If we represent the unit vector e_1 in terms of Eigenvectors, we get<\/p>\n\n\n\n
          P = \\lambda_1^n \\alpha_1 v_1 + \\ldots \\lambda_N^n \\alpha_N v_N<\/pre><\/div>\n\n\n\n
          In the matrices of this examples, all Eigenvalues will be smaller than 1. Thus P will converge to 0, meaning that eventually all tries exit. They usually do so with at the geometric rate given by the largest eigenvalue.  <\/p>\n\n\n\n
          There is a lot more to write about this, and there are some proofs missing here. But this is certainly an interesting problem in probability theory.<\/p>\n","protected":false},"excerpt":{"rendered":"
          Let us start with a simple question. How long does it on average take to throw two times 6 in a row when throwing dice? I have treated average waiting times in one of the examples for Euler Math Toolbox (see here). But I want to treat more examples for sequences of random numbers in […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-393","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/renegrothmann.de\/index.php?rest_route=\/wp\/v2\/posts\/393","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/renegrothmann.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/renegrothmann.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/renegrothmann.de\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/renegrothmann.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=393"}],"version-history":[{"count":8,"href":"https:\/\/renegrothmann.de\/index.php?rest_route=\/wp\/v2\/posts\/393\/revisions"}],"predecessor-version":[{"id":409,"href":"https:\/\/renegrothmann.de\/index.php?rest_route=\/wp\/v2\/posts\/393\/revisions\/409"}],"wp:attachment":[{"href":"https:\/\/renegrothmann.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=393"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/renegrothmann.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=393"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/renegrothmann.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=393"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}