# Fuzzy Random Walkers with Second Order Bounds: An Asymmetric Analysis
## 3 Edge-Fuzzy Graphs
### Definitions
: _The cost \(\Delta(p_{j})\) of a fuzzy path \(p_{j}\;=\;(e_{1},\ldots,e_{m})\) is the sum of the cost of its individual edges_  
\[\Delta(p_{j})\stackrel{{\triangle}}{{=}}\sum_{e_{k}\in p_{j}} \delta(e_{k})\;=\;\sum_{k=1}^{m}\frac{1}{h(e_{k})}\;=\;\frac{m}{\mathcal{H} \left(h(e_{1}),\ldots,h(e_{m})\right)},\quad h(e_{k})\;\
eq\;0,1\;\leq\;k\; \leq\;m, \tag{4}\]_where \(\mathcal{H}\left(h(e_{1}),\ldots,h(e_{m})\right)\) is the harmonic mean of \(h(e_{k})\) defined as_  
\[\mathcal{H}\left(s_{1}\,\ldots\,s_{n}\right)\,\stackrel{{\triangle} }{{=}}\frac{1}{\frac{1}{n}\sum_{k=1}^{n}\left(\frac{1}{s_{k}}\right)}\,=\,\, \frac{n}{\frac{1}{s_{1}}+\ldots+\frac{1}{s_{n}}},\quad s_{k}\,\
eq\,0,1\,\leq \,k\,\leq\,n. \tag{5}\]  
By construction \(\Delta\big{(}p_{j}\big{)}\) is bounded as follows  
\[\frac{1}{\max_{1\leq k\leq m}\left\{h(e_{k})\right\}}\,\leq\,\frac{\Delta \big{(}p_{j}\big{)}}{\big{|}p_{j}\big{|}}\,\leq\,\,\frac{1}{\min_{1\leq k\leq m }\left\{h(e_{k})\right\}}. \tag{6}\]  
Whether the above bounds are loose depends on the variability of the actual values \(h(e_{k})\). That is, if the latter are drawn from a distribution which favors extreme values, \(\Delta\big{(}p_{j}\big{)}\) will tend to be close to these bounds. It should also be noted that the variance \(\Delta\big{(}p_{j}\big{)}\) is strongly dependent on that of \(h(e_{k})\). Moreover, \(\Delta\big{(}p_{j}\big{)}\) is prone to outliers, which might lead to an unrealistically high average fuzzy path length. This can be remedied by taking into account the variance of the fuzzy path length. Finally, a low \(\Delta\big{(}p_{j}\big{)}\) tends to contain almost exclusively low edge costs \(\delta(e_{k})\) or, equivalently, edges with high probability of belonging to the graph, an argument which agrees with the weak law of large numbers. In turn, this suggests the intuitive corollary that low cost paths are comprised almost exclusively of edges that are less likely to be fuzzy. This corollary can be used in order to design efficient hybrid probabilistic and combinatorial algorithms based on dynamic programming for finding and enumerating low cost paths akin to the way a similar observation has led to the development of shortest paths relying on dynamic programming in deterministic graphs. From a probabilistic viewpoint, the sum \(\sum_{k=1}^{m}\delta(e_{k})\) is interesting by itself as a finite but possibly large sum of inverse random variables. Notice that the central limit theorem may not be applied in such a setting since the variance of the \(h(e_{k})\) might be infinite. If this is not the case, different bounds can be computed depending on the distribution of \(h(e_{k})\) such as the abovementioned central limit theorem, a Poisson bound, a power law bound, or finally approximations based on Markov or Chebyshev inequalities, the Chernoff bound, or on the Gnedenko extreme value theorem. Notice that the effect of a single edge which is exceedingly difficult to cross can be instrumental in shaping graph communities. The numerical properties of the above sum are also of interest. As values of possibly uneven orders of magnitude may be added, catastrophic cancellation may occur resulting in the loss of meaningful information. This might happen if the summation is executed in an order left to the implementation. On the other hand, the summation order dictated by the Priest algorithm [49] results in the least possible loss of significant decimal digits by adding only numbers of comparable magnitude. Another option would be to substitute the harmonic mean with its thresholded counterpart  
\[\mathcal{H}\left(s_{1},\ldots,s_{m};\tau_{0}\right)\,\stackrel{{ \triangle}}{{=}}\frac{m}{\sum_{1}^{m}\frac{1}{\max\{h(e_{k}),\tau_{0}\}}}\,= \,\,\frac{m}{\frac{1}{\max\{h(e_{1}),\tau_{0}\}}+\ldots+\frac{1}{\max\{h(e_{m }),\tau_{0}\}}}. \tag{7}\]  
For other uses of the thresholded harmonic and geometric means, see [50], while, for the effect of finite precision arithmetic to long biosignals, see [51].