Bike-sharing systems are becoming an urban mode of transportation. In such systems, users arrive at a station, take a bike and use it for a while, then return it to another station of their choice. Each station has a finite capacity: it cannot host more bikes than its capacity. A stochastic model is proposed to study the effect of users random choices on the number of problematic stations, i.e., stations that host zero bikes or that have no available spots at which a bike can be returned. The influence of the stations' capacities is quantified and the fleet size that minimizes the proportion of problematic stations is computed. Even in a homogeneous city, the system exhibits a poor performance: the minimal proportion of problematic stations is to the order of (but not lower than) the inverse of the capacity. We show that simple incentives, such as suggesting users to return to the least loaded station among two stations, improve the situation by an exponential factor. We also compute the rate at which bike has to be redistributed by trucks to insure a given quality of service. This rate is to the order of the inverse of the stations capacity. For all cases considered, the optimally reliable fleet size is a little more than half of the station capacity, the value of the little more depends on the system parameters.