This study considers paging schemes that can page some cells or only one cell within the location area to reduce paging cost by using PAs (Paging Agents) and compares their performances by using a new analytic method. There are three ways of paging schemes using PAs; BSPA (Base Staton Paging Agent), 2SPA (2-Step Paging Agent), LAPA (Location Area Paging Agent). This study proposes exact performance of BSPA and 2SPA using a new analytic method based on Markov chain modeling to find the most efficient paging scheme. Numerical results for various circumstances are presented by using proposed analytic method to select a proper paging scheme in mobile communication networks.