applicationsapplied-mathematicsbilliardsds.dynamical-systems
Recently I gave an interview to local media where I explained some basic open problems in billiard dynamics.
After a 45 min interview the reported asked me what "real life" problems can be solved using billiards…and I gave a really vague answer.
I'm looking for a precise example of a "real life" problem (besides the billiard game of course) that can be modeled using billiard dynamics.
"real life" = applied (I'm not english native speaker)
Complex networks is a young and active area of scientific research inspired largely by the empirical study of real-world networks such as computer networks, social networks, biological networks, ecological networks, telecommunication networks etc. A lot of interesting and important properties of complex networks were found by statistics such as sparsity, small world phenomenon (also called six degree separation, for example, from the ‘small world’ studies of Harvard sociologist Stanley Milgram[1], play of Guare [2], Hands shaking(Watt’s father remarks that he was only six handshakes away from the president of US) example of Watts[3]), power law distribution(also called long tail or heavy tail distribution or scale free, Barabási and Albert [4] noticed actor collaboration networks and World Wide Web had power law distribution).
The field continues to develop at a brisk pace, and has brought together researchers from many areas including mathematics, physics, biology, telecommunications, computer science, sociology, epidemiology, and others[5].
To set up the foundations of complex network, the first step is to define some new metrics. There are a lot of different metrics widely used in complex networks such as average degree, diameter, entropy, average distance, centrality, betweenness, density, clustering coefficient, transitivity, diffusion time etc.
How to model complex networks is one big issue in this area. Traditional well known model such as the popular Erdős-Rényi random network model does not fit on the real world network so well in most cases. For example, although Erdős-Rényi random network has small diameter, but have very few triangles, which is not like in social networks the friends of one person tend to be friends, too. Scientists are trying to find new mathematical models for complex networks.
For small world model, Watts and Strogatz [6] started from ring lattice with $n$ vertices and $k$ edges per vertex , and then rewired each edge with probability $p$, connecting one end to a vertex chosen at random, this can drastically reduce the diameter. Bollobás and Chung [7] added a random matching to a ring of $n$ vertices with nearest neighbor connections and showed the resulting graph had diameter $\sim\log n$. This model is called BC small world, however, this is weak in social network. Newman and Watts [8] (NW small world)added a Poisson number of shortcuts with mean $n\rho/2$ instead of rewiring edges, and then attaches them to randomly chosen pairs of sites. This results in a Poisson mean $\rho$ number of long distance edges per site.
For Power Law distribution model, Barabási and Albert [4] found some real world network such as actor collaboration networks and World Wide Web had degree distributions $p_k\sim Ck^{-\gamma}$ as $k\rightarrow \infty$. Usually $\gamma$ is between $2$ and $3$, but Liljeros et al. [9] found $\gamma_{male}=3.3$ and $\gamma_{female}=3.5$ by analyzing the data of sexual behavior of 4781 Swedes. Ebel et al. [10] found $\gamma=1.81$ by studying email network of Keil University. Newman[11][12][13] found the number of collaborators was better fit by a power law with an exponential cutoff $p_k\sim Ck^{-\tau}exp(-k/k_c)$ in collaboration network. Later, scholars found other values of $\gamma$. Barabási and Albert [4] introduced the preferential attachment model to give a mechanism explanation for power law distribution. Whether this model still keeps small world property? Bollobás and Riordan [14] showed for this model, the diameter $\sim \log n/(\log \log n)$. Chung and Lu[15][16] showed for their corresponding model (known as Chung-Lu model) has the distance between to randomly chosen vertices is $O(\log n/(\log \log n))$. Callaway, Hopcroft, Kleinberg, Newman and Strogatz [17] introduced CHKNS model inspired by Barabási and Albert [4].
Just name a few. Further details and more models are referenced to [18][19].
However, it is difficult to find a model which can fit perfectly on the real world networks in every aspect. Now the research in this area is usually data and application driven. For example, they study application problems such as influence maximization, community detection, rumor detection, recommender system, PageRank etc. , in which they design algorithm or mechanism and use some real world network data to make simulation to test the quality of algorithms, usually they don’t care too much about the model itself. But the big issue without an exact mathematical model is large scale data is hard to handle, thus some sparse optimization and large scale optimization techniques were introduced.
For other application such as the famous Kidney Exchange Long Chain mechanism of Al Roth, who won Nobel Prize, dynamic homogeneous random graph [20], Random compatibility graphs[21], sparse graphs [21]etc. were used. Those models are more mathematical than better fitting on the real world networks.
In communication networks, such as ad hoc sensor network, it is not small world nor power law distribution, random geometry network or other models are used.
[1] S. Milgram, “The small world problem,” Psychology Today, vol. 2, no. 1, pp.60–67, 1967.
[2] J. Guare, Six Degrees of Separation: A Play. New York: Vintage, 1990.
[3] Watts, Duncan J. Six degrees: The science of a connected age. WW Norton & Company, 2004.
[4] Barabási, Albert-László, and Réka Albert. "Emergence of scaling in random networks." science 286.5439 (1999): 509-512.
[5] A.E. Motter, R. Albert (2012). "Networks in Motion". Physics Today 65 (4): 43–48.
[6] Watts, Duncan J., and Steven H. Strogatz. "Collective dynamics of ‘small-world’networks." nature 393.6684 (1998): 440-442.
[7]Bollobás, Bela, and Fan R. K. Chung. "The diameter of a cycle plus a random matching." SIAM Journal on discrete mathematics 1.3 (1988): 328-333.
[8] Newman, Mark EJ, and Duncan J. Watts. "Renormalization group analysis of the small-world network model." Physics Letters A 263.4 (1999): 341-346.
[9]Liljeros, Fredrik, et al. "The web of human sexual contacts." Nature 411.6840 (2001): 907-908.
[10] Ebel, Holger, Lutz-Ingo Mielsch, and Stefan Bornholdt. "Scale-free topology of e-mail networks." Physical review E 66.3 (2002): 035103.
[11] Newman, Mark EJ. "The structure of scientific collaboration networks." Proceedings of the National Academy of Sciences 98.2 (2001): 404-409.
[12] Newman, Mark EJ. "Scientific collaboration networks. I. Network construction and fundamental results." Physical review E 64.1 (2001): 016131.
[13] Newman, Mark EJ. "Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality." Physical review E 64.1 (2001): 016132.
[14] Bollobás, Béla, and Oliver Riordan. "The diameter of a scale-free random graph." Combinatorica 24.1 (2004): 5-34.
[15] Chung, Fan, and Linyuan Lu. "Connected components in random graphs with given expected degree sequences." Annals of combinatorics 6.2 (2002): 125-145.
[16] Chung, Fan, and Linyuan Lu. "The average distance in a random graph with given expected degrees." Internet Mathematics 1.1 (2004): 91-113.
[17] Callaway, D. S., Hopcroft, J. E., Kleinberg, J. M., Newman, M. E., & Strogatz, S. H. (2001). Are randomly grown graphs really random?. Physical Review E, 64(4), 041902.
[18] Chung, Fan RK, and Linyuan Lu. Complex graphs and networks. Vol. 107. Providence: American mathematical society, 2006.
[19] Durrett, Richard. Random graph dynamics. Vol. 200. No. 7. Cambridge: Cambridge university press, 2007.
[20] Ashlagi, Itai, Patrick Jaillet, and Vahideh H. Manshadi. "Kidney exchange in dynamic sparse heterogenous pools." arXiv preprint arXiv:1301.3509 (2013).
[21] Ashlagi, Itai, et al. The need for (long) chains in kidney exchange. No. w18202. National Bureau of Economic Research, 2012.
As remarked by Joe Silverman, a natural way to look at this question is by phrasing it in terms of the map $f(x):=\frac{1}{2}x(x+1)$ on the $2$-adic integers $\mathbb{Z}_2$. We are then asking about the behaviour of the orbit $f^n(2)$ with respect to the partition of $\mathbb{Z}_2$ into two clopen sets $U_1:=2\mathbb{Z}_2$ and $U_2:=1+2\mathbb{Z}_2$. Most questions of this form are very hard, for reasons which I will attempt to explain. Short answer: dynamically, there is no obvious reason why this should be easier than the Collatz problem or the normality of $\sqrt{2}$.
Suppose that we are given a continuous transformation $f$ of a compact metric space $X$ and a partition of $X$ into finitely many sets $U_1,\ldots,U_N$ of reasonable regularity (e.g. such that the boundary of each $U_i$ has empty interior). We are given a special point $x_0$ and we want to know how often, and in what manner, the sequence $(f^n(x_0))_{n=1}^\infty$ visits each of the sets $U_i$. We might believe the following result to be useful: if $\mu$ is a Borel probability measure on $X$ such that $\mu(f^{-1}A)=\mu(A)$ for every Borel measurable set $A\subset X$, and if additionally every $f$-invariant measurable set $A\subseteq X$ satisfies $\mu(A)\in \{0,1\}$, then $$\lim_{n\to\infty}\frac{1}{n}\sum_{i=0}^{n-1}\phi(f^i(x)) =\int \phi\,d\mu$$ for $\mu$-almost-every initial point $x$ and every $\mu$-integrable function $\phi \colon X \to \mathbb{R}$. This is the Birkhoff ergodic theorem or pointwise ergodic theorem. In particular we could take $\phi$ to be the characteristic function of a partition element $U_i$, so the above measures the average time spent in $U_i$ by the sequence $f^n(x)$. Or we could take $\phi$ to be the characteristic function of a set such as $U_1\cap f^{-1}U_2 \cap f^{-2}U_1$, which would tell us how often the orbit of $x$ follows the path $U_1 \to U_2 \to U_1$, and so on.
The Birkhoff theorem is great if we are content to study points $x$ which are generic with respect to a particular invariant measure. If we want to study a specific $x$ then we have no way to apply the theorem. If multiple different invariant measures $\mu$ exist then the integrals which they assign to the characterstic functions $\chi_{U_i}$ will in general be different and we will get different answers, and the Birkhoff averages along orbits will have fundamentally different behaviours depending on which measure the starting point is generic with respect to (if any). In a broad sense this is an aspect of the phenomenon called "chaos". Here is a nice example: let $X=\mathbb{R}/\mathbb{Z}$, $f(x):=2x$, let $U_1=[0,\frac{1}{2})+\mathbb{Z}$ and $U_2=X\setminus U_1$. What can we say about the manner in which the trajectory $f^n(\sqrt{2})$ visits $U_1$ and $U_2$? For example, does the trajectory spend an equal amount of time in both sets? Put another way, is $\sqrt{2}$ normal to base $2$? Dynamical methods can tell us that Lebesgue a.e. number is normal to base $2$, but they struggle badly for specific numbers. The difficulty of this problem is tied quite closely to the existence of many invariant measures for this map: Lebesgue measure is invariant, but so is the Dirac measure at $0$; there are many invariant measures supported on closed $f$-invariant proper subsets corresponding to restricted digit sets (e.g. numbers where "11" is not allowed in the binary expansion) and also many fully supported invariant measures which are singular with respect to Lebesgue measure (and indeed with respect to one another). Each invariant measure contributes a set of points with its own particular, distinct dynamical behaviour, and given an arbitrary point we have no obvious way of knowing which of these different dynamical behaviours prevails.
There is only one situation in which this dynamical problem becomes easy: when a unique $f$-invariant Borel probability measure exists. In this case the convergence in the Birkhoff theorem is uniform[*] over all $x$, and the problem of distinguishing which invariant measure (if any) characterises the behaviour of the trajectory $f^n(x)$ vanishes completely. An example would be the leading digit of $2^n$: take $X=\mathbb{R}/\mathbb{Z}$, $U_k=[\log_{10}k,\log_{10}(k+1))+\mathbb{Z}$ for $k=1,\ldots,9$, $f(x):=x+\log_{10}2$, then the leading digit of $2^n$ is $k$ if and only if $f^n(0) \in U_k$. The irrationality of $\log_{10} 2$ may be applied to show that Lebesgue measure is the only $f$-invariant Borel probability measure, and using the uniform ergodic theorem we can simply read off the average time spent in each $U_k$ as the Lebesgue measure of that interval.
So how does this affect $f(x):=x(x+1)/2$ on $\mathbb{Z}_2$? Well, $x=1$ and $x=0$ are both fixed points and carry invariant Borel probability measures $\delta_1$ and $\delta_0$. So the dynamical system is not uniquely ergodic, and the problem of determining which of the (presumably many) invariant measures characterises the trajectory of the initial point $2$ has no obvious solution.
[*] to obtain uniform convergence in this case $\phi$ must be a continuous function. By upper/lower approximation we can deduce pointwise convergence to $\int \phi\,d\mu$ for all $x\in X$ in the case where $\phi$ is upper or lower semi-continuous, for example where $\phi$ is the characteristic function of a closed or open set.
Best Answer
The billiard-ball computer was never realized in this form, but it played a significant role in the development of the quantum computer. Since the unitary evolution of quantum mechanics is reversible, it cannot employ the irreversible logical operations of a conventional computer. (This story is told here.)
For an altogether different application of billiard ball dynamics, to semiconductor device physics, see Billiard model of a ballistic multiprobe conductor (1989).