Nanoscale resistive switching devices (memristive devices or memristors) have been studied for a number of applications ranging from non-volatile memory, logic to neuromorphic systems. However a major challenge is to address the potentially large variations in space and time in these nanoscale devices. Here we show that in metal-filament based memristive devices the switching can be fully stochastic. While individual switching events are random, the distribution and probability of switching can be well predicted and controlled. Rather than trying to force high switching probabilities using excess voltage or time, the inherent stochastic nature of resistive switching allows these binary devices to be used as building blocks for novel error-tolerant computing schemes such as stochastic computing and provides the needed "analog" feature for neuromorphic applications. To verify such potential, we demonstrated memristor-based stochastic bitstreams in both time and space domains, and show that an array of binary memristors can act as a multi-level "analog" device for neuromorphic applications.