A novel stochastic neural network is proposed in this paper. Unlike the traditional Boltzmann machine, the new model uses stochastic connections rather than stochastic activation functions. Each neuron has very simple functionality but all of its synapses are stochastic. It is shown that the stationary distribution of the network uniquely exists and it is approximately a Boltzmann Gibbs distribution. It is also revealed there exists a strong relationship between the model and the Markov random field. New efficient techniques are developed to implement simulated annealing and Boltzmann lerning.The model has been successfully applied to large-scale face recognition task in which face images are dynamically captured from a video source.Learing and recoginiz-ing processes are carried out in real time.The experimental results show the new model is not only feasible but also efficient.