en>Macrakis: Macrakis moved page Circuit minimization to Circuit minimization for Boolean functions: "circuit minimization" is much too broad

2013-11-17T16:05:44Z

Macrakis moved page Circuit minimization to Circuit minimization for Boolean functions: "circuit minimization" is much too broad

New page

In mathematics, a '''multiplicative cascade'''<ref>[Meakin P, PRA vol 36 No 6(1987) "Diffusion-limited aggregation on multifractal lattices"]</ref><ref>[http://uk.arxiv.org/abs/0803.3212 Cristano G. Sabiu, Luis Teodoro, Martin Hendry, arXiv:0803.3212v1 ''Resolving the universe with multifractals'']</ref> is a [[fractal]]/[[multifractal]] distribution of points produced via an iterative and multiplicative [[random process]].

[[Image:3fractals2.jpg|800px]] 
'''Model I (left plot):
: '''<math>\lbrace p_1,p_2,p_3,p_4 \rbrace = \lbrace 1,1,1,0 \rbrace</math>
'''Model II (middle plot):
: '''<math>\lbrace p_1,p_2,p_3,p_4 \rbrace = \lbrace 1,0.75,0.75,0.5 \rbrace</math>
'''Model III (right plot):
: '''<math>\lbrace p_1,p_2,p_3,p_4 \rbrace = \lbrace 1,0.5,0.5,0.25 \rbrace</math>

The plots above are examples of multiplicative cascade multifractals.
To create these distributions there are a few steps to take. Firstly, we must create a lattice of points which will be our underlying probability density field. Then we will populate this lattice with randomly placed points, insisting that the probability that the points be placed are proportional to the cell probability.

The fractal is constructed as follows: The space is split into four equal parts. Each part is then assigned a probability from the set <math>\lbrace p_1,p_2,p_3,p_4 \rbrace</math> without replacement, where <math>p_i \in [0,1]</math>. Each subspace is then divided again and assigned probabilities randomly from the same set and this is continued to the ''N''th level.

At the ''N''th level the probability of a cell being occupied is the product of the cell's ''p''''i'' and its parents and ancestors up to level 1 i.e. all the cells above it. In constructing this model down to level 8 we produce a 48 array of cells each with its own probability. To then place particle in the space we invoke a [[Monte Carlo method|Monte Carlo rejection scheme]]. Choosing ''x'' and ''y'' coordinates randomly we simply test if a random number between 0 and 1 is less or greater than the cell probability. To produce the plots above we dust the probability density field with 5,000 points in a space of 256 × 256.

An example of the probability density field: 
[[Image:Multifractal density field.jpg]]

The fractals are generally not scale-invariant and therefore cannot be considered ''standard'' [[fractals]]. They can however be considered [[multifractals]]. The Rényi (generalized) dimensions can be theoretically predicted. It can be shown <ref>Martinez et al. ApJ 357 50M "Clustering Paradigms and Multifractal Measures"</ref> that as <math>N \rightarrow \infty</math>,

: <math>D_q=\frac{\log_2\left( f^q_1+f^q_2+f^q_3+f^q_4\right)}{1-q},</math>

where N is the level of the grid refinement and,

: <math>f_i=\frac{p_i}{\sum_i p_i}.</math>

==References==
{{reflist}}

== See also ==
{{Commons|Fractal|fractals}}
* [[Fractal dimension]]
* [[Hausdorff dimension]]
* [[Scale invariance]]

[[Category:Fractals]]

Circuit minimization for Boolean functions - Revision history

en>Macrakis: Macrakis moved page Circuit minimization to Circuit minimization for Boolean functions: "circuit minimization" is much too broad