The Chebyshev polynomials of the first kind are a family of orthogonal polynomials with a number of properties useful for designing numerical algorithms for symmetric matrices. On the interval between -1 and 1, the magnitude of all Chebyshev polynomials is bounded above by one. Outside of that interval, their magnitude grows faster than that of any other polynomial family with the same boundedness property on that interval.

A probabilistic perspective due to Sachdeva and Vishnoi views the Chebyshev polynomial recurrence in terms of expectation, enabling the development of useful results in approximation theory.

In this thesis, we generalize Sachdeva and Vishnoi's probabilistic argument to develop approximation theory results suitable for regions of the complex plane. Specifically, we introduce a number of polynomial families defined by recurrence relations with coefficients derived from mean-zero random walks. These polynomial families can be viewed as a generalization of the Chebyshev polynomials, and are closely related to the Faber polynomials for certain regions, often hypocycloidal, of the complex plane. We demonstrate that the polynomial families we construct remain bounded on these regions, and, like the Chebyshev polynomials, can be used to approximate polynomials of much higher degree on their regions of boundedness. Additionally, we prove that these polynomial families exhibit a fast growth property near z = 1. To demonstrate potential applications of these results, we leverage the fast growth property to develop higher-order momentum acceleration schemes for the power method, which we apply to quickly compute the dominant eigenvectors of non-symmetric operators with small spectral gaps.