Random Walk and Fractal Growth

Random Walk and Fractal Growth I
전산물리 입문 2000/2 김승환
POSTECH NCSL (포항공대 비선형 및 컴플렉스시스템 연구실 )

invalid-file

Random Walk and Fractal Growth I 전산물리 입문 2000/2 김승환 POSTECH NCSL (포항공대 비선형 및 컴플렉스시스템 연구실 )

아이고 이런 감사할 데가... html로 보기

keywords:
random, Brownian motion, Tydall effect, random walk, mean square distance,  Monte Carlo (여기에도 나오네... 적분 방법 아니었어?), pseudo-random number generators (그래 이게 목적이겠지만.), Molecular Dynamics (MD) 방법 (방법??), self-avoiding random walk (SAW), Flory 이론, Nienhuis (??), persistent random walk, limited random walk, fractal growth, DLA (Diffusion Limited Aggregates), Chaos Game, Iterated Function System, Theory of Affine Map (->Image Processing), Benoit Mandelbrot, Fractal Geometry, Hausdorff Dimension, Koch 곡선, Box counting algorithm (Capacity dimension), 'Mountains Never Existed',



MC(Monte Carlo) code:

      if randN(m) < 0.5,

           Point(m) = Point(m)+1;

      else

           Point(m) = Point(m)-1;

      end;

randN = rand(N)
: Generate  N random number between 0 and 1

뭐니? orz... point()가 뭔데? 이렇게 짧으면 더 쓸쓸해. ㅡㅜ
그냥 좀 더 흘트린다는 건가? 뭐를? m을? 전산물리... 안 듣긴 했지만...
근데 이거 통계물리나 열물리 같은 거 아니야?
Monte Carlo N-Particle Transport Code 이거랑 관계가 있는가?
헉... 적분이랑 관계 없는 건가... Monte Carlo method -> 여기에 정리하는 중


MC 방법의 응용
    * random walks, fractal growth,
    * Equilibrium/non-equilibrium statistical phenomena, phase transition
    * neural networks
    * particle scattering with the help of computers
    * optimization
    나는 particle scattering 때문에 자주 본 거였구만.


RAND(N)
(0.0,1.0)사이의 균일한 분포를 가진 마구잡이 수로 이루어진 NxN 행렬
그럼 프로세싱에서의 random()인 건가...? 분포가 다른 건가?


S = RAND('state')
현재상태를 포함한 35-element 벡터.
RAND('state',S) resets the state to S.
RAND('state',0) resets the generator to its initial state.
RAND('state',J), for integer J, resets the generator to its J-th state.
RAND('state',sum(100*clock)) resets it to a different state each time.
포기.

ref.
K. Kremer and T. W. Lyklema, Phys. Rev. Lett. 55, 9091 (1985)
T. M. Bishtein, S. V. Buldyrev, and A. M. Elyashivitch, Polymer 26, 1814 (1985)


 Fractal Growth
- 평형으로부터 멀리 떨어진 현상 (far from equilibrium)
- 시공간적으로 매우 다양한 형태
- 해석적 연구가 매우 어려움

프랙탈 성장의 예
- 금속이온의 전기화학적 흡착에 의한 뭉침
- 고분자, 세라믹, 유리, 얇은막의 성장
- Viscous fingering
- Dielectric breakdown
- 박테리아의 성장
- 신경세포의 성장


DLA 모형

    * Diffusion Limited Aggregates
          o 프랙탈 구조를 만들 수 있음이 증명된 첫 성장 모형
          o T.A. Witten and L.M. Sander , 1981.

    * 마구걷기 모형화
          o 매우 간단함
          o 브라운운동에 기초
          o 마구걷기에 의한 확산 모형

    * 성장규칙
          o 평면상의 움직이지 않는 씨앗으로부터 시작.
          o 멀리 떨어진 곳으로부터 시작하여 마구 걷기를 수행.
          o 마구 걷기가 씨앗을 만나면 붙음.
          o 다시 마구걷기를 반복함._M#]

Mountains Never Existed
 

Iterated Function System

The concept of the Iterated Function System was invented by creative fractal genius Michael Barnsley. An IFS is composed of a few simple elements: transformations and probabilities. The transformations are usually expressed as matrices--one translational matrix and one transformational matrix. This sounds a bit dry, but actually the concept is a bit more interesting than all that. For the Sierpinski Triangle, the transformations are simple, and are better expressed as rules in a recursive procedure:

          Begin by selecting three vertices in the two-dimensional plane. Note their coordinates. Next, select an initial point--best if within the bounds of the triangle formed by the three vertices, but this is not a requirement. The main procedure goes as follows.

          Select one of the three vertices at random.

          Roll a six sided die and integer-divide by two, flip three coins and take the exception, or ask a friendly computer for help.

          From the current location of the point, calculate the midpoint of the line connecting the point and the vertex just selected.

          Move to this midpoint, and plot the point.

          Iterate ad infinitum.

That's it! Sierpinski's Triangle. To get any sort of worthwhile picture, of course, hundreds to thousands of points need to be plotted. In fact, usually the first twenty or so points are off track and need not be plotted. However, the algorithm outlined above is amazingly simple to do, and incredibly easy to implement on any machine. I have written Sierpinski programs for every graphing calculator under the sun, as well as for most desktop computers as well. Try

it yourself in BASIC or on a graphing calculator. You'll surprise yourself at how easy it is to impress people with a graphing calculator. :)
 
 

How Long is the Coast?

     A long, long time ago, fractal god Benoit Mandelbrot posed a whimsical question: How long is the coastline of Britain? His mathematical colleagues were miffed, to say the least, at such annoying waste of their amazing computation powers on this insignificant minutae. They told him to look it up.

     Of course, Mandelbrot had a reason for his peculiar question. Quite an interesting reason. Look up the coastline of Britain yourself, in some encyclopedia. Whatever figure you get, it is wrong. Quite simply, the coastline of Britain is infinite. You protest that this is impossible. Well, consider this. Consider looking at Britain on a very large-scale map. Draw the simplest two-dimensional shape possible, a triangle, which circumscribes Britain as closely as possible. The perimeter of this shape approximates the perimeter of Britain.However, this area is of course highly inaccurate. Increasing the amount of vertices of the shape going around the coastline, and the area will become closer. The more vertices there are, the closer the circumscribing line will be able to conform to the dips and the protrusions of Britain's rugged coast.There is one problem, however. Each time the number of vertices increases, the perimeter increases. It  must increase, because of the triangle inequality. Moreover, the number of vertices never reaches a

     maximum. There is no point at which one can say that a shape defines the coastline of Britain. After all, exactly circumscribing the coast of Britain would entail encircling every rock, every tide pool, every pebble which happens to lie on the edge of Britain. Thus, the coastline of Britain is infinite.

The dependence of length (or area) measurements on scale poses great problems for biologists who need to use the results. For example, lakes that have a very convoluted shoreline are known to offer more area of shallows in relation to their total surface area, and thus support richer communities of plant and animal life. Attempts to characterize shore-line communities in terms of indexes that relate water surface to shoreline length have been frustrated by problems of scale.
 

Fractal dimension

The notion of "fractional dimension" provides a way to measure how rough fractal curves are. We normally consider lines to have a dimension of 1, surfaces a dimension of 2 and solids a dimension of 3. However, a rough curve (say) wanders around on a surface; in the extreme it may be so rough that it effectively fills the surface on which it lies. Very convoluted surfaces, such as a tree's foliage or the internal surfaces of lungs, may effectively be three-dimensional structures. We can therefore think of roughness as an increase in dimension: a rough curve has adimension between 1 and 2, and a rough surface has a dimension somewhere between 2 and 3. The dimension of a fractal curve is a number that characterizes the way in which the measured length between given points increases as scale decreases. Whilst the topological dimension of a line is always 1 and that of a surface always 2, the fractal dimension may be any real number between 1 and 2. The fractal dimension D is defined by

         log ( L2 / L1 )

     D = ---------------           ... (1)

         log ( S1 / S2 )

where L1, L2 are the measured lengths of the curves (in units), and S1, S2 are the sizes of the units (i.e. the scales) used in the measurements.

Van Koch Curve

This is the Von Koch curve. Its construction is almost as easy as the Sierpinski Triangle. You start with a triangle (equilaterality is really more important in this case than for the Sierpinski Triangle), and, on each side, tack on little equilateral triangles, so you end up with a shape very much like a Star of David. The Star of David has six little triangles sticking out. For each triangle, repeat the previous process. Iterate infinitely.

Recall that when we discussed the Koch Curve in figure 4(b), we had four chunks that were small copies of the whole curve. Each chunk could be magnified by 3 to return a copy the same size as the original curve. Plugging these values into the above equation, we get

                     Ds = log4 /log3= 1.262

This is a value we would have expected. Because the curve is more intricate than a 1-dimensional line segment (it wanders around on the plane some), we would expect its fractal dimension to be greater than 1. But it doesn't come very close to filling an area of the 2-dimensional plane, so we would expect the curve's fractal dimension to be much smaller than 2. The Koch Curve is indeed a fractal. It is self-similar and it has a fractional dimension of about 1.262.

Sierpinsky Gasket

Now the Sierpinski Gasket of figure 2 comes a little closer to filling a 2-dimensional triangle, so we will expect it to have a fractal dimension closer to 2. Recall that we have 3 subtriangles that can be magnified by 2 to get back a copy the same size as the original. Plugging those values into the Self-Similarity dimension equation, we get

                                    Ds = log3/log2= 1.585

The Sierpinski Gasket is therefore a fractal--It is self-similar and its fractional dimension is about 1.585.  We have now investigated two bonafide fractals. Both the Sierpinski Gasket and the Koch Curve satisfy Devaney's two criteria for being a fractal: self-similarity and fractional dimension.