Bike sharing systems are becoming an urban mode of transportation. In such a system, 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. We develop a stochastic model and study the effect of random choices from users 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. We quantify the influence of the stations capacities and compute the optimal fleet size. Even in an homogeneous city, the system exhibits a poor performance: the optimal number of problematic stations decreases only as the inverse of the capacity. We show that simple incentives, such as suggesting users to return to the least loaded station among two neighboring stations, improve the situation by an exponential factor. We study the optimal redistribution rate in a simple redistribution model. We show that this rate decreases as the inverse of the stations capacity. For all cases considered, the optimal fleet size is more than half of the station capacity, the extra depending on the system parameters.