BazTech - Yadda

1

A Quarter Century of Baker-Map Exploration

Hoover William Graham, Hoover Carol Griswold

Computational Methods in Science and Technology

|

2023

|

Vol. 29, No. 1-4

5--16

EN

25 years ago the June 1998 Focus Issue of “Chaos” described the proceedings of a workshop meeting held in Budapest and called “Chaos and Irreversibility”, by the organizers, T. Tél, P. Gaspard, and G. Nicolis. These editors organized the meeting and the proceedings’ issue. They emphasized the importance of fractal structures and Lyapunov instability to modelling nonequilibrium steady states. Several papers concerning maps were presented. Ronald Fox considered the entropy of the incompressible Baker Map B(x, y), shown here in Fig. 1. He found that the limiting probability density after many applications of the map is ambiguous, depending upon the way the limit is approached. Harald Posch and Bill Hoover considered a time-reversible version of a compressible Baker Map, with the compressibility modelling thermostatting. Now, 25 years later, we have uncovered a similar ambiguity, with the information dimension of the probability density giving one value from pointwise averaging and a different one with areawise averaging. Goldstein, Lebowitz, and Sinai appear to consider similar ambiguities. Tasaki, Gilbert, and Dorfman note that the Baker Map probability density is singular everywhere, though integrable over the fractal y coordinate. Breymann, Tél, and Vollmer considered the concatenation of Baker Maps into MultiBaker Maps, as a step toward measuring spatial transport with dynamical systems. The present authors have worked on Baker Maps ever since the 1997 Budapest meeting described in “Chaos”. This paper provides a number of computational benchmark simulations of “Generalized Baker Maps” (where the compressibility of the Map is varied or “generalized”) as described by Kumicák in 2005.

2

No cutoff for circulants : an elementary proof

Abrams Aaron, Landau Henry, Pommersheim Jamie, Babson Eric, Landau Zeph

Probability and Mathematical Statistics

|

2022

|

Vol. 42, Fasc. 1

97--108

EN

We give an elementary proof of a result due to Diaconis and Saloff-Coste (1994) that families of symmetric simple random walks on Cayley graphs of abelian groups with a bound on the number of generators never have sharp cutoff. Here convergence to the stationary distribution is measured in the total variation norm. This is a situation of bounded degree and no expansion; sharp cutoff (or the cutoff phenomenon) has been shown to occur in families such as random walks on a hypercube (Diaconis, 1996) in which the degree is unbounded as well as on a random regular graph where the degree is fixed, but there is expansion (Diaconis and Saloff-Coste, 1993).

3

Network Capacity Bound for Personalized PageRank in Multimodal Networks

Kłopotek Mieczysław Alojzy, Wierzchoń Sławomir, Kłopotek Robert A.

Fundamenta Informaticae

|

2022

|

Vol. 189, nr 1.

49--68

EN

In a former paper [1] the concept of Bipartite PageRank was introduced and a theorem on the limit of authority flowing between nodes for personalized PageRank has been generalized. In this paper we want to extend those results to multimodal networks. In particular we deal with a hypergraph type that may be used for describing multimodal network where a hyperlink connects nodes from each of the modalities. We introduce a generalisation of PageRank for such graphs and define the respective random walk model that can be used for computations. We state and prove theorems on the limit of outflow of authority for cases where individual modalities have identical and distinct damping factors.

4

Energy of Taut Strings Accompanying Random Walk

Lifshits Mikhail A., Siuniaev Anatoly A.

Probability and Mathematical Statistics

|

2021

|

Vol. 41, Fasc. 1

9--23

EN

We consider the kinetic energy of the taut strings accompanying trajectories of a Wiener process and a random walk. Under certain assumptions on the band width, it is shown that the energy of a taut string accompanying a random walk within a band satisfies the same strong law of large numbers as proved earlier for a Wiener process and a fixed band width. New results for Wiener processes are also obtained.

5

Stationarity against integration in the autoregressive process with polynomial trend

Proïa F.

Probability and Mathematical Statistics

|

2018

|

Vol. 38, Fasc. 1

1--26

EN

We tackle the stationarity issue of an autoregressive path with a polynomial trend, and generalize some aspects of the LMC test, the testing procedure of Leybourne and McCabe. First, we show that it is possible to get the asymptotic distribution of the test statistic under the null hypothesis of trend-stationarity as well as under the alternative of nonstationarity for any polynomial trend of order r. Then, we explain the reason why the LMC test, and by extension the KPSS test, does not reject the null hypothesis of trend-stationarity, mistakenly, when the random walk is generated by a unit root located at −1.We also observe it on simulated data and correct the procedure. Finally, we describe some useful stochastic processes that appear in our limiting distributions.

6

Random walk analysis of cave maps for exemplary gypsum caves-mazes of Western Ukraine

Błachowicz T., Andreychouk V., Domino K.

Landform Analysis

|

2018

|

Vol. 36

3--8

EN

The paper presents a new method of quantitative parameterization of net geomorphological structures with the use of random walk formalism and an analysis of Hurst exponent distribution derived from random walk experiments. As examples, horizontally developed gypsum caves were elaborated. The provided methodology is able to uniquely characterize cave systems.

7

Calibration of backward-in-time model using drifting buoys in the East China Sea

Yu F., Li J., Zhao Y., Li Q., Chen G.

Oceanologia

|

2017

|

No. 59 (3)

238--247

EN

In the process of oil exploitation and transportation, large amounts of crude oil are often spilled, resulting in serious pollution of the marine environment. Forecasting oil spill reverse trajectories to determine the exact oil spill sources is crucial for taking proactive and effective emergency measures. In this study, the backward-in-time model (BTM) is proposed for identifying sources of oil spills in the East China Sea. The wind, current and random walk are three major factors in the simulation of oil spill sources. The wind drag coefficient varies along with the uncertainty of the wind field, and the random walk is sensitive to various traits of different regions, these factors are taken as constants in most of the state-of-the-art studies. In this paper, a self-adaptive modification mechanism for drift factors is proposed, which depends on a data set derived from the drifter buoys deployed over the East China Sea shelf. It can be well adapted to the regional characteristics of different sea areas. The correlation factor between predicted positions and actual locations of the drifters is used to estimate optimal coefficients of the BTM. A comparison between the BTM and the traditional method is also made in this study. The results presented in this paper indicate that our method can be used to predict the actual specific spillage locations.

8

Kendall random walks

Jasiulis-Gołdyn B. H.

Probability and Mathematical Statistics

|

2016

|

Vol. 36, Fasc. 1

165--185

EN

The paper deals with a new class of random walks strictly connected with the Pareto distribution. We consider stochastic processes in the sense of generalized convolution or weak generalized convolution. The processes are Markov processes in the usual sense. Their structure is similar to perpetuity or autoregressive model. We prove the theorem which describes the magnitude of the fluctuations of random walks generated by generalized convolutions. We give a construction and basic properties of random walks with respect to the Kendall convolution.We show that they are not classical Lévy processes. The paper proposes a new technique to cumulate the Pareto-type distributions using a modification of the Williamson transform and contains many new properties of weakly stable probability measure connected with the Kendall convolution. It seems that the Kendall convolution produces a new class of heavy tailed distributions of Pareto-type.

9

Use of random walk in two-dimensional lattice graphs to describe influence of wind and sea currents on oil slick movement

Guze S., Mazurek J., Smolarek L.

Journal of KONES

|

2016

|

Vol. 23, No. 2

147--153

EN

The concept of oil slick movement being influenced by wind and sea currents is elementary for the decision model of the distribution of large oil spill emergency control means at sea. The analysis of water area conditions such as wind and sea currents is elementary for the concept of oil slick movement. The article presents the model of oil slick movement under the influence of wind and sea currents. In building the model, random walk in two-dimensional lattice graphs has been used. The movement of oil slick is analysed in two ways. In the paper, the movement of the oil slick is analysed in two ways without wind and focus on surface sea currents and with wind and currents. Case one assumes no wind and focuses on surface sea currents only using random walk in a two-dimensional square grid graph. Case two assumes that wind is in place, so oil slick is moving due to surface sea currents and wind currents. The description of movement in case two is based on a two-dimensional lattice graph, which is a combination of a triangular grid graph and a hexagonal grid graph. The article also describes the basic assumptions of oil slick model: the definition of water area, oil slick and algorithm for rescue action to contain the oil spill. Oil slick movement concept is elementary for the decision model of oil spill control at sea. The model allows estimating the distance of oil slick from coastal areas.

10

Asymmetric detrended fluctuation analysis reveals asymmetry in the rr intervals time series

Mieszkowski D., Kośmider M., Krauze T., Guzik P., Piskorski J.

Journal of Applied Mathematics and Computational Mechanics

|

2016

|

Vol. 15, nr 1

99--106

EN

In this paper we apply the Asymmetric Detrended Fluctuation Analysis to the RR intervals time series. The mathematical background of the ADFA method is discussed in the context of heart rate variability and heart rate asymmetry. We calculate the α- and α+ ADFA scaling exponents for 100 RR intervals time series recorded in a group of healthy volunteers (20-40 years of age) with the use of the local ADFA. It is found that on average α+ < α-, and that locally α- dominates most of the time over α+ - both results are highly statistically significant.

11

An efficient Monte Carlo approach to compute PageRank for large graphs on a single PC

Sonobe T.

Foundations of Computing and Decision Sciences

|

2016

|

Vol. 41, No. 1

29--43

EN

This paper describes a novel Monte Carlo based random walk to compute PageRanks of nodes in a large graph on a single PC. The target graphs of this paper are ones whose size is larger than the physical memory. In such an environment, memory management is a difficult task for simulating the random walk among the nodes. We propose a novel method that partitions the graph into subgraphs in order to make them fit into the physical memory, and conducts the random walk for each subgraph. By evaluating the walks lazily, we can conduct the walks only in a subgraph and approximate the random walk by rotating the subgraphs. In computational experiments, the proposed method exhibits good performance for existing large graphs with several passes of the graph data.

12

Quantitative estimation of 3D cave networks complexity using random walk analysis

Błachowicz T., Andreychouk V.

Landform Analysis

|

2015

|

Vol. 29

91--96

EN

The paper presents a new method of quantitative parameterization of volumetric-net geomorphological structures with the use of random walk formalism and an analysis of self-similarity exponent distribution derived from random walk experiments. As examples, two American three-dimensional Wind and Lechuguilla cave networks were elaborated. The provided methodology is able to uniquely characterize the morphology of cave systems.

13

Nowoczesne metody segmentacji obrazów w wybranych przemysłowych i medycznych systemach wizyjnych

Fabijańska A.

Zeszyty Naukowe. Rozprawy Naukowe / Politechnika Łódzka

|

2012

|

Z. 435

1--228

PL

W rozprawie przedstawiono podsumowanie dotychczasowych prac autorki dotyczących problemu segmentacji obrazów cyfrowych. Omówione zagadnienia dotyczą zarówno opracowania nowoczesnych algorytmów dedykowanych rozważanemu problemowi, jak również ich zastosowania i weryfikacji w rzeczywistych aplikacjach systemów wizyjnych z dziedziny przemysłu oraz medycyny. W szczególności, zagadnienia referowane w rozprawie dotyczą czterech zasadniczych problemów, którymi są: wykorzystanie teorii grafów w segmentacji obrazów, wykorzystanie teorii błądzenia przypadkowego w segmentacji obrazów, zastosowanie technik subpikselowych do poprawy odwzorowania kształtu obiektów w procesie segmentacji oraz wykorzystanie procesu dyfuzji do sterowania przebiegiem segmentacji obrazów. W pierwszej kolejności skupiono się na najnowszych technikach grafowych stosowanych w segmentacji obrazów. Przedstawiono ich charakterystykę, przeanalizowano słabe strony oraz zaproponowano dwa autorskie rozwiązania, pozwalające na eliminację wskazanych wad. Następnie rozważano algorytm random walker oparty na teorii błądzenia przypadkowego. Zaproponowano sposób połączenia tej metody z prowadzonym w trzech wymiarach rozrostem obszaru, w taki sposób, aby skutecznie dokonywać segmentacji danych wolumetrycznych i jednocześnie unikać wycieków spowodowanych nieciągłością krawędzi poddawanych segmentacji obiektów. Znaczącą część rozprawy poświęcono również problemowi zastosowania subpikselowych metod przetwarzania i analizy obrazów w procesie segmentacji. Dokonano obszernego przeglądu istniejących metod z tej grupy oraz przeanalizowano ich przydatność w procesie segmentacji obrazów. Zaproponowano autorskie rozwiązanie dedykowane segmentacji obrazów z subpikselową precyzją. Ostatecznie rozważono możliwość połączenia anizotropowej filtracji obrazów opartej na procesie dyfuzji z segmentacją poprzez rozrost obszaru. W konsekwencji, opracowano uniwersalny algorytm, który pozwala na poprawną segmentację struktur o włosowatym kształcie. Wszystkie zaprezentowane w rozprawie algorytmy segmentacji obrazów zaimplementowano, a ich poprawność zweryfikowano poprzez zastosowanie w rzeczywistych systemach pomiarowych, reprezentujących trzy zasadniczo różne dziedziny, tj.: metalurgię, włókiennictwo oraz medycynę. Należy również podkreślić, że rozprawa jest pierwszym tak obszernym opracowaniem, poświęconym innym niż tradycyjne metodom segmentacji obrazów cyfrowych.

EN

The dissertation summarizes results of author’s research on digital image segmentation. The discussed issues concern both the development of modern algorithms dedicated to the regarded problem as well as their application and verification in a real-world vision systems from the field of industry and medicine. In particular the issues referred in the dissertation relate to the four main problems, namely: the use of graph theoretical methods in image segmentation, the application of random walk theory in image segmentation, the use of subpixel techniques for increasing accuracy of image segmentation and the application of the diffusion process for controlling image segmentation. Firstly, the latest graph based methods for image segmentation were regarded. Their characteristics were presented and their weaknesses were analyzed. As a result, two author’s methods were presented which allowed for elimination of the identified weaknesses. Next, the random walker algorithm was considered. The new approach based on the random walks theory and region growing was proposed. The introduced method is dedicated to effective segmentation of volumetric images and allows to avoid leakages caused by a weak boundaries of the segmented objects. A significant part of the dissertation was also devoted to the problem of application of subpixel methods of image processing and analysis in image segmentation. The exhaustive review of the existing subpixel methods was provided and their usefulness in image segmentation was examined. The author’s algorithm for image segmentation with subpixel precision was proposed. Finally, the possibility to combine diffusion-based image anisotropic filtering with region growing segmentation was regarded. As a result, a new universal method for segmentation of flow-like, capillary objects was introduced. All image segmentation algorithms proposed in the dissertation were implemented. Their correctness and accuracy were positively verified in the real-world measurement systems, representing three different fields, namely: metallurgy, textiles and medicine. It should also be underlined, that the dissertation is the first one, such exhaustive study devoted to other than the traditional ones image segmentation algorithms.

14

Random walk - fuzzy aspects

Frič R., Papčo M.

Scientific Issues of Jan Długosz University in Częstochowa. Mathematics

|

2011

|

Vol. 16

205--212

EN

Some beautiful and powerful mathematical ideas are hard to present to students because of the involved abstract language (notation, definitions, theorems, proofs, formulas) and lack of time. Animation and “mathematical experiments” provide a remedy. In the field of stochastics, the Galton board experiment presents several fundamental stochastic notions: a random event, independent random events, the binomial distribution, limit distribution, normal distribution, interpretation of probability, and leads to their better understanding. Random walk is a natural generalization of the Galton board. We use random walks as a motivation and presentation of basic principles of fuzzy random events and fuzzy probability. Fuzzy mathematics and fuzzy logic generalize classical (Boolean) mathematics and logic, reflect everyday experience and decision making and have broader applications. Experimenting with random walks also sheds light on the transition from classical to fuzzy probability.

15

Próba szacowania niezawodności i trwałości urządzenia z wykorzystaniem modelu błądzenia przypadkowego

Tomaszek H., Ważny M.

Przegląd Mechaniczny

|

2011

|

nr 1

43-46

PL

W artykule przedstawiono metodę oceny niezawodności i trwałości urządzenia z wykorzystaniem metody błądzenia przypadkowego, opartą na założeniu, że można ocenić niezawodność urządzenia według odchyłki jednego dominującego parametru diagnostycznego od wartości nominalnej. Przyjęto, że odchyłki parametru diagnostycznego od wartości nominalnej mają wartości dodatnie i narastają w sposób losowy, dający się opisać przy użyciu modelu błądzenia przypadkowego prowadzącego do równania Fokkera-Plancka. Rozwiązanie szczególne tego równania pozwala otrzymać funkcję gęstości wartości odchyłki zależną od czasu eksploatacji. Funkcję tę następnie wykorzystano do określenia ryzyka przekroczenia stanu granicznego i wyznaczenia funkcji gęstości czasu przekroczenia stanu granicznego. Wyznaczona funkcja gęstości została wykorzystana do oceny niezawodności i trwałości urządzenia ze względu na przyjęty parametr diagnostyczny.

EN

Method of determination of durability and reliability of a device with the use of the random walk model, based on the assumption that possible is to determine the reliability of a device according to deviation from the nominal value of one dominant diagnostic parameter. It was take that deviation had positive values and grown up randomly, in way described with the random walk model and Fokker-Planck equation. Particular solution of this equation allows to obtain density function of deviation value depending on exploitation period. Obtained function was then applied to evaluation of risk of the limit overflow and determination of density function of the time of the limit overflow. Density function was applied to determination of reliability and durability of the device for the sake of approved diagnostic parameter.

16

Błądzenie losowe i jego zastosowanie do modelowania deformacji górotworu powodowanych eksploatacją górniczą

Niemiec R., Niemiec T.

Prace Naukowe GIG. Górnictwo i Środowisko / Główny Instytut Górnictwa

|

2008

|

Wyd. spec. nr 6

351-364

PL

Ruch pustki poeksploatacyjnej w górotworze ku górze, jest inwersją wsypywania się rumoszu skalnego w przestrzeń po wybraniu pokładu kopaliny użytecznej. Gdy rozmiary tych licznych, wędrujących w górotworze pustek są makroskopowe (rzędu milimetrów lub ich części), a ich ruchy są przypadkowe - obserwuje się dyskretne i stochastyczne rozkłady deformacji górotworu; w szczególności powierzchni terenu. W artykule przedstawiono model pozwalający określać odpowiednio zdefiniowane wskaźniki deformacji. Na podstawie wielokrotnych symulacji, określono średnie wartości niektórych wskaźników deformacji, ich odchylenia standardowe i współczynniki zmienności. Rozluzowanie skał, a przez to zwiększenie swej pierwotnej objętości, w istotny sposób wpływa na asymetrię rozkładu wskaźników deformacji.

EN

Movement of postmining void up in the rockmass is an inversion of rubble pouring into the space remaining after mining a bed of useful mineral. When sizes of these numerous voids moving in rockmass are macroscopic (of millimetres rank or part of it), and their movements are accidental - discreet and stochastic distributions of rockmass deformation are observed; in particular of terrain surface. In the paper, a model was presented enabling to determine suitably defined deformation indices. On a basis of multiple simulations, average values of some deformation indices, their standard deviations and coefficients of variability were defined. Loosening of rocks, and through that enlargement of their primary volume, influences in an essential way the asymmetry of distribution of deformation indices.

17

Testing the weak-form of efficiency on Czech and Slovak stock market

Hanclova J., Rublikova E.

Badania Operacyjne i Decyzje

|

2006

|

nr 1

21-38

EN

The article deals with the testing of the weak form of efficiency on Czech and Slovak stock market during the period of years 2000–2004 based on daily returns representing index PX50 and SAX30 in the form of martingale as well as in the form of random walk. Concerning functional model forms of conditional variance, the linear and nonlinear volatility models have been estimated and half-life of the variance on the markets, presence of leverage effect or risk aversion have been evaluated. Based on the results the Czech stock market was evaluated as the weakly efficient one in the monitored period. Slovak stock market was evaluated as more or less inefficient, only in the time period of 2000–2002 the martingale form of efficiency has not been rejected.

PL

Artykuł dotyczy analizy słabych form efektywnooci giełdy Czech i Słowacji w latach 2000 - 2004 na podstawie dziennych zwrotów reprezentujących indeksy PX50 i SAX30 w formie martyngałów oraz w formie błądzenia losowego. W odniesieniu do modelu funkcjonalnego wariancji warunkowej rynku liniowe i nieliniowe modele zmienności zostały estymowane oraz połowiczna wariancja na rynkach, obecność efektu dźwigni i unikanie ryzyka zostały oszacowane. Wyniki oszacowania giełdy czeskiej w omawianym okresie określają ją jako słabo efektywną. Giełda słowacka została oszacowana jako bardziej lub mniej nieefektywna, jedynie w latach 2000 - 2002 martyngałowa forma efektywności nie została odrzucona.

18

A newly developed random walk model for PCS network

Islam I., Hossain S.

Journal of Telecommunications and Information Technology

|

2005

|

nr 1

153-156

EN

Different types of random walk models are prevalent in mobile cellular network for analysis of roaming and handover, being considered as important parameters of traffic measurement and location updating of such network. This paper proposes a new random walk model of hexagonal cell cluster, exclusively developed by the authors and a comparison is made with two existing models. The proposed model shows better performance in context of number of probability states compared to existing models.

19

Zastosowanie teorii błądzenia przypadkowego w przetwarzaniu wstępnym barwnych obrazów cyfrowych

Szczepański M.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2004

|

nr 10

395-398

PL

Celem pracy było opracowanie uniwersalnej techniki redukcji szumów w barwnych obrazach cyfrowych wykorzystujących ideę ścieżek cyfrowych będących trajektoriami wirtualnej cząstki błądzącej po kracie obrazu. Zaproponowane filtry wykorzystują ogólną strukturę filtru rozmytego z funkcją przynależności liczoną na podstawie kosztu połączenia pikseli przez ścieżki cyfrowe. W pracy przedstawiony został szeroki przegląd technik stosowanych do celów poprawy jakości obrazów cyfrowych, przeprowadzono też porównanie efektywności nowych algorytmów ze znanymi z literatury. Zamieszczono także analizę złożoności proponowanych filtrów.

EN

In this thesis formulation of the novel class of multichannel filters for color image low-level processing is introduced and evaluated. The new filter class exploits all topological connections between adjacent image pixels using the concept of digital paths, which can be seen as trajectories of virtual particle performing random walk on the image lattice. The class of filters introduced in this thesis utilizes fuzzy membership functions defined over vectorial inputs connected via digital paths. The efficiency of the new filters is compared, under a variety of performance criteria, to that of commonly used techniques, such as the vector median, the generalized vector directional filter and with anisotropic diffusion approach. It is shown that, compared to existing techniques, the filters introduced here are better able to suppress impulsive, Gaussian as well as mixed type noise in color digital images.

20

Generalized multiple importance sampling for Monte-Carlo global illumination

Csonka F., Szirmay-Kalos L., Antal G.

Machine Graphics and Vision

|

2002

|

Vol. 11, No. 1

3-20

EN

The global illumination or transport problems can be considered as a sequence of integrals, while their Monte-Carlo solutions - as different sampling techniques. Multiple importance sampling takes advantage of different sampling strategies, and combines the results obtained with them to estaglish a quasi-optimal sampling for Monte--Carlo quadratures. This offers a combination of totally different global illumination algorithms which preserves thier strengths. However, implementation of this general concept poses two problems. The solution of the global illumination problem does not contain a single integral, but a sequence of integrals that are approximated simulataneously. One objective of this paper is to generalize the fundamental theory of multiple importance sampling to sequences of integrals. The cost of the computation and the contribution of a single integral to the final result vary. On the other hand, different methods compute a sample with different computational burdens, which should also be taken into account. This paper attacks this problem and introduces the concept of computational cost in multiple importance sampling. The theoretical results are used to combine bi--directional path tracing and ray-bundle based stochastic iteration. We conclude that the combined method preserves the high initial speed of stochastic interation, but can also accurately compute the specular light paths through bi-directional path tracing.