As Moore's law approaches the low nanometer range, predictions have been made that computing via future technology nodes may no longer be correct due to, for example, the presence of noise sources such as thermal noise. Probabilistic computing, a term coined for computing via devices that yield a probabilistically correct output, has earlier been shown as a means for realizing energy efficient computing in signal processing applications. In this paper, we explore the application of probabilistic computing for low power motion estimation. It is observed that motion estimation itself exhibits high resilience to erroneous computation. Simulations show that energy savings up to 44% can be achieved in motion estimation using full search block matching with probabilistic computing with a minor impact (under 0.5 dB) on the required quality of the output. A scheme of error correction based on the motion vector distribution is proposed that further increases the possible energy savings with full search block matching up to 57%.