First hitting times of simple random walks on graphs with congestion points (Q1415070): Difference between revisions

Consider a lollipop \(P\) (which consists of a circle with \(2n\) vertices and a line segment with \(n+1\) vertices) and a dumbbell \(Q\) (consisting of a line segment with \(n+1\) vertices and two circles each with \(2n\) vertices). Using group representations the author gives explicit formulas for the probability generating functions (pgf) of the first hitting times of simple random walks on \(P\) and \(Q\), resp. The same arguments can be modified to derive pgf on necklace graphs which consist of several circles and some lines. Random walks on such graphs can model computer networks and traffic congestion problems in terms of hitting times.