{'fraction_non_alphanumeric': 0.050047295554217906, 'fraction_numerical': 0.017628342935764037, 'mean_word_length': 3.984997856836691, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Wind-tree model for billiard motion from a signal processing viewpoint

In the Ehrenfest wind tree model, a point particle moves on the plane and collides with randomly placed fixed square obstacles under the usual law of geometric optics. The particle represents the wind and the squares are the trees. We examine the periodic version of the model. Previous authors analyze the dynamical properties of the model using techniques from algebraic topology or ergodic theory. In contrast to these works, we adopt a signal processing viewpoint. We describe the phenomenon of the long-term trajectories by using a 3-state hidden Markov model.


Introduction and Motivation
In the wind tree model introduced by P. Erhenfest and T. Ehrenfest in 1912, a point particle moves on the plane and collides with randomly placed fixed square obstacles under the usual law of geometric optics. The particle represents the wind and the squares are the trees. We investigate the periodic version of the model, where identical square obstacles are placed periodically in the plane. Our aim is to understand some of it dynamical properties (see Figure 1 for the position of the billiard after 15 collisions with the obstacles.) Previous authors analyze the dynamical properties of the model using techniques from algebraic topology (see [1], [2], [3], [4]). In this paper we take a somewhat different point of view than these works. We assume no knowledge of algebraic topology. Instead, we take a signal processing viewpoint and use a hidden Markov model with three hidden states to study the phenomenon we observe.
The billiard trajectory is characterized by a direction at the initial position. This direction is specified by the tangent of the angle with a horizontal line parallel to the plane. The slope m of the initial velocity vector corresponds to the angle θ, i.e. m = tan θ. Henceforth, we can refer to either the direction θ or the initial slope m.

Background and Related Works
In the periodic version of the Erhenfest wind tree model, due to J. Hardy and J. Weber ( [10]), the obstacles are identical rectangular blocks located periodically in the plane, every obstacle centered at each point of Z 2 . The blocks are rectangles of size a × b, with 0 < a < 1, 0 < b < 1. We denote by T (a, b) the subset of the plane obtained by removing the obstacles and name its billiard the wind tree model. Let φ θ t : T (a, b) → T (a, b) be the billiard flow: for a point p ∈ T (a, b), the point φ θ t (p) is the position of a particle after time t starting from position p in direction θ. Let d be the Euclidean distance in R 2 . The flow in direction θ is recurrent, if for almost all points x in T (a, b), we have lim inf t→∞ d(x, φ θ t (x)) = 0. The flow in direction θ is divergent, if for almost all points x in T (a, b), we have lim inf t→∞ d(x, φ θ t (x)) = ∞. Delecroix [3] proves the following result about the set of parameters (a, b, θ) for which the flow in T (a, b) in direction θ is divergent.
there exists a dense set Λ ∈ [0, 2π) of Hausdorff dimension not smaller than 1/2 such that for every θ ∈ Λ and every point x in T (a, b) with infinite forward orbit lim inf t→∞ d(x, φ θ t (x)) = ∞. In particular the flow φ θ t is divergent.
Delecroix, Hubert, and Lelièvre ( [2]) determine the rate of diffusion of the orbits which is valid for almost all direction θ. Theorem 2. Then for all parameters (a, b) ∈ (0, 1) 2 , Lebesgue-almost all θ and every point p in T (a, b) (with an infinite forward orbit) Remark: The implication is significant. If we change the height and the width of the obstacle, we can get different billiard trajectories, but this does not change the diffusion rate. To understand the dynamical properties of the billiard motion, it is enough to take all the obstacles to be square blocks.
This theorem is impressive because it is valid for almost all direction θ (in the sense of Lebesgue measure). The set of rational numbers Q is a set of Lebesgue measure 0, therefore, if tan θ ∈ Q, we cannot conclude from the theorem whether the particle with direction θ is recurrent or divergent.
We adopt the following setting in the remainder of this manuscript: (1) All obstacles are square blocks of side length 1.
(2) The particle starts at the origin.
(3) The centers of the blocks are the ordered pairs of all the odd integers.
This setting implies that the first obstacle to the northeast of the origin has its bottom left corner at (0.5, 0.5) and its bottom right corner at (1.5, 0.50) with its center at (1, 1). Two adjacent square blocks are at distance one apart. There is no loss of generality in choosing this specific setting (see the Remark).
Sections 3 and 4 contain illustrations for the position of the particle after N collisions with the square blocks. Section 5 shows two experiments for billiard trajectories after 500 collisions, from which we can identify some patterns. These simulations suggest that there are three types of motions. Section 6 reviews some important definitions and notations in hidden Markov processes, also known as hidden Markov models. Section 7 describes how a 3-state hidden Markov process is adequate to model a dynamical property of the periodic wind-tree model.

Illustrations: Part 1
Initial slope = 1.414 These figures show the position of the particle after N collisions with square blocks.
Motion of billiard after 50 collisions, after 100, 150, and 300 collisions.   We can see that a pattern emerges after 1000 collisions. (1). Recurrent (e.g. when initial slope = 1.414) (2). Divergent in a quasi-periodic way (e.g. when initial slope = 1.732) (3). Divergent rapidly (e.g. when initial slope = 1.618) In the above classification, we use the term quasi-periodic in (2). We say that the motion is quasi-periodic if there is a T , a quasi-period τ , and a small number > 0, such that the y-coordinate y(t) of the particle at time t satisfies for all t > T . The number τ can depend on the time t. We observe recurrent motion. Figure 8 shows the particle almost returns to original position. (1) P r(X(t) |X (t−1) , C (t) ) = P r(X(t) |C t )

Hidden Markov process
In applications, the Marko chain {C t } can represent a coin process or some hidden conditions. For example, the daily return of stock prices {X(t)}, is influenced by the market condition {C t }, a Markov chain which is not directly observable. To illustrate the notation, we denote the history of the coin up to time t = 4 by C (4) = {C 1 , C 2 , C 3 , C 4 }. The main assumption for Hidden Markov model is P r( X(4) = 1| X(1), X(2), X(3), C (4) ) = P r(X(4) = 1| C 4 ) Notation: We denote the probability for the coin at time t by δ i = P r(C t = i) for t = 1, 2, 3, . . . , T.
Let p i be the probability mass function of X(t) when the Markov chain is in state i at time t. p i (x) = P r(X(t) = x|C t = i).
As a consequence, if there are m possible outcomes for the coin, then Key assumption: {C t } is a homogeneous Markov chain. That means, does not depend on t. It is a number that depends on i and j. We define Γ is a probability transition matrix, whose entry in row i and column j is the probability that the coin at time t + 1 will be in state j, given that the coin is in state i at time t.
The likelihood at time t = T is given by The likelihood can be conveniently expressed in matrix notation, where P(x) is defined to be the diagonal matrix whose (i, i) entry is p i (x). Here, 1 denotes a column vector of ones.
To estimate the parameters of the model, we maximize the likelihood. This can be done by the Baum-Welch algorithm ( [8], [9], [11], [14]), which is in effect one of the earliest instances of the EM algorithm ( [6]). In the E step of the algorithm, we infer the probabilities of the hidden states C t from the observations X(t) = x t . Then, in the M step, we update the parameters of the model by maximizing the likelihood, conditional on the hidden states.
The computation in the M step is straightforward. The challenging part is in the E step of the EM algorithm. We include the details in section 8 for completeness.

Model Results
In this section, we describe how a 3-state hidden Markov process is adequate to model a dynamical property of the periodic wind-tree model.
Let d(k) be the distance of the particle from the origin, after k collisions with the square blocks. Let m = tan θ be the initial slope. Let D(θ) be the minimum distance of the particle from the origin, between the 500 th and 1000 th collision, when the initial slope is m = tan θ. To be precise, We consider T = 300 values of m, starting from tan θ 1 = For each value of m, we compute log D(θ). The random process X(t) is defined by where θ 1 = 1.4140, θ 2 = 1.4165, θ 3 = 1.4190, . . . , θ T = 2.1615.
To model this random process {X(t) : 1 ≤ t ≤ T }, we use a hidden Markov model with 3 states, so that conditional on state C t = j, the random variable X(t) is normally distributed with mean µ j and variance σ 2 j . The parameters of the 3-state normal-HMM are estimated from the observations {X(t), t = 1, 2, 3, . . . , T }.
To start the EM algorithm, the probability transition matrix Γ is initialized so that all three diagonal entries are set to 0.8 and all the off-diagonal entries are set to 0.1. This initialization is arbitrary.
By applying the EM algorithm, the parameters of the model after 15 iterations are:  We can interpret the states in the 3-state hidden Markov model so that the states match the 3 types of patterns we observed in Experiment 1 from section 5. For example, state 1 can represent recurrent motion. We caution against the tendency to over-interpret, since we know of no convincing reason to give physical interpretation to each state. Models need not be interpretive; they can be useful as empirical models. We are using model as empirical model, in the sense Cox ([7]) uses that term.
In generalized linear models, it is common to use residuals as a tool to check the validity of the fitted model. The residuals are calculated from the expected observation and the actual observation. Pseudo-residuals are intended to fulfill the same role as the residuals, in the context of HMMs. The uniform pseudo-residual for the observation x t is where X(t) is a continuous random variable and F is its cumulative distribution function (c.d.f.). The diagrams of the pseudo-residuals and the series X(t) are shown (for ease of viewing, the figure shows 100 values of X(t), from t = 1.5390 to 1.7865). We check the histogram for the pseudo-residuals, as a model diagnostic. None of the 10 bins deviate significantly from 30. The highest value among the 10 bins is 48, and the smallest is 19. We conclude that the model is adequate.

Probabilities of the hidden states
In this section, we state and prove the main proposition for computing the probabilities for the hidden states C t in the E step of the EM algorithm. We include the details here for completeness. Before we can state the proposition, we need to describe the forward and backward probabilities. For the sake of clear exposition, we illustrate this with 5 time periods. Suppose T = 5. The likelihood at time t = T is given by where we applied formula (2) from section 6 in the last line.
Forward probabilities Backward probabilities The forward and backward probabilities are related to the likelihood.

Acknowledgements
The first author is grateful for the financial support of an Undergraduate Summer Research Program (USRP) grant from DePaul University.
The second author is grateful that the Undergraduate Summer Research Program (USRP) grant from DePaul University makes this research project possible.