In this talk we discuss a new approach for the Hamilton cycle problem (HCP). The HCP is one of the classical problems in combinatorial mathematics. It can be stated as given a graph G, find a cycle that passes through every single vertex exactly once, or determine that such a cycle does not exist. In 1994, Filar and Krass developed a new model for HCP by embedding this problem into a Markov decision process. This approach was the motivation of a new line research which was extended by several other people afterwards. In this approach, a new polytope corresponding to a given graph G was constructed and searching for Hamiltonian cycles in a given Hamiltonian graph G was converted to searching for particular extreme points (called Hamiltonian extreme points) among extreme points of that polytope. In this research, we are going to design a Markov chain with certain properties to sample Hamiltonian extreme points of that polytope. More precisely, we would like to study a specific class of input graphs, the so-called random graphs. Some preliminary theoretical results are presented in this talk.