We consider the probabilistic traveling salesman problem (PTSP) in which customer presences are Bernoulli random variables, and the objective is to determine an a priori tour minimizing the expected traveling cost of the a posteriori tour obtained by skipping absent customers after customer presence is revealed. The existing literature has established that, given an a priori tour, the expected recourse function—the objective function of the PTSP—can be evaluated using efficient polynomial-time procedures under certain distributions of the random customer presence. However, a tractable convex representation exploiting the structure of the a priori tour and recourse policy for the expected recourse function was unknown until now, despite its importance in developing sophisticated exact algorithms for the PTSP and related problems. In this paper, we fill this research gap by deriving a new tractable convex piecewise-affine representation for the expected recourse function in the PTSP with an arbitrary distribution of the random customer presence. Building upon this convex representation, we develop new mixed integer linear programming formulations for the PTSP, and design an exact algorithm in which the exponentially many linear inequalities are separated dynamically. Extensive computational results on benchmark instances with both independent and correlated customer presences demonstrate that, thanks to the strong linear programming relaxation bound, the proposed exact algorithm significantly outperforms the state-of-the-art integer L-shaped method. Using the proposed algorithm, PTSP instances with up to 300 vertices can now be solved to optimality or near-optimality within a two-hour time limit. Moreover, when run under a 600-second time budget, it can provide much better solutions than a leading heuristic algorithm in the literature.