In this thesis random walks similar to the Metropolis algorithm are investigated. Special emphasis is laid on different types of acceptance probabilities, namely Metropolis, Tsallis and Threshold Accepting. Equilibrium and relaxation properties as well as performance aspects in stochastic optimization are investigated. Analytical investigation of a simple system mimicking an harmonic oscillator yields that a variety of acceptance probabilities, including the abovementioned, result in an equilibrium distribution that is widely dominated by an exponential function. In the last chapter an optimal optimization schedule for the Tsallis acceptance probability for the idealized barrier is investigated. / In dieser Dissertation werden Random Walks ähnlich dem Metropolis Algorithmus untersucht. Es werden verschiedene Akzeptanzwahrscheinlichkeiten untersucht, dabei werden Metropolis, Tsallis und Threshold Accepting besonders betrachtet. Gleichgewichts- und Relaxationseigenschaften sowie Performanceaspekte im Bereich der stochastischen Optimierung werden untersucht. Die Analytische Betrachtung eines simplen, dem harmonischen Oszillator ähnlichen Systems zeigt, dass eine Reihe von Akzeptanzwahrscheinlichkeiten, eingeschlossen die oben Erwähnten, eine Gleichgewichtsverteilung ausbilden, die von einer Exponentialfunktion dominiert wird. Im letzten Kapitel wird der optimale Schedule für die Tsallis Akzeptanzwahrscheinlichkeit für eine idealisierte Barriere untersucht.

We study anomalous diffusion on fractals with a static external field applied. We utilise the master equation to calculate particle distributions and from that important quantities as for example the mean square displacement <r^2(t)>. Applying different bias amplitudes on several regular Sierpinski carpets we obtain maximal drift velocities for weak field strengths. According to <r^2(t)>~t^(2/d_w), we determine random walk dimensions of d_w<2 for applied external fields. These d_w corresponds to superdiffusion, although diffusion is hindered by the structure of the carpet, containing dangling ends. This seems to result from two competing effects arising within an external field. Though the particles prefer to move along the biased direction, some particles get trapped by dangling ends. To escape from there they have to move against the field direction. Due to the by the bias accelerated particles and the trapped ones the probability distribution gets wider and thus d_w<2. / In dieser Arbeit untersuchen wir anomale Diffusion auf Fraktalen unter Einwirkung eines statisches äußeres Feldes. Wir benutzen die Mastergleichung, um die Wahrscheinlichkeitsverteilung der Teilchen zu berechnen, um daraus wichtige Größen wie das mittlere Abstandsquadrat <r^2(t)> zu bestimmen. Wir wenden unterschiedliche Feldstärken bei verschiedenen regelmäßigen Sierpinski-Teppichen an und erhalten maximale Driftgeschwindigkeiten für schwache Feldstärken. Über <r^2(t)>~t^{2/d_w} bestimmen wir die Random-Walk-Dimension d_w als d_w<2. Dieser Wert für d_w entspricht der Superdiffusion, obwohl der Diffusionsprozess durch Strukturen des Teppichs, wie Sackgassen, behindert wird. Es schient, dass dies das Ergebnis zweier konkurrierender Effekte ist, die durch das Anlegen eines äußeren Feldes entstehen. Einerseits bewegen sich die Teilchen bevorzugt entlang der Feldrichtung. Andererseits gelangen einige Teilchen in Sackgassen. Um die Sackgassen, die in Feldrichtung liegen, zu verlassen, müssen sich die Teilchen entgegen der Feldrichtung bewegen. Somit sind die Teilchen eine gewisse Zeit in der Sackgasse gefangen. Infolge der durch das äußere Feld beschleunigten und der gefangenen Teilchen, verbreitert sich die Wahrscheinlichkeitsverteilung der Teilchen und somit ist d_w<2.

Robbins' problem is an optimal stopping problem where one seeks to minimize the expected rank of their observations among all observations. We examine random walk analogs to Robbins' problem in both discrete and continuous time. In discrete time, we consider full information and relative ranks versions of this problem. For three step walks, we give the optimal stopping rule and the expected rank for both versions. We also give asymptotic upper bounds for the expected rank in discrete time. Finally, we give upper and lower bounds for the expected rank in continuous time, and we show that the expected rank in the continuous time problem is at least as large as the normalized asymptotic expected rank in the full information discrete time version.

We describe the large-time moment asymptotics for the parabolic Anderson model where the speed of the diffusion is coupled with time, inducing an acceleration or deceleration. We find a lower critical scale, below which the mass flow gets stuck. On this scale, a new interesting variational problem arises in the description of the asymptotics. Furthermore, we find an upper critical scale above which the potential enters the asymptotics only via some average, but not via its extreme values. We make out altogether five phases, three of which can be described by results that are qualitatively similar to those from the constant-speed parabolic Anderson model in earlier work by various authors. Our proofs consist of adaptations and refinements of their methods, as well as a variational convergence method borrowed from finite elements theory.

<p dir="ltr"> The general design goal of low latency communication systems is to minimize the end-to-end delay while attaining the predefined reliability and throughput requirements. The burgeoning demand for low latency communications motivates a renewed research interest of the tradeoff between delay, throughput, and reliability. In this dissertation research, we consider slotted-based systems and explore the potential advantages of the so-called sequential codes in low latency network communications.</p><p dir="ltr"> The first part of this dissertation analyzes the exact error probability of random linear streaming codes (RLSCs) in the large field size regime over the stochastic independently and identically distributed (i.i.d.) symbol erasure channels (SECs). A closed-form expression of the error probability <i>p</i>_<em>e</em> of large-field-size RLSCs is derived under, simultaneously, the finite memory length α and decoding deadline Δ constraints. The result is then used to examine the intricate tradeoff between memory length (complexity), decoding deadline (delay), code rate (throughput), and error probability (reliability). Numerical evaluation shows that under the same code rate and error probability requirements, the end-to-end delay of RLSCs is 40-48% of that of the optimal block codes (i.e., MDS codes). This implies that switching from block codes to streaming codes not only eliminates the queueing delay completely (which accounts for the initial 50% of the delay reduction) but also improves the reliability (which accounts for the additional 2-10% delay reduction).</p><p dir="ltr"> The second part of this dissertation focuses on the asymptotics of the error probability of RLSCs in the same system model of the first part. Two important scenarios are analyzed: (i) tradeoff between Δ and <i>p</i>_<em>e</em> under infinite α; and (ii) tradeoff between α and <i>p</i>_<em>e</em> under infinite Δ. In the first scenario, the asymptote of <i>p</i>_<em>e</em>(Δ) is shown to be <i>ρ</i>Δ^-1.5<i>e</i>^-^<em>η</em>^Δ. The asymptotic power term Δ^-1.5 of RLSCs is a strict improvement over the Δ^-0.5 term of random linear block codes. A pair of upper and lower bound on the asymptotic constant <i>ρ</i> is also derived, which are tight (i.e., identical) for one specific class of SECs. In the second scenario, a refine approximation is proposed by computing the parameters in a multiterm asymptotic form, which closely matches the exact error probability even for small memory length (≈ 20). The results of the asymptotics can be further exploited to find the <i>c</i>-optimal memory length <i>α</i>_<em>c</em>^*(Δ), which is defined as the minimal memory length α needed for the resulting <i>p</i>_<em>e</em> to be within a factor of <i>c</i>>1 of the best possible <i>p</i>_<em>e</em>^<em>*</em>_{<em> </em>}for any Δ, an important piece of information for practical implementation.</p><p dir="ltr"> Finally, we characterize the channel dispersions of RLSCs and MDS block codes, respectively. New techniques are developed to quantify the channel dispersion of sequential (non-block-based) coding, the first in the literature. The channel dispersion expressions are then used to compare the levels of error protection between RLSCs and MDS block codes. The results show that if and only if the target error probability <i>p</i>_<em>e</em> is smaller than a threshold (≈ 0.1774), RLSCs offer strictly stronger error protection than MDS block codes, which is on top of the already significant 50% latency savings of RLSCs that eliminate the queueing delay completely.</p>

Anomale Diffusion ist ein weitverbreiteter Transportmechanismus, welcher für gewöhnlich mit ensemble-basierten Methoden experimentell untersucht wird. Motiviert durch den Fortschritt in der Einzelteilchenverfolgung, wo typischerweise Zeitmittelwerte bestimmt werden, entsteht die Frage nach der Ergodizität. Stimmen ensemble-gemittelte Größen und zeitgemittelte Größen überein, und wenn nicht, wie unterscheiden sie sich? In dieser Arbeit studieren wir verschiedene stochastische Modelle für anomale Diffusion bezüglich ihres ergodischen oder nicht-ergodischen Verhaltens hinsichtlich der mittleren quadratischen Verschiebung. Wir beginnen unsere Untersuchung mit integrierter Brownscher Bewegung, welche von großer Bedeutung für alle Systeme mit Impulsdiffusion ist. Für diesen Prozess stellen wir die ensemble-gemittelte quadratische Verschiebung und die zeitgemittelte quadratische Verschiebung gegenüber und charakterisieren insbesondere die Zufälligkeit letzterer. Im zweiten Teil bilden wir integrierte Brownsche Bewegung auf andere Modelle ab, um einen tieferen Einblick in den Ursprung des nicht-ergodischen Verhaltens zu bekommen. Dabei werden wir auf einen verallgemeinerten Lévy-Lauf geführt. Dieser offenbart interessante Phänomene, welche in der Literatur noch nicht beobachtet worden sind. Schließlich führen wir eine neue Größe für die Analyse anomaler Diffusionsprozesse ein, die Verteilung der verallgemeinerten Diffusivitäten, welche über die mittlere quadratische Verschiebung hinausgeht, und analysieren mit dieser ein oft verwendetes Modell der anomalen Diffusion, den subdiffusiven zeitkontinuierlichen Zufallslauf. / Anomalous diffusion is a widespread transport mechanism, which is usually experimentally investigated by ensemble-based methods. Motivated by the progress in single-particle tracking, where time averages are typically determined, the question of ergodicity arises. Do ensemble-averaged quantities and time-averaged quantities coincide, and if not, in what way do they differ? In this thesis, we study different stochastic models for anomalous diffusion with respect to their ergodic or nonergodic behavior concerning the mean-squared displacement. We start our study with integrated Brownian motion, which is of high importance for all systems showing momentum diffusion. For this process, we contrast the ensemble-averaged squared displacement with the time-averaged squared displacement and, in particular, characterize the randomness of the latter. In the second part, we map integrated Brownian motion to other models in order to get a deeper insight into the origin of the nonergodic behavior. In doing so, we are led to a generalized Lévy walk. The latter reveals interesting phenomena, which have never been observed in the literature before. Finally, we introduce a new tool for analyzing anomalous diffusion processes, the distribution of generalized diffusivities, which goes beyond the mean-squared displacement, and we analyze with this tool an often used model of anomalous diffusion, the subdiffusive continuous time random walk.

Ce travail présente un développement et une analyse des approches numériques déterministes et probabilistes efficaces pour les équations aux dérivées partielles avec des coefficients et données aléatoires. On s'intéresse au problème d'écoulement stationnaire avec des données aléatoires. Une méthode de projection dans le cas unidimensionnel est présentée, permettant de calculer efficacement la moyenne de la solution. Nous utilisons la méthode de collocation anisotrope des grilles clairsemées. D'abord, un indicateur de l'erreur satisfaisant une borne supérieure de l'erreur est introduit, il permet de calculer les poids d'anisotropie de la méthode. Ensuite, nous démontrons une amélioration de l'erreur a priori de la méthode. Elle confirme l'efficacité de la méthode en comparaison avec Monte-Carlo et elle sera utilisée pour accélérer la méthode par l'extrapolation de Richardson. Nous présentons aussi une analyse numérique d'une méthode probabiliste pour quantifier la migration d'un contaminant dans un milieu aléatoire. Nous considérons le problème d'écoulement couplé avec l'équation d'advection-diffusion, où on s'intéresse à la moyenne de l'extension et de la dispersion du soluté. Le modèle d'écoulement est discrétisée par une méthode des éléments finis mixtes, la concentration du soluté est une densité d'une solution d'une équation différentielle stochastique, qui sera discrétisée par un schéma d'Euler. Enfin, on présente une formule explicite de la dispersion et des estimations de l'erreur a priori optimales. / This work presents a development and an analysis of an effective deterministic and probabilistic approaches for partial differential equation with random coefficients and data. We are interesting in the steady flow equation with stochastic input data. A projection method in the one-dimensional case is presented to compute efficiently the average of the solution. An anisotropic sparse grid collocation method is also used to solve the flow problem. First, we introduce an indicator of the error satisfying an upper bound of the error, it allows us to compute the anisotropy weights of the method. We demonstrate an improvement of the error estimation of the method which confirms the efficiency of the method compared with Monte Carlo and will be used to accelerate the method using the Richardson extrapolation technique. We also present a numerical analysis of one probabilistic method to quantify the migration of a contaminant in random media. We consider the previous flow problem coupled with the advection-diffusion equation, where we are interested in the computation of the mean extension and the mean dispersion of the solute. The flow model is discretized by a mixed finite elements method and the concentration of the solute is a density of a solution of the stochastic differential equation, this latter will be discretized by an Euler scheme. We also present an explicit formula of the dispersion and an optimal a priori error estimates.

Extracting useful knowledge from data sets is a key concept in modern information systems. Consequently, the need of efficient techniques to extract the desired knowledge has been growing over time. Machine learning is a research field dedicated to the development of techniques capable of enabling a machine to \"learn\" from data. Many techniques have been proposed so far, but there are still issues to be unveiled specially in interdisciplinary research. In this thesis, we explore the advantages of network data representation to develop machine learning techniques based on dynamical processes on networks. The network representation unifies the structure, dynamics and functions of the system it represents, and thus is capable of capturing the spatial, topological and functional relations of the data sets under analysis. We develop network-based techniques for the three machine learning paradigms: supervised, semi-supervised and unsupervised. The random walk dynamical process is used to characterize the access of unlabeled data to data classes, configuring a new heuristic we call ease of access in the supervised paradigm. We also propose a classification technique which combines the high-level view of the data, via network topological characterization, and the low-level relations, via similarity measures, in a general framework. Still in the supervised setting, the modularity and Katz centrality network measures are applied to classify multiple observation sets, and an evolving network construction method is applied to the dimensionality reduction problem. The semi-supervised paradigm is covered by extending the ease of access heuristic to the cases in which just a few labeled data samples and many unlabeled samples are available. A semi-supervised technique based on interacting forces is also proposed, for which we provide parameter heuristics and stability analysis via a Lyapunov function. Finally, an unsupervised network-based technique uses the concepts of pinning control and consensus time from dynamical processes to derive a similarity measure used to cluster data. The data is represented by a connected and sparse network in which nodes are dynamical elements. Simulations on benchmark data sets and comparisons to well-known machine learning techniques are provided for all proposed techniques. Advantages of network data representation and dynamical processes for machine learning are highlighted in all cases / A extração de conhecimento útil a partir de conjuntos de dados é um conceito chave em sistemas de informação modernos. Por conseguinte, a necessidade de técnicas eficientes para extrair o conhecimento desejado vem crescendo ao longo do tempo. Aprendizado de máquina é uma área de pesquisa dedicada ao desenvolvimento de técnicas capazes de permitir que uma máquina \"aprenda\" a partir de conjuntos de dados. Muitas técnicas já foram propostas, mas ainda há questões a serem reveladas especialmente em pesquisas interdisciplinares. Nesta tese, exploramos as vantagens da representação de dados em rede para desenvolver técnicas de aprendizado de máquina baseadas em processos dinâmicos em redes. A representação em rede unifica a estrutura, a dinâmica e as funções do sistema representado e, portanto, é capaz de capturar as relações espaciais, topológicas e funcionais dos conjuntos de dados sob análise. Desenvolvemos técnicas baseadas em rede para os três paradigmas de aprendizado de máquina: supervisionado, semissupervisionado e não supervisionado. O processo dinâmico de passeio aleatório é utilizado para caracterizar o acesso de dados não rotulados às classes de dados configurando uma nova heurística no paradigma supervisionado, a qual chamamos de facilidade de acesso. Também propomos uma técnica de classificação de dados que combina a visão de alto nível dos dados, por meio da caracterização topológica de rede, com relações de baixo nível, por meio de medidas de similaridade, em uma estrutura geral. Ainda no aprendizado supervisionado, as medidas de rede modularidade e centralidade Katz são aplicadas para classificar conjuntos de múltiplas observações, e um método de construção evolutiva de rede é aplicado ao problema de redução de dimensionalidade. O paradigma semissupervisionado é abordado por meio da extensão da heurística de facilidade de acesso para os casos em que apenas algumas amostras de dados rotuladas e muitas amostras não rotuladas estão disponíveis. É também proposta uma técnica semissupervisionada baseada em forças de interação, para a qual fornecemos heurísticas para selecionar parâmetros e uma análise de estabilidade mediante uma função de Lyapunov. Finalmente, uma técnica não supervisionada baseada em rede utiliza os conceitos de controle pontual e tempo de consenso de processos dinâmicos para derivar uma medida de similaridade usada para agrupar dados. Os dados são representados por uma rede conectada e esparsa na qual os vértices são elementos dinâmicos. Simulações com dados de referência e comparações com técnicas de aprendizado de máquina conhecidas são fornecidos para todas as técnicas propostas. As vantagens da representação de dados em rede e de processos dinâmicos para o aprendizado de máquina são evidenciadas em todos os casos

自1997年以降，受到亞洲金融風暴的衝擊，亞洲各國匯率巨幅波動，於是如何增進匯率預測的準確度已成為重要的研究課題。而自1973年布列敦森林體制崩潰，各工業國家改採浮動匯率以來，匯率巨幅波動致使國際收支理論不再能解釋匯率如何決定，於是1970年代，學者們紛紛提出各種匯率決定理論，其中以貨幣學派模型與資產組合平衡模型最受到重視。然而，自1978年始，這些結構模型的解釋能力逐漸受到質疑，在1983年Meese and Rogoff甚至提出結構模型的樣本外預測能力不如隨機漫步模型的樣本外預測表現，引起學者們的討論到底何者的樣本外預測表現較佳。而隨著計量方法的演進實證研究已由恆定的計量方法演進至非恆定的計量方法，在非恆定的計量方法方面，MacDonald and Taylor(1993、1994)、吳宜璋(1996)等人的研究皆採誤差修正模型來做預測。 本研究亦採誤差修正模型來做預測，但對其他學者的研究稍作改良：1.加入結構變動虛擬變數2.以向量誤差修正模型而非一條誤差修正的式子來做預測，在此以整個體系的觀點來做預測3.以背氏方法加入相驗情報來改善預測。 結論為在金融風暴發生期間，匯率受非基本面因素影響較大時，貝氏向量自迴歸模型預測表現較佳。而在金融風暴發生之前，匯率受基本面影響較小時，以貝氏向量誤差修正模型為良好的預測模型。 / This study improves other scholars' empirical studies by testing structure changes and by using Vector Error Correction Model to forecast N.T. Dollars. Futhermore,use Bayesian Method to improve predition .The conclusion is Bayesian VAR Model perform better when forecasting period include Asian finanl crisis . And Bayesian VECM Model is better model when forecasting period don't include Asian financial crisis.And the out of sample prediction performance of structure model is better than Random Walk Model.

本篇論文擴充Ang et al. (2007)之基本架構,分別建構台灣各式月資料與季資料的物價指數預測模型,並進行預測以及實證分析。我們用以衡量通貨膨脹率的指標為 CPI 年增率與核心CPI 年增率。我們比較貨幣模型、成本加成模型、6 種不同設定的菲力浦曲線模型、3 種期限結構模型、隨機漫步模型、 AO 模型、ARIMA 模型、VAR 模型、主計處(DGBAS)、中經院(CIER) 及台經院(TIER) 之預測。藉由此研究,我們可以完整評估出文獻上常用之各式月資料及季資料預測模型的優劣。 我們實證結果顯示,在月資料預測模型樣本外預測績效表現方面, ARIMA 模 型對 2 種通貨膨脹率指標的樣本外預測能力表現最好。至於季資料預測模型樣本外預測績效表現, ARIMA 模型對未來核心 CPI 年增率的樣本外預測能力表現最好; 然而,對於 CPI 年增率為預測目標的預測模型則不存在最佳的模型。此外,實證分析中我們也發現本研究所建構的模型預測表現仍遜於主計處的預測,但部份模型的樣本外預測能力表現則比中經院與台經院的預測為佳。 / This paper compares the forecasting performance of inflation in Taiwan. We conduct various inflation forecasting methods (models) for two inflation measures(CPI growth rate and core-CPI growth rate) by using monthly and quarterly data. Besides the models of Ang et al. (2007), we also consider some macroeconomic models for comparison. We compare some Monetary models, Mark-up models, six variants of Phillips curve models, three variants of term structure models, a Random walk model, an AO model, an ARIMA model, and a VAR model. We also compare the forecast ability of these model with three different survey forecasts (the DGBAS, CIER, and TIER surveys). We summarized our findings as follows. The best monthly forecasting model for both inflation measures is ARIMA model. For quarterly core-CPI inflation, ARIMA model is also the best model; however, when comparing the quarterly forecasts for CPI inflation, there does not exist the best one. Besides, we also found that the DGBAS survey outperforms all of our forecasting methods/models, but some of our forecasting models are better than the CIER and TIER surveys in terms of MAE.