Commercial and low-saturation gas (also called paleoresidual gas [PRG]) show similar strong amplitude signatures on P-wave seismic data. This poses an exploration risk in gas reservoir regions. However, density correlates inversely with gas saturation and can differentiate a zone of full gas saturation from PRG. This can improve the chances of success in terms of predrill prediction of gas saturation. Amplitude-variation-with-offset (AVO) inversion using prestack seismic data is the most commonly used technique that can estimate elastic parameters such as P-wave velocity, S-wave velocity, and density. Out of these three parameters, extracting density from seismic data is the most challenging due to its weak sensitivity to seismic reflection amplitude and the lack of good quality seismic data at far offsets. However, with recent improvements in seismic data acquisition and processing technology, which produces reliable AVO gathers, density estimates have improved. This requires that strong density sensitivity to AVO exists. Note that multiple density models may fit the data equally well. Therefore, quantifying uncertainty is crucial for interpretation and risk assessment. We apply a recently developed stochastic approach based on the Bayesian framework to solve the problem in a transdimensional framework, where the number of model parameters is treated as a variable and estimated along with the elastic properties. We use the reversible jump Hamiltonian Monte Carlo (RJHMC) algorithm to sample models from a variable dimensional model space and obtain a globally optimum model and uncertainty estimates. We use a synthetic and good quality real data set from Columbus Basin in Trinidad, which has a proven gas reservoir, to demonstrate the algorithm. The RJHMC results calibrate well with the logs and show the areal extents of the density anomalies within the 3D volume.