Simulation Simplified
9. Mean, Median, and the Like
Class P2Pedia03a

import edu.rit.numeric.Function;
import edu.rit.numeric.ListSeries;
import edu.rit.numeric.ListXYSeries;
import edu.rit.numeric.SampledXYSeries;
import edu.rit.numeric.Series;
import edu.rit.numeric.plot.Plot;
import edu.rit.numeric.plot.Strokes;
import edu.rit.util.Random;
import edu.rit.util.RandomSubset;
import java.awt.Color;
import java.util.Arrays;
import java.util.LinkedList;
public class P2Pedia03a
   {
   public static void main
      (String[] args)
      throws Exception
      {
      if (args.length != 4) usage();
      int N = Integer.parseInt (args[0]);
      int K = Integer.parseInt (args[1]);
      final int T = Integer.parseInt (args[2]);
      long seed = Long.parseLong (args[3]);
      Random prng = Random.getInstance (seed);
      int[][] conn = new int[N][K+1];
      for (int i = 0; i < N; ++ i) conn[i][0] = (i + 1)%N;
      int[] dist = new int[N];
      ListSeries len = new ListSeries();
      for (int trial = 0; trial < T; ++ trial)
         {
         for (int i = 0; i < N; ++ i)
            {
            RandomSubset rs = new RandomSubset (prng, N);
            rs.remove (i);
            rs.remove ((i + 1)%N);
            for (int j = 1; j <= K; ++ j) conn[i][j] = rs.next();
            }
         int orig = prng.nextInt (N);
         int match = prng.nextInt (N);
         len.add (shortestPathLength (conn, dist, orig, match));
         }
      System.out.printf ("Query path length:%n");
      final Series.Stats stats = len.stats();
      System.out.printf ("Mean   = %.2f%n", stats.mean);
      System.out.printf ("Stddev = %.2f%n", stats.stddev);
      Series.RobustStats rstats = len.robustStats();
      System.out.printf ("Median = %.0f%n", rstats.median);
      int a = (int) rstats.quantile (0.05);
      int b = (int) rstats.quantile (0.95);
      System.out.printf ("90%% ci = %d .. %d%n", a, b);
      ListXYSeries hist = new ListXYSeries();
      for (int i = 0; i <= b + a; ++ i)
         {
         hist.add (i, rstats.histogram (i, i + 1));
         }
      new Plot()
         .plotTitle ("P2Pedia03a, N="+N+", K="+K+", T="+T)
         .xAxisTitle ("Query path length")
         .yAxisTitle ("Occurrences")
         .xySeries (hist)
         .seriesDots (null)
         .seriesStroke (Strokes.solid (1))
         .seriesColor (Color.RED)
         .xySeries
            (new SampledXYSeries
               (new Function()
                  {
                  private double mean = stats.mean;
                  private double var = stats.var;
                  private double stddev = stats.stddev;
                  private double A = T/Math.sqrt(2*Math.PI)/stddev;
                  public double f (double x)
                     {
                     double d = x - mean;
                     return A*Math.exp(-0.5*d*d/var);
                     }
                  },
                0.0, 0.1, 10*(b + a) + 1))
         .getFrame()
         .setVisible (true);
      }

   private static int shortestPathLength
      (int[][] conn,
       int[] dist,
       int orig,
       int match)
      {
      if (orig == match) return 0;
      Arrays.fill (dist, -1);
      dist[orig] = 0;
      LinkedList<Integer> queue = new LinkedList<Integer>();
      queue.addLast (orig);
      for (;;)
         {
         int i = queue.removeFirst();
         for (int j : conn[i])
            {
            if (j == match)
               {
               return dist[i] + 1;
               }
            else if (dist[j] == -1)
               {
               dist[j] = dist[i] + 1;
               queue.addLast (j);
               }
            }
         }
      }

   private static void usage()
      {
      System.err.println
         ("Usage: java P2Pedia03a <N> <K> <T> <seed>");
      System.exit (1);
      }
   }