# Decision System Based on Markov Chains for Sizing the Rebalancing Fleet of Bike Sharing Stations
## 3 Methodology
### A Markov Chain for the Subsystem  
Before defining the MC for the subsystem, we must address two issues: the state explosion problem and the interdependence between states and the number of bike stations. Both issues are resolved by a quantization strategy, described as follows. Until now, we have associated a specific value from the domain \([0\%,100\%]\) to the subsystem state vector. The resolution of the measurement is dependent on \(m\) (defined in Equation (7) as the number of bike stations). The states of the MC must be independent of the number of bike stations, otherwise subsystem scalability is not ensured (i.e., if \(m\) is increased, the number of states should remain constant; otherwise, the state explosion problem appears). Therefore, a quantization is performed on the value range \([0\%,100\%]\) of \(\overline{x}\), described as follows:  
\[ \begin{array}{ccccccccc}[0\%,100\%]=&[0\%,v_{1})&\cup&[v_{1},v_{2})&\cup& \ldots&\cup&[v_{N-1},100\%]\\ &\Upar&\Upar&&\Upar&&\Upar\\ &S_{1}&&S_{2}&&S_{N}\end{array} \, \tag{8}\]  
where \(S_{1},S_{2},\ldots,S_{N}\) represent the states of the MC; \(v_{1},v_{2},\ldots,v_{N-1}\) are constants (\(0\%<v_{1}<v_{2}<\cdots<v_{N-1}<100\%\)). At any given state (\(S_{i}\)), a subsystem has the theoretical opportunity to transition to any other state (\(S_{j}\)), as can be seen in the state evolution example from Figure 4 or the general state transition diagram from Figure 5.  
Figure 3: Flowchart for the computation of overall criticality of the subsystem. In this example, from Figure 4, the subsystem representation is featured by any set of small circles with white or dark fill surrounded by a large circle with dashed outline and the same color fill as the state it belongs to. For example, the left-most representation of the subsystem contains eleven dark and eight white small circles, surrounded by a green filled circle. Each small circle represents a bike station, dark if it has critical load, white otherwise. This means that, in the context of this example, the subsystem contains nineteen bike stations. Above the subsystems' representations, there is a graph with a horizontal axis denoting time and a vertical axis corresponding to overall criticality (\(\overline{x}\)). All variables from Equation (8) and their relationship are reflected in the graph. Each measurement from the graph, symbolized by \(\times\), means that the overall criticality \(\overline{x}\) of the subsystem at time \(t_{i}\) is of value \(\overline{x}_{i}\), which translates to the affiliation to one of the states \(S_{1}\), \(S_{2}\), \(S_{3}\), or \(S_{4}\). Each value \(\overline{x}_{i}\) is computed by dividing the number of small dark circles over the number of all small circles inside the bigger circle. The state \(S_{i}\) of the MC is defined based on the ratio of bike stations in critical load. The state changes when the ratio of bike stations in critical load goes outside of a determined interval. Therefore, the state can be characterized by the specific range \([v_{i-1},v_{i})\to S_{i}\) of the ratio of bike stations in critical load. The timing associated with the state transition is expressed by a random variable \(X\) with a specified distribution function. The exponential distribution function is expressed by the following relation:  
\[F(X)=P(X\geq x)=1-e^{-\lambda x}. \tag{9}\]  
If \(t_{ij}\) represents the time interval for which a subsystem remains in state \(S_{i}\) until it reaches state \(S_{j}\), expressed by a random variable of exponential distribution with mean value \(\gamma_{ij}\), then the execution frequency of the transition will be \(\lambda_{ij}=\frac{1}{\gamma_{ij}}\), which, from now on, will be called \"transition rate\". So, from \(S_{i}\) to \(S_{j}\), the transition probability is defined as an exponential distribution function, outlined in Equation (9), with frequency \(\lambda_{ij}\) and mean value \(\gamma_{ij}\). The probability is dependent on the current state and is not influenced by past or future states. Figure 4: Evolution of subsystem state.