Is the MCMC simply a probabilistic gradient descent? I'm learning about Markov Chain Monte Carlo methods, and to my undifferentiated mind, they basically resemble gradient descent with a stochastic component replacing the gradient computation. Is this a correct understanding. If not what key difference am I missing?
 A: I know this question has been answered, but if anyone is interested in learning more on on jbowman's suggestion of random proposals with an acceptance step see Simulated Annealing:
http://en.wikipedia.org/wiki/Simulated_annealing
Excerpt: 

"The method is an adaptation of the Metropolis-Hastings algorithm, a
  Monte Carlo method to generate sample states of a thermodynamic
  system..."

Typically slower then SGD, it's a good MC-based method for seeking global minima.
Java implementation for reference: https://github.com/wlmiller/BKTSimulatedAnnealing
A: The key difference is that we are not attempting to optimize anything.  Instead, we are attempting to estimate a density function - but not by estimating in some optimal manner a small number of parameters, instead by generating a lot of random numbers from the density function and going from there.  So MCMC is really a random number generation technique, not an optimization technique.
To see what a gradient descent-like algorithm with a stochastic component looks like, check out stochastic approximation.  The simultaneous perturbation variant is quite effective and accessible.
A: While the accepted answer here is true, it is a bit misleading in light of recent theoretical work.
When you are doing gradient descent, you are trying to find the maximum a posterior (MAP) - aka the mode of your posterior distribution.  While stochastic gradient descent (SGD) will only give you a point estimate, it will give you a trajectory that will allow you to explore the posterior density around your MAP estimate.
There is a ton of emerging literature around this, starting with Neal 2012 / Welling 2011 with Langevin dynamics and later Mandt 2017, Maddox 2019 and Zhang 2021. At this point, it is safe to say that SGD will generate a single MCMC draw from your posterior distribution.
