Highly scaled CMOS devices are predicted to show probabilistic behavior due to process variations or the presence of noise sources such as thermal noise. Past research dealing with characterizing CMOS devices with probabilistic behavior has shown that computing via these devices, termed probabilistic computing, can help realize highly efficient circuits in terms of energy consumption. In this paper, we explore low power motion estimation, specifically low power hierarchical search algorithms for motion estimation, in the context of probabilistic computing. With the fault tolerant algorithm design (MC-TSS) proposed in this paper, we show that energy savings that can be realized with probabilistic computing increase to 70% versus 57% with the conventional algorithm (TSS), with minor impact on the quality of motion estimation. Furthermore, a 1.8 dB improvement in PSNR under the same energy savings of 70% for both algorithms is shown establishing the superior resilience of the proposed algorithm to probabilistic computing over the conventional algorithm.