text:
# Diffusion and Aggregation in an Agent Based Model of Stock Market Fluctuations

## 1 Introduction

In recent years many microsimulation models of financial markets are being developed  (see  for a review). All these models emphasize some aspects of the traders and their behaviour. In  agents aggregate in percolation lattices to model the tendency of traders to imitate each other; in a variant  of this model the agents are allowed to diffuse on the lattice to induce autocorrelation in volatility; in  the agents are equipped with a capital that they reinvest and accumulate while in  the authors distinguish among liquidity and stocks at the current nominal price. Moreover, some models (the first example is found in ) take into account the different tendency to follow a *perceived price* for the assets while  illustrates different strategies for value trades some of which are much more realistic than the simple random buy/sell/inactive choice of .

The present model incorporated many of these features into a single versatile model. The main goal is to give an easy way to implement different key issues in modeling the stock market, to understand the relevance and the mutual influence of certain factors that other models have treated separately, and to investigate the necessary and sufficient conditions determining the factors which actually drive the empirical observed facts in real markets.

The word “agents” in the title of this article can be misleading due to the fact that traders in financial markets are also called *agents*. Instead we refer to the idea of agents in the “agent-based models” in the simulation and modeling paradigm. The modeling and simulation of real systems consisting of agents that cooperate with each other has emerged as an important field of research. They are regarded as a consistent paradigm enabling an important step forward in empirical sciences, technology and theory . To model the dynamics of a complex system composed of interacting entities with their internal complex structure and dynamics has many appealing points: self organization strategies and decentralized control, emergent behaviour, autonomous behaviour, cooperative capacity and aggregation, and spatial mobility.

The purpose of the model hereafter described is to provide a relatively simple description of the price formation in a stock market. The agents paradigm is most suited to accomplish this task. Our personal experience in modeling other complex systems rather than financial markets (in biology and in particular in immunology ) tell us that complex systems need versatile and powerful methods to be simulated with a certain degree of realism.

This paper is organized as follows: in section 2 we will present the model, in section 3 we will discuss its dynamics presenting the results of some simulations and in section 4 we point out some further developments.

## 2 Model description

In this model we consider two kinds of agents representing what are called *chartists* and *fundamentalists* .

The first are traders and speculators whose strategy depends exclusively on the price history. They are known also as *technical traders*. For the time being, we model the chartists as traders who base their decision only on the “current” value of the price and not on a real historical evaluation of the “trend”.

The other kind of traders, the fundamentalists, consider the “fundamental” value to determine the “right” price of an asset. To do so we consider an artificially generated time series as the perceived just price for the traded asset.
Fundamentalists are also called *value-traders*. Value-strategies are based on perceived value, that is a model for what something ought to be worth, which not necessarily corresponds to the actual value. The perceived value is inherently subjective and at a first approximation it is considered external information. Basically, value strategies tend to buy when an asset is undervalued and sell when it is over-valued.

This distinction between the two kind of traders is mostly reflected in the different way they decide, at each time step, to buy or to sell a stock. This will be treated in section 2.1.

Each agent $`i`$ is represented by some attributes. The order at time $`t`$ $`x_t^{(i)}\{+1,0,1\}`$, indicates respectively the decision to buy, to sell or to stay inactive. The capital $`c_t^{(i)}`$ of agent $`i`$ at time $`t`$ is the current amount of money or credits. Each agent starts with a certain capital of money with which (s)he can buy stocks. The decision to buy/sell is then constrained by the availability of stocks to be sold or funds to buy other stocks. Agents reinvest their profit and accumulate capital. The number of owned stocks of agent $`i`$ is indicated by $`n_t^{(i)}`$. At each time step, the owned stocks account for the actual wealth of the trader with the current nominal price of the asset $`p_t`$.

Along with the agents we need to define how an asset is represented in our artificial stock market, that is, how the price is determined. The current price $`p_t`$ is computed every time step by a single market maker. While the traders observe the actual price or the perceived price and submit orders $`x_t^{(i)}`$, the market maker fills all orders at the new price $`p_{t+1}`$ according to a certain increasing function of the excess demand $`p_{t+1}\zeta (p_t,D_t)`$ where $`D_t=_ix_t^{(i)}`$ denotes the total excess demand a time $`t`$. The form of the function $`\zeta `$ is usually very complicated and also takes into account exogenous factors (for example the market maker wants to adjust the price so as to eliminate eventual profit opportunities). For sake of simplicity we set the new price proportional to the square root of total supply and demand (as in )

$$\mathrm{\Delta }_t=p_{t+1}p_t\mathrm{sign}(D_t)\sqrt{|D_t|}$$
(1)
On the other side, to model the fundamentalist behaviour, we need to define the perceived value $`f_t`$ of the asset. This include an exogenous source of information hitting the market, thus $`f_t`$ can be arbitrarily modeled as an exogenous stochastic process () with the relative changes drawn from a Gaussian with zero mean and standard deviation $`\sigma _ϵ`$: $`\mathrm{log}(f_{t+1})\mathrm{log}(f_t)=ϵ_t`$ where $`ϵ_t𝒩(0,\sigma _ϵ^2)`$. Note that the fundamental value $`f_t`$ is perceived at the same time and in the same way by all the fundamentalist traders. In  also the case in which there are diverse perceived values is studied.
At each time step both $`p_t`$ and $`f_t`$ are updated as specified above. In particular $`p_t`$ is updated with eq(1) where the strategy $`x_t^{(i)}`$ for each agent $`i`$ is determined by the trading rule described in the next section. The time corresponding to a single iteration should be thought as the time scale on which the fastest traders observe and react to price, e.g., a minute to a day. In section 3 we will determine approximatively the time scale of the model just looking at the outcome of a simulation.

### 2.1 Trading strategy

This section describes the logic which rules the trading activity. At each time step each agent decides, independently from the others, if to buy, to sell or not to trade. The probability to stay inactive is $`1\alpha `$ where $`\alpha `$ is the activity parameter as in . In the case they choose to trade, a different decision path is followed by the two types of traders.

#### Fundamentalist strategy

Fundamentalists tend to follow the “right” price $`f_t`$. At each time step the decision to buy or sell proceeds as follows: (a) If they own stocks then they check if it is appropriate to sell: if $`p_t>f_t`$ then they sell, otherwise they buy another stock. If they cannot buy because no money is left, then they stay inactive. (b) In the case they do not own any stock, they check if it is appropriate to buy, that is, if $`p_t<f_t`$. If $`p_t<f_t`$ and if they have enough money, they buy, otherwise they stay inactive.

Note that this is similar to the “order-based value strategy” in  that buys *until prices match values*. That strategy is consider unrealistic because it is not bounded by any risk constraint. In the present rule, instead, the upper/lower bound is given respectively by the limited amount of capital of the agents and by the number of stocks they own.

#### Chartist strategy

Chartists follow the market price $`p_t`$. They are not influenced by any external source of information. At each time step they decide as follows: (a) If they own stocks, then they ask if it is appropriate to sell, that is, if the average price they paid for all the stocks they have bought up to then is lower than $`p_t`$. For example if one has invested $`p_t^{}+p_{t^{\prime \prime }}`$ (with $`t^{},t^{\prime \prime }<t`$) in two stocks and if $`p_t>(p_t^{}+p_{t^{\prime \prime }})/2`$ then selling one of those stock will be a profit opportunity. If this does not hold and (s)he has money, (s)he will buy another stock.

(b) In the case they do not own stocks, they simply flip a coin to decide whether to buy or to do nothing.

Case (b) gives a larger degree of randomness to the behaviour of the chartists.

### 2.2 Collective formation and diffusion

At this stage of formulation the agents follow independent strategies. Thus, the excess demand $`D_t`$ is the sum of independent identically distributed random variables and for the central limit theorem determines a Gaussian distribution of the histogram of log-return which is different from what is observed in the real markets .

To obtain a deviation from normality we need to take into account *herding* behaviour that has already been demonstrated to determine (at least in part) the fat tail property of the distribution of returns .
Instead of determining a priori the clusters distribution as in percolation models we just allow the agents to diffuse on the grid and to aggregate inside each single lattice site (in  self-organized percolation is used to have percolating clusters without setting the system to the critical point).

To give spatial mobility to the agents we model the market as a *lattice gas*. Agents are placed randomly on a regular hexagonal (honeycomb) two-dimensional lattice $`L\times L`$ (six links at $`60^{}`$) with toroidal boundary conditions. Each site of the lattice may potentially contain all the agents. At each time step, agents diffuse uniformly to a neighboring site. The diffusion determines a re-shuffling of agents inside each single lattice site and changes the impact on the price fluctuations.

Now, the decision of each agent to buy, sell or stay inactive is determined in two phases: first, each agent makes his choice according to his actual situation and potential benefit from the activity as specified by the trading strategy in section 2.1, then, in the second phase, the single agent’s strategy is aggregated to a simple collective strategy. In this last phase the agent’s decisions $`x_t^{(i)}`$ are weighted by the *influence strength* $`s^{(i)}`$ in a kind of proportional vote described below.
In the spirit of Nowak et al.  (see also ) the decision of each agent affects and gets affected by other agents on the basis of its influence strength. The influence strength of agent $`i`$ is represented as a real number $`s^{(i)}`$. If we assign a much larger influence to some traders among the totality (call them *leaders*), the dynamics of the model will be dependent on how many leaders are present. Leaders are chosen uniformly among the two classes of traders, chartists and fundamentalists. We represent a group of traders by those agents contained in same lattice site. So, each group of traders forms a collective system. We also want a group to be dominated by a *leader* so that we can set the number of leaders equal to $`L^2`$ given that $`NL^2`$ where $`N`$ indicates the total number of agents.

The influence among agents found in the same lattice site works as follows: each agent $`i`$ imposes his/her strategy according to the influence strength $`s^{(i)}`$. For each $`x_t^{(i)}\{1,0,+1\}`$ determined by the trading strategy discussed above, we sum the influence strength of each agent that is following strategy $`x`$ and we normalize it to the total so to get values between zero and one to be interpreted as probabilities ($`_xpr[x]=1`$):

$$pr[x]=\underset{i:x^{(i)}=x}{}s^{(i)}/\underset{i}{}s^{(i)}$$
(2)
where the index $`i`$ runs over all agents contained in that lattice site. Then we update agents’ strategy $`x^{(i)}`$ using a *random wheel* with probability $`pr[1]`$, $`pr[0]`$ and $`pr[+1]`$ given by eq(2).

A collective system arises from the coherent behaviour of a group of strongly interacting constituents. It also has a weak external coupling. In our case, the collective can be treated as an individual whose strategy has a distribution of buy/sell/inactive which is determined by the single agent’s actual strategy $`x^{(i)}`$ through eq(2). This means that if exactly one agent is a leader and he has chosen strategy $`\widehat{x}`$ then $`pr[\widehat{x}]pr[x]`$ for the other choices $`x`$. Thus, the fraction of agents in that collective that will follow strategy $`\widehat{x}`$ is large. If more than one leader, say two, is present in the same site and their decision is different, then they will compete to determine the majority strategy. On average half of the traders will follow one leader and the other half will follow the other. And so on for the other possibilities. In general, if we set more than one single leader in each site (on average), their competition will destroy the effects of the herding behaviour. This determines, as confirmed by numerical simulations, a Gaussian distribution of returns.
In conclusion we decide to set on average a single leader (or less) in each lattice site.

It is worth to note that even in this case the dynamics of each collective group is equivalent to that of a single agent (the leader) with combined capital. Following this reasoning one would expect a distribution of return with no fat tails at all. In fact the effect of the collective strategies of the leaders with combined capital would end up to zero when summed over the whole grid just because the uniformity of the collectives’ dimension which is about $`(N_C+N_F)/L^2`$ on average. The results show a clear deviation from a Gaussian instead. Why this happens? The answer is found considering the synergy between the trading rule of section 2.1 and the collective formation mechanism described in 2.2; the collective groups influenced by a fundamentalist leader are coupled (weakly, but they do) by means of the fundamental price that is perceived by all of them equally. So, while the *chartists’ collectives*, being totally uncoordinated, only produce noise, it happens that fundamentalists’ leaders occasionally end up with the same decision to buy or sell, driving a large fraction of all the traders to follow the same decision.

The re-shuffling given by the diffusion of agents can also be interpreted as a change of preference, in the same way people decide to trust to another brokerage agency or bank. Moreover, not all lattice sites will contain a leader. In these “leader free” sites no collective if formed and the behaviour of the agents is totally independent. Another remarkable mechanism given by the diffusion is that one agent that leaves a group whose leadership is fundamentalist for a group whose leadership is chartist will end up in a *behaviour’s change* much like the fundamentalist-noisy switch in .

## 3 Discussion

When the number of fundamentalists is higher than that of chartists, the price $`p_t`$ tracks closely the perceived value $`f_t`$. This is both trivial and unrealistic. In fact, evidence from real market data suggests that, while prices track values over the very long term, large deviations are the rule rather than the exception . The opposite situation results in too random fluctuations given the random behaviour of the chartists with the price that does not follows the value.

So, a non trivial dynamics is obtained for $`N_FN_C`$. In this case we observe periods in which the price follows the fundamental price followed by periods of apparently independent fluctuations. For this purpose we set $`N_F=\widehat{N}L^2`$ and $`N_C=\widehat{N}L^2`$ for a certain $`\widehat{N}`$. The value of this parameter is found observing that the collective dynamics depends on its dimension. If the collective systems are too small we do not get any herding behaviour.

To avoid too large fluctuations of the price around the fundamental price, we can also get rid of another parameter and set the activity $`\alpha =10/(N_F+N_C)`$.

Figure 1 refers to a simulation with $`L=10`$ and $`\widehat{N}=25`$ running for $`10^6`$ time steps. The influence strength of the leader is set to 100 while the remaining agents have influence strength one. The diffusion speed is set to $`10^1`$. As in  half of the agents start with one stock while the remaining with no stocks. In this way we obtain a balance between an initial number of people willing to sell and people willing to buy that would produce an artificial initial bubble or valley whose amplitude depends on the number of market participants. Besides it is worth to note that the initial amount of capital each agent is equipped with, induces the ability of the market price $`p_t`$ to follow the fundamental value $`f_t`$ when this strongly deviates from the initial value $`f_0`$. To see this fact just consider the case in which the agents own little initial capital, then $`p_t`$ is limited by the global capacity of the agents to buy.

On the other hand, the price $`p_t`$ is limited from below by the amount of initial stocks we equip the agents with; the greater it is, the larger will be a potential fall of the price $`p_t`$ to follow the fundamental value $`f_t`$. These and other related questions will be investigated elsewhere.

Another consequence coming from the constraint given by the availability of funds/stocks is that, given the trading rule described above, the activity of the agents is not uniform. In fact, agents may end up with the decision to stay inactive either if they want to sell but they do not own stocks or they want to buy but they do not have money.

Figure 1 shows the price $`p_t`$ to follow the fundamental price $`f_t`$ apart of some large occasional deviations. The standard deviation of the price is $`\sigma _p=46`$ while $`\sigma _f=44.94`$ giving an *excess volatility* of 2.3%.
In the small chart at the bottom of the same figure we show the traded volume $`V_t`$ computed each time step (in contrast to reality where it is computed every certain period of time, e.g., day or week but not instantaneously). Because in this model we do not require to match the sell/buy orders, we compute the volume as $`V_t=_i|x_t^{(i)}|`$. In fact the model does not require that each buy order should match a sell order because the balance is assured to be made involving a market maker outside the model itself. The figure shows an increase in volume when $`p_tf_t`$ because, according to the trading rule, fundamentalists trade much more in proximity of the fundamental value. This is opposed to periods in which they either (a) sell all stocks they own because the price is higher than the perceived value and wait to buy a new stock when the price is lower than its expected value or (b) they have already invested all the capital and cannot buy other stocks even if appropriate (see also plots of wealth 2).

Figure 2 bottom panel shows the average wealth per agent computed as the sum of both liquidity and stocks for the actual nominal price of all agents. The upper plot shows the average profit per capita and the middle plot the average number of stocks per capita. It seems that a kind of synchronization exist between chartists and fundamentalist: when one buys the other sells. This is given by the balance of the fundamentalists to the escaping force of the chartists. In fact fundamentalists trade to put the market on track again. In this view the chartists globally exercise a great indirect influence on the fundamentalists actions. The same phenomena are observed in LLS’s model  taking into account fundamentalists and trend followers (they call them *extrapolating investors*).

To better investigate the final distribution of capital we run a large simulation involving two million agents and running for 15000 time steps.

In figure 3 is shown the histogram of agent’s wealth-change distribution. It shows a power law in the central part with slope -1.3 and wide tails. So the central part of the distribution is consistent with a Pareto-like distribution . It is noticeable the fact that the initial uniform distribution (all agents start with same capital) is strongly reshaped over a sufficiently long run (indeed over shorter run the final distribution of wealth is Gaussian-like, not shown).

This qualitative picture of the model dynamics must be enhanced by a more quantitative assessment that the model reproduces the features of market price time series.

Plot 4 shows the histogram of log-return $`r_t=\mathrm{log}p_t\mathrm{log}p_{t1}`$ for the same simulation of figure 1 and 2. The excess kurtosis of the distribution is 4.58. Moreover, the histogram has fat tails and power law decay $`x^\mu `$ in the central part leading to exponent $`\mu 2.8`$ (see inset plot) roughly consistent with empirical studies .

Figure 5 show the comparison of the return of the market price $`p_t`$ and those of the fundamental price $`f_t`$. The deviation is clear; the exogenous source of information is transformed into something else by the endogenous dynamics of the market participant as already demonstrated in .

Another relevant property of market price dynamics is the absence of correlation of return and the persistence of long range correlation of volatility . Volatility of stock price changes is a measure of how much the market is liable to fluctuate and can be defined in different ways. In the following we define the volatility as the square of return $`v_t=r_t^2`$.

Figure 6 shows the autocorrelation function of volatility defined as $`c(\tau )=[<v_tv_{t+\tau }><v_t>^2]/[<v_t^2><v_t>^2]`$ . Empirical studies show that the autocorrelation of volatility in real data follows a power law decay with exponent between 0.1 and 0.3 . Instead we found a slope $`.013`$ that is one order of magnitude less.

Other empirical studies of large data bases  show that the cumulative distribution of the volatility is consistent with a power-law asymptotic behaviour characterized by an exponent $`3`$. Figure 7 shows the histogram of volatility computed for both fundamental $`f_t`$ and actual price $`p_t`$. In particular a regression in log-log shows an exponent of -1.67 of the histogram of $`r_t^2`$.

In summary, the model is not yet able to perfectly match some empirical findings and more work is required.

To obtain a rough estimation of the time scale of the simulated market we filtered out the time series of return $`r_t`$ from the complete series at intervals of increasing size $`\mathrm{\Delta }t`$. In figure 8 we show the histogram of the filtered series for different time lags (this is a slightly simpler procedure than the time-aggregation used in ). A crossover to a Gaussian is observed for $`\mathrm{\Delta }t60`$ suggesting that the time scale of the simulation shown in all figures but fig. 3 is of the order of half day per time step. Indeed, empirical observations tell that a crossover to a Gaussian is found on time scales approximatively of one month .

There is no doubt that a more rigorous argument would be given estimating the excess kurtosis of the filtered series and determining the crossover when the filtered series with a certain $`\mathrm{\Delta }t`$ have excess kurtosis about zero. Unfortunately this would require a huge amount of data points because the kurtosis depends on the estimation of the fourth moment.

## 4 Conclusions and future developments

We have described a new model to reproduce the price fluctuations of a single stock in an artificial stock exchange whose traders are modeled as chartists and fundamentalists. Some of them have more influence than others and represent a brokerage agency where people go to ask for advice. They group together inside each lattice site to form a collective system and to follow a common strategy according to proportional voting. Traders are free to diffuse on a two-dimensional lattice to model the tendency to change opinion and to follow a different advisor.

The model is consistent with fat tails of histogram of returns and correlation of volatility. Nevertheless much work still has to be done to better reproduce other empirical observed facts as the volatility and wealth distribution.
The structure of the model is versatile enough to allow future expansion some of which are discussed below. We believe that a more realistic description of the agents behaviour and trading may allow to get further insight in the dynamics of price change as well as in the distribution of wealth among traders.

It has been made clear that the availability of capital strongly influences the dynamics of the model. Thus, a non uniform initial wealth distribution (some agents represent capitalists or large investors like banks who manage large capitals), may determine the power law of wealth distribution. Besides, agents should be able to buy/sell more than just one stock at a time according to, for example, the availability of capital and difference between perceived value and actual price.
Besides it is worth (and the model will easily allow it) to develop more realistic trading strategies like trend-following  and/or divide the action among different choices (more stocks and/or bonds with fixed income as in ).

#### Acknowledgments:

I would like to thank M. Bernaschi, R. Pandey and D. Stauffer for helpful suggestions and constructive critics. Fruitful discussions with Z.-F. Huang are also acknowledged.


format: text

text:
# References

Density Functional Theory of Spin-Polarized Disordered Quantum Dots

Kenji Hirose1, Fei Zhou2, and Ned S. Wingreen3

1 Fundamental Research Laboratories, NEC Corporation, 34 Miyukigaoka, Tsukuba, Ibaraki 305-8501, Japan

2 Physics Department, Princeton University, Princeton, New Jersey 08544

3 NEC Research Institute, 4 Independence Way, Princeton, New Jersey 08540

Abstract

Using density functional theory, we investigate fluctuations of the ground-state energy of spin-polarized, disordered quantum dots in the metallic regime. To compare to experiment, we evaluate the distribution of addition energies and find a convolution of the Wigner-Dyson distribution, expected for noninteracting electrons, with a narrower Gaussian distribution due to interactions. The third moment of the total distribution is independent of interactions, and so is predicted to decrease by a factor of $`(25\pi /8)/(26/\pi )0.405`$ upon application of a magnetic field, which transforms from the Gaussian orthogonal to the Gaussian unitary ensemble.

PACS numbers: 73.61.-r, 73.23.Hk, 71.15.Mb

The interplay of disorder and electron-electron interactions in quantum dots has recently attracted much attention. Experiments using quantum dots – small islands fabricated in a two-dimensional electron gas  – measure the spacings between conductance peaks in the Coulomb blockade region. Since the peak spacings reflect differences between ground-state energies for different numbers of electrons one cannot apply random matrix theory  to evaluate the spectrum of peak-spacing fluctuations. Indeed, experiments find a more symmetric distribution than the Wigner-Dyson form. Experiments disagree, however, on the magnitude of the fluctuations . Sivan et al. , observed fluctuations several times as large as the inferred mean level spacing $`\mathrm{\Delta }_0`$, and concluded that the fluctuations are a fixed percentage $`1015\%`$ of the total charging energy $`e^2/C`$, where $`C`$ is the dot capacitance. Similar results have recently been obtained by Simmel et al.  in small Si dots. In contrast, Patel et al.  found fluctuations in GaAs dots comparable to the mean level spacing.

Theoretical treatments also disagree regarding the magnitude of the peak-spacing fluctuations. Sivan et al.  found large fluctuations scaling as $`(0.100.17)e^2/C`$ for a small lattice model. Similar results were found by Koulakov et al. for the classical, strong interaction regime $`r_s1`$  where electrons form a Wigner lattice . Blanter et al.  used the random phase approximation (RPA)  for weakly interacting dots and concluded that, for dimensionless conductance $`g1`$ , the contribution to fluctuations from interactions should be parametrically smaller than the mean level spacing $`\mathrm{\Delta }_0`$. While the above results can be reconciled as applying to different regimes of $`r_s`$ and $`g`$, recent work employing the self-consistent Hartree-Fock equations  found peak-spacing fluctuations several times as large as $`\mathrm{\Delta }_0`$ even for $`r_s1`$ and $`g1`$ where RPA should still provide a good approximation .

The purpose of the present article is to clarify the origin, magnitude, and distribution of peak-spacing fluctuations in spin-polarized disordered quantum dots in the regime $`g\stackrel{>}{}1`$ and $`r_s1`$. Density functional theory (DFT) provides us with accurate ground-state energies including electron-electron interaction, confinement, and disorder for realistic quantum dots. We find that the distribution of peak spacings is the convolution of a Wigner-Dyson distribution, expected for noninteracting electrons, with a narrower Gaussian distribution due to interactions. The width of the Gaussian is accurately given by the fluctuations in the screened Coulomb interaction between a pair of electrons at the Fermi energy – a result which will also apply to unpolarized quantum dots. The total peak spacing fluctuations are hence smaller than the mean level spacing $`\mathrm{\Delta }_0`$. Use of an unscreened interaction between electrons, either direct or exchange, is found to greatly overestimate the magnitude of the fluctuations. Furthermore, since interactions add a symmetric contribution to the distribution of peak-spacing fluctuations, the third moment of the total distribution is independent of interactions. Hence, we predict that experimental application of a magnetic field will reduce the third moment by a universal factor of 0.405, corresponding to a change from the Gaussian orthogonal ensemble to the Gaussian unitary ensemble.

The ground-state energies of spin-polarized, disordered quantum dots are obtained within density functional theory with the exchange-correlation part of the electron-electron interactions treated in the local-density approximation. Specifically, we solve the following Kohn-Sham equations  numerically, and iterate until self-consistent solutions are obtained ;

$$\left[\frac{\mathrm{}^2}{2m^{}}^2+\frac{e^2}{\kappa }\frac{\rho (𝐫^{})}{|𝐫𝐫^{}|}𝑑𝐫^{}+\frac{\delta E_{\mathrm{xc}}[\rho ,\zeta ]}{\delta \rho (𝐫)}+V_{\mathrm{ext}}(𝐫)\right]\mathrm{\Psi }_i(𝐫)=ϵ_i\mathrm{\Psi }_i(𝐫),$$
(1)
where the density is

$$\rho (𝐫)=\underset{i}{\overset{N}{}}|\mathrm{\Psi }_i(𝐫)|^2.$$
(2)
Here $`E_{\mathrm{xc}}[\rho ,\zeta ]`$ is the exchange-correlation energy functional  with local spin polarization $`\zeta (𝐫)=1`$. The summation in the density (2) is taken over the $`N`$ lowest energy Kohn-Sham orbitals. In previous work , we have shown that the DFT method gives very accurate ground state energies for clean parabolic GaAs quantum dots, in agreement with exact calculations for up to five electrons . Comparison with quantum Monte Carlo calculations  confirms that DFT is valid for interaction strengths up to $`(e^2/\kappa \mathrm{}_0)/\mathrm{}\omega _0=6(r_s8)`$ and up to $`N=8`$ electrons.

The external potential for our disordered dots is the sum of a confining parabola and multiple “impurity” potentials each with a Gaussian profile:

$$V_{\mathrm{ext}}(𝐫)=\frac{1}{2}m^{}\omega _0^2r^2+\frac{1}{2\pi \lambda ^2}\underset{i}{\overset{N_{\mathrm{imp}}}{}}\gamma _i\mathrm{exp}\left(\frac{|𝐫𝐫_i|^2}{2\lambda ^2}\right).$$
(3)
The impurity potentials are randomly distributed with density $`n_{\mathrm{imp}}=1.03\times 10^3\mathrm{nm}^2`$ and strength $`\gamma _i`$ uniformly distributed on $`[W/2,W/2]`$ with $`W=10\mathrm{}^2/m^{}`$. The width of each impurity is taken as $`\lambda =\mathrm{}_0/(2\sqrt{2})`$, where $`\mathrm{}_0=\sqrt{\mathrm{}/m^{}\omega _0}19.5\mathrm{nm}`$. Here we use the effective mass for GaAs, $`m^{}=0.067m`$, and $`\mathrm{}\omega _0=3.0\mathrm{meV}`$. The strength of the Coulomb interaction is controlled by changing the dielectric constant $`\kappa `$, where $`\kappa =12.9`$ for GaAs. The resulting dimensionless interaction strength is measured by $`(e^2/\kappa \mathrm{}_0)/\mathrm{}\omega _0`$ or $`r_s(=1/\sqrt{\pi \rho _0}a_B^{})`$ where $`a_B^{}=\mathrm{}^2\kappa /m^{}e^2`$ is the effective Bohr radius, and $`\rho _0`$ is the electron density at the center of the dot. From a scattering phase-shift analysis we find the mean free path of electrons $`l=v_F\tau 170\mathrm{n}\mathrm{m}`$ to be slightly larger than the dot diameter $`L=120160\mathrm{n}\mathrm{m}`$, where the dot diameter increases with $`r_s`$. Therefore the dots are marginally in the ballistic regime and have a dimensionless conductance $`g=24`$ .

At low temperatures, electron hopping into a dot containing $`N1`$ electrons is suppressed except when the ground-state free energy $`E(N1)(N1)\mu `$ is equal to the ground state free energy for $`N`$ electrons $`E(N)N\mu `$. This degeneracy condition determines the position of the $`N`$th conductance peak as a function of the electron chemical potential $`\mu _N=E(N)E(N1)`$, or equivalently, as a function of an applied gate voltage . The increase in $`\mu `$ needed to put an extra electron in the dot, which we will refer to as the addition energy $`\mathrm{\Delta }`$, is given by $`\mathrm{\Delta }=E(N+1)2E(N)+E(N1)`$. From our solution of the Kohn-Sham equations, the ground-state energy of a dot with $`N`$ electrons is obtained from

$$E(N)=\underset{i}{}ϵ_i\frac{e^2}{2\kappa }\frac{\rho (𝐫)\rho (𝐫^{})}{|𝐫𝐫^{}|}𝑑𝐫𝑑𝐫^{}\rho (𝐫)\frac{\delta E_{\mathrm{xc}}[\rho ,\zeta ]}{\delta \rho (𝐫)}𝑑𝐫+E_{\mathrm{xc}}.$$
(4)
We consider fluctuations of the addition energy for $`N=10`$ electrons. Thus for each realization of disorder we calculate $`\mathrm{\Delta }E(11)2E(10)+E(9)`$. The disorder average is taken over more than 1,000 different impurity configurations. As a check of accuracy, we have confirmed that the ground-state energies obtained from DFT for disordered quantum dots with $`N=2`$ and $`3`$ are in good agreement with exact diagonalization results for $`0r_s5`$.

Figure 1 shows the distribution of addition energies $`\mathrm{\Delta }`$ for interacting dots with $`(e^2/\kappa \mathrm{}_0)/\mathrm{}\omega _0=2.39`$ (right), and the distribution of $`\mathrm{\Delta }_0`$ for noninteracting dots of the same size (left). In the inset, we show the charge density $`\rho (𝐫)`$ for one realization of disorder. The distribution of level spacings $`\mathrm{\Delta }_0`$ in the noninteracting dots has the Wigner-Dyson form, while that in the interacting dots is somewhat more symmetrical. The symmetry continues to increase with increasing interaction strength. While interactions considerably enhance the average addition energy $`\mathrm{\Delta }6.50\mathrm{\Delta }_0`$, the fluctuation in the interacting case $`\delta \mathrm{\Delta }\sqrt{\mathrm{\Delta }^2\mathrm{\Delta }^2}`$ is only $`13\%`$ larger than the noninteracting fluctuation $`\delta \mathrm{\Delta }_0\sqrt{\mathrm{\Delta }_0^2\mathrm{\Delta }_0^2}`$.

Figure 2 shows the average addition energy $`\mathrm{\Delta }`$, its rms fluctuations $`\delta \mathrm{\Delta }`$, and its third moment for disordered dots as a function of the Coulomb interaction strength $`(e^2/\kappa \mathrm{}_0)/\mathrm{}\omega _0`$. For comparison, we have also plotted results for disordered, noninteracting dots of the same size, which we obtain as follows. First we find the effective potential for the clean dot, without impurities. Then we solve for the single-particle level energies $`ϵ_i^0`$ for this effective potential plus the random impurity potentials in (3). The addition energy is simply given by $`\mathrm{\Delta }_0=ϵ_{N+1}^0ϵ_N^0`$ with $`N=10`$. All dot sizes satisfy the relation $`\delta \mathrm{\Delta }_0=\sqrt{4/\pi 1}\mathrm{\Delta }_00.52\mathrm{\Delta }_0`$ predicted by random matrix theory for the Gaussian orthogonal ensemble . In Fig. 2(a), the average addition energy in the noninteracting case is seen to decrease with increasing Coulomb interaction. This is because the increasing Coulomb repulsion among electrons causes the dot to grow and hence the level spacing to shrink. The average addition energy in the interacting case increases considerably with Coulomb interaction strength, as expected from the classical electrostatics relation $`\mathrm{\Delta }{\displaystyle \frac{e^2}{C}}`$ where $`C`$ is the capacitance of the dot. However, Fig. 2(b) shows that the interactions only slightly increase the addition-energy fluctuations. For GaAs, $`r_s2`$, the enhancement is only about 10%, in rough agreement with the experiment of Patel et al. .

To understand the magnitude of addition-energy fluctuations, we use the phenomenological framework presented by Blanter, Mirlin, and Muzykantskii  for the regime $`r_s1`$, where RPA is valid, and show that it applies to the DFT results at least up to $`r_s5`$. Consider first a dot containing $`N1`$ electrons in the ground state. Addition of the $`N`$th electron to form the $`N`$ electron ground state requires an electron chemical potential $`\mu _N`$. To form instead the first excited state of $`N`$ electrons requires the higher chemical potential $`\mu _N+\mathrm{\Delta }ϵ`$. For an ensemble of disordered metallic dots, $`\mathrm{\Delta }ϵ`$ will have Wigner-Dyson statistics, with $`\mathrm{\Delta }ϵ`$ equal to the mean noninteracting level spacing $`\mathrm{\Delta }_0`$, since the lowest excitation of a Fermi liquid is a single electron promoted across the Fermi surface.

The addition energy $`\mathrm{\Delta }`$ is the increase in chemical potential from $`\mu _N`$ required to add one more electron to the dot and thus form the $`N+1`$ electron ground state. This $`(N+1)`$st electron must have an extra energy $`\mathrm{\Delta }ϵ`$ to occupy the lowest empty level plus an extra energy $`U_{N,N+1}`$ due to its Coulomb interaction with the $`N`$th electron. The total addition energy $`\mathrm{\Delta }`$ will be approximately given by the sum of these two contributions,

$$\mathrm{\Delta }\mathrm{\Delta }ϵ+U_{N,N+1}.$$
(5)
The distribution of $`\mathrm{\Delta }ϵ`$ is given by the Wigner-Dyson distribution of level spacings for a noninteracting dot of the same size. The average interaction energy $`U_{N,N+1}`$ is the capacitive charging energy $`e^2/C`$. We estimate the fluctuations in $`U_{N,N+1}`$ by calculating the screened Coulomb interaction between two electrons at the Fermi surface . Specifically, we treat the screening effect in the Thomas-Fermi approximation as

$$U_{N,N+1}^{TF}=e\phi _N(𝐫)\rho _{N+1}^0(𝐫)𝑑𝐫.$$
(6)
The screened potential due to the $`N`$th electron in Fourier representation is

$$\phi _N(𝐪)=\frac{2\pi e}{\kappa }\frac{\rho _N^0(𝐪)}{|𝐪|+q_0},$$
(7)
where $`\rho _N^0(𝐫)=|\varphi _N^0(𝐫)|^2`$ is the density of the $`N`$th single-particle wavefunction $`\varphi _N^0(𝐫)`$ of a noninteracting disordered dot. The Thomas-Fermi wavevector is $`q_0=(2\pi e^2/\kappa )(dn/d\mu )=1/a_B^{}`$. It is found that the fluctuation $`\delta U^{TF}=\sqrt{(U_{N,N+1}^{TF})^2U_{N,N+1}^{TF}^2}`$ is always considerably smaller than the noninteracting level-spacing fluctuation $`\delta \mathrm{\Delta }_0`$ up to at least $`r_s5`$. The total fluctuation estimated as $`\delta \mathrm{\Delta }^{TF}=\sqrt{(\delta \mathrm{\Delta }_0)^2+(\delta U^{TF})^2}`$ is shown in Fig. 2(b) by crosses. We see that the fluctuations in the Thomas-Fermi screening model agree well with the DFT results with no free parameters. This supports the picture  that the addition-energy fluctuation arises from two quasi-particles above a filled Fermi sea interacting via a screened Coulomb potential.

Within this picture, the increase of the fluctuation of $`U_{N,N+1}`$ with increasing interaction strength leads naturally to greater symmetry of the distribution of addition energies. Numerically, we find that that the distribution of $`U_{N,N+1}^{TF}`$ has a symmetric Gaussian form. Hence, in agreement with Eq. (5), we observe that the addition-energy distribution function $`P(\mathrm{\Delta })`$ is always extremely well described by the convolution of a Wigner-Dyson distribution for level spacings $`\mathrm{\Delta }ϵ`$,

$$P_{\mathrm{WD}}(\mathrm{\Delta }ϵ)=\frac{\pi }{2}\frac{\mathrm{\Delta }ϵ}{\mathrm{\Delta }_0^2}\mathrm{e}^{\frac{\pi }{4}\frac{\mathrm{\Delta }ϵ^2}{\mathrm{\Delta }_0^2}}$$
(8)
with a Gaussian distribution for interaction energies $`U_{N,N+1}`$,

$$P_{\mathrm{Gauss}}(U_{N,N+1})=\frac{1}{\sqrt{2\pi }\delta U}\mathrm{e}^{\frac{(U_{N,N+1}\mathrm{\Delta }+\mathrm{\Delta }_0)^2}{2(\delta U)^2}}.$$
(9)
The result for the distribution of addition energies is

$`P(\mathrm{\Delta })`$ $`=`$ $`{\displaystyle 𝑑\mathrm{\Delta }ϵ𝑑U_{N,N+1}P_{\mathrm{WD}}(\mathrm{\Delta }ϵ)P_{\mathrm{Gauss}}(U_{N,N+1})\delta (\mathrm{\Delta }ϵ+U_{N,N+1}\mathrm{\Delta })}`$ (10)
$`=`$ $`{\displaystyle \frac{1}{2}}\sqrt{{\displaystyle \frac{\pi }{2}}}{\displaystyle \frac{\delta U}{\alpha \mathrm{\Delta }_0^2}}e^{\frac{\pi }{4}\frac{\stackrel{~}{\mathrm{\Delta }}^2}{\alpha \mathrm{\Delta }_0^2}}\left\{e^{\frac{\stackrel{~}{\mathrm{\Delta }}^2}{2\alpha (\delta U)^2}}+\sqrt{{\displaystyle \frac{\pi }{2\alpha }}}{\displaystyle \frac{\stackrel{~}{\mathrm{\Delta }}}{\delta U}}\left[1+\mathrm{erf}({\displaystyle \frac{\stackrel{~}{\mathrm{\Delta }}}{\sqrt{2\alpha }\delta U}})\right]\right\}.`$
Here $`\alpha =\pi \delta U^2/(2\mathrm{\Delta }_0^2)+1`$ and $`\stackrel{~}{\mathrm{\Delta }}=\mathrm{\Delta }\mathrm{\Delta }+\mathrm{\Delta }_0`$, where $`\mathrm{\Delta }`$ is the center of the distribution and $`\delta U`$ is a fitting parameter giving the width of the fluctuations of $`U_{N,N+1}`$. In the noninteracting case, $`\delta U=0`$ so that $`P(\mathrm{\Delta })=P_{\mathrm{WD}}(\mathrm{\Delta })`$ as expected. In the other limit, $`P(\mathrm{\Delta })`$ becomes nearly symmetric for sufficiently large $`\delta U`$. In Fig. 1, we show $`P(\mathrm{\Delta })`$ given by Eq. (10) as a dashed line. It is seen that the DFT distribution is described very well by (10) with the best fit value of $`\delta U=0.13\mathrm{meV}`$ very close to the value $`\delta U_{N,N+1}^{TF}=0.10\mathrm{meV}`$ estimated from the Thomas-Fermi screened Coulomb interaction between two electrons at the Fermi surface.

To test whether the distribution of addition energies is well described by the sum of noninteracting level spacings and a symmetric distribution due to interactions, we propose to compare the third moment of the distribution $`P(\mathrm{\Delta })`$ with and without a magnetic field $`B_{}`$ normal to the plane of the dot. Since the interaction part, coming from the screened Coulomb interaction in our picture, is symmetric it does not contribute to the third moment of $`P(\mathrm{\Delta })`$. Therefore, the ratio $`{\displaystyle \frac{(\mathrm{\Delta }\mathrm{\Delta })^3_{B_{}0}}{(\mathrm{\Delta }\mathrm{\Delta })^3_{B_{}=0}}}`$ should take the value $`(25\pi /8)/(26/\pi )0.405`$ which applies to level spacings taken from a Gaussian orthogonal ensemble ($`B_{}=0`$) and a Gaussian unitary ensemble ($`B_{}0`$) . Since our results apply only to the case of spin-polarized electrons, it is necessary to apply a large magnetic field in the plane of the dots, or to spin polarize the nuclei . The result can also be tested numerically, e.g. by exact diagonalization studies as in Ref. .

Existing diagonalization studies for spin polarized electrons on small lattices find addition-energy fluctuations $`\delta \mathrm{\Delta }0.15e^2/C`$ . For comparison, the Coulomb contribution to the fluctuations found by DFT are much smaller $`\delta \mathrm{\Delta }0.03e^2/C`$ at $`r_s2`$. This difference may be attributed to differences in the strength of disorder: while the dimensionless conductance in our dots is $`g=24`$, we estimate $`g=0.10.3`$ in Ref. . Various theoretical estimates give fluctuations $`\delta \mathrm{\Delta }\mathrm{\Delta }_0/g`$ or $`\delta \mathrm{\Delta }\mathrm{\Delta }_0/\sqrt{g}`$ . In either case, the discrepancy between exact diagonalization and DFT can be attributed to the order of magnitude difference in the dimensionless conductance $`g`$ in the samples studied. The experiments on GaAs  have $`r_s1`$ and $`g>1`$, and thus fall more closely in the range of interaction strengths and dimensionless conductance treated in this paper.

Recently, several calculations  based on the self-consistent Hartree-Fock (SCHF) equations have found large fluctuations, up to $`\delta \mathrm{\Delta }0.2e^2/C`$, in the same range of $`r_s`$ we consider. In one case , the dimensionless conductance is estimated to be $`g1`$, a regime where DFT predicts fluctuations an order of magnitude smaller. As pointed out by Walker, Montambaux, and Gefen , the exchange interaction in the SCHF equations is unscreened. To test whether the lack of exchange screening in the SCHF approach could be responsible for the discrepancy with DFT, we have calculated the unscreened exchange interaction between two electrons near the Fermi surface in our dots

$$U_{N,N+1}^{\mathrm{exch}}=\frac{e^2}{\kappa }\frac{\varphi _N^0(𝐫)\varphi _N^0(𝐫^{})\varphi _{N+1}^0(𝐫^{})\varphi _{N+1}^0(𝐫)}{|𝐫𝐫^{}|}𝑑𝐫𝑑𝐫^{}.$$
(11)
In Fig. 2(b), we have plotted as open circles the fluctuations taken by summing the unscreened exchange interaction (11) with the noninteracting level spacing . It is clear that for $`r_s>1`$, the unscreened exchange interaction noticeably overestimates the addition-energy fluctuations. In contrast, density functional theory correctly accounts for screening within the electron gas, including exchange interactions . These results suggest that the unscreened exchange interaction in the SCHF approach may generally lead to an overestimate of the addition-energy fluctuations.

In this work, we have neglected external screening by gates or electrodes. This simplification should be valid as long as the distance to external conductors is larger than the diameter of the dot. In the opposite limit, it is essential to consider external screening, but this may be done by a simple modification of the $`1/r`$ potential between electrons.

In conclusion, we have studied the electronic states of spin-polarized, disordered quantum dots using density functional theory and investigated the fluctuation of the ground-state energies. We have found that electron-electron interactions increase the fluctuation of addition energies by no more than $`25\%`$, up to $`r_s5`$, even though the average addition energy is increased by a factor of 10. The addition energy is well approximated as the sum of the noninteracting level spacing and the screened Coulomb interaction between two electrons at the Fermi surface. Hence the distribution of addition energies is the convolution of a Wigner-Dyson distribution of level spacings with a Gaussian distribution of interaction energies. Since the latter is symmetric, it does not contribute to the third moment of the addition-energy distribution. The third moment is therefore predicted to decrease by a universal factor of 0.405 on application of a magnetic field which transforms the dot from the Gaussian orthogonal to the Gaussian unitary ensemble. For quantum dots having larger numbers of electrons, whether spin-polarized or not, we anticipate that the decrease of the screened Coulomb interaction-energy fluctuations occurs as fast as the decrease of the level spacing and thus the present results are also applicable.

We acknowledge I. L. Aleiner, B. L. Altshuler, R. Berkovits, C. M. Marcus, and M. Stopa for useful comments and suggestions.

Figure Captions

* Distribution of addition energies $`\mathrm{\Delta }`$ to add the 11th electron for interacting dots with $`(e^2/\kappa \mathrm{}_0)/\mathrm{}\omega _0=2.39`$ (right) and $`\mathrm{\Delta }_0`$ for noninteracting dots of the same size (left). The energy binwidth is 0.05 \[meV\]. The dashed lines show the distribution function obtained from Eq. (10). Inset: The charge density profile $`\rho (𝐫)`$ for $`N=10`$ electrons with one configuration of impurities.
* (a) Average addition energy $`\mathrm{\Delta }`$, (b) fluctuation $`\delta \mathrm{\Delta }`$, and (c) cube-rooted third moment $`\sqrt[3]{(\mathrm{\Delta }\mathrm{\Delta })^3}`$, as a function of electron-electron interaction strength $`(e^2/\kappa \mathrm{}_0)/\mathrm{}\omega _0`$. The measure of interaction strength $`r_s(=1/\sqrt{\pi \rho _0}a_B^{})`$ indicated by arrows in (a) can be applied to the data in all panels. For each data point, the disorder average is taken over more than 1,000 different impurity configurations. At each $`r_s`$, the noninteracting data are taken for dots of the same size as the interacting dots, and the relation $`\delta \mathrm{\Delta }_00.52\mathrm{\Delta }_0`$ expected for noninteracting level-spacing statistics is always satisfied. Also plotted in (b) are the fluctuations due to noninteracting level spacings plus the screened Coulomb interaction between two electrons at the Fermi surface (crosses), or the unscreened exchange interaction between the two electrons (open circles).


text:
# Distorted English Alphabet Identification: An application of Difference Boosting Algorithm.

## 1 Introduction

Learning is a process that involves identification and distinction of objects. A child learns by examples. In the early days of learning, a child identifies the proximity of his mother by smell or sound or body temperature. Thus it is often not easy for him to distinguish between his mother, grandmother or mother’s sister in the first few months of his learning process. But as he grows and his brain develops, he starts identifying the differences in each of his observations. He learns to differentiate colours, between flowers and leaves, between friends and enemies. This is reflected in his responses too. From the binary expressions of smiling and weeping, different expressions appear in his reactions. He learns to read the expressions on the faces of others and also develops the skill to manage it. Difference boosting is an attempt to implement these concepts of child learning into machine code. In the first round it picks up the unique features in each observation using the naive Bayes’ theorem, something that is shown to be very similar to the functions of animal brain in object identification. In the second step it attempts to boost the differences in these features that enables one to differentiate almost similar objects. This is analogous to the contention of the child that something that looks like a human but having a tail is a monkey. The feature ’having a tail’ gets boosted even if all the other features are strikingly similar. Or, this is how the mother is able to effortlessly distinguish her identical twin children or the artist is able to alter the expressions on the face of his portrait with a few strokes of disjoint line segments. Classic examples to these include the lighting effects on the facial expressions of a sculpture. In all these examples, the brain does not appear to keep the details but only those unique differences required to identify the objects.

In complex problems, such as the distorted English alphabet detection example discussed in this paper, the selection of a complete training set is not trivial. We thus device a set of rules to identify the examples from a dataset that form the complete training set for the network. The rules we follow in the said example are:

1. If the network classify an object incorrectly, but with a high probability of around 90% or above, the example could be a new possibility and should be included in the training set.

2. The network is allowed to produce a second guess on the possible class of an object when it fails in the first prediction. If this is a correct guess and if the difference between the degree of confidence between the first and the second guess is greater than 90% or less than 2%, again the example is assumed to be a new possibility or is in the vicinity of boostable examples and is added to the training set.

The underlying logic in these rules are simple. Psychologists point out that the human expert also develops his skill primarily based on past experiences rather than on logical deduction or symbolic reasoning. We also expect a similar situation in the learning process and assume that if an example is incorrectly classified with a confidence higher than 90%, there could be two possible reasons for this. One possibility is that the network is unaware of the existence of that example in the stated class. The other possibility is that the features used are identical to that of an object from another class. In this case, classification of the object into its actual class is difficult without additional information. Assuming that the reason for the misclassification is that such an sample is not known in the training set, we add that sample also to the training set. In the second rule, we take the difference of the confidence levels since we want to identify new examples and to tackle the border problem that makes it difficult for the network to identify the exact class based on the limited information content in the given features. The first condition picks up the new examples while the second condition picks up the border examples. These are the so-called ’difficult problems’ in the learning process.

One word of caution here is that the purpose of these rules are just to pickup a complete set of examples in the training set, which is a pre-requisite of any probability dependent classification problem. Once this dataset is generated, the training process is done on this dataset and the testing is done on the entire dataset and also on the independent test set. A good classification is when the classification accuracy in both these cases are more or less the same.

## 2 Naive Bayesian learning

Each object has some characteristic features that enables the human brain to identify and characterize them. These feature values or attributes might be either associated to the object by a logical AND or a logical OR relation. The total probability of a system with feature values associated by the logical OR relation is the sum of the individual probabilities. Naive Bayesian classifiers handles this situation by assigning probability distribution values for each attribute separately. If on the otherhand, the attributes are associated by a logical AND relation, meaning that each attribute value should be somewhere around a stipulated value simultaneously, then the total probability is given by the product of the individual probabilities of the attribute values.

Now, the naive Bayesian classifier assumes that it is possible to assign some degree of confidence to each attribute value of an example while attempting to classify an object. Assume that the training set is complete with $`K`$ different known discrete classes. Then a statistical analysis should assign a maximal value of the conditional probability $`P(C_kU)`$ for the actual class $`C_k`$ of the example. By Bayes’ rule this probability may be computed as :

$$P(C_kU)=\frac{P(UC_k)P(C_k)}{_KP(UC_k)P(C_k)}$$

$`P(C_k)`$ is also known as the background probability. $`P(UC_k)`$ is given by the product of the probabilities due to individual attributes. That is:

$$P(UC_k)=\underset{m}{}P(U_mC_k)$$

Following the axioms of set theory, one can compute $`P(U_mC_k)`$ as $`P(U_mC_k)`$. This is nothing but the ratio of the total count of the attribute value $`U_m`$ in class $`C_k`$ to the number of examples in the entire training set. Thus naive Bayesian classifiers complete a training cycle much faster than perceptrons or feed-forward neural networks.

## 3 Difference Boosting

Boosting is an iterative process by which the network upweights misclassified examples in a training set until it is correctly classified. The Adaptive Boosting (AdaBoost) algorithm of Freund and Schapire  attempts the same thing. In this paper, we present a rather simple algorithm for boosting. The structure of our network is identical to AdaBoost in that it also modifies a weight function. Instead of computing the error in the classification as the total error produced in the training set, we take each misclassified example and apply a correction to its weight based on its own error. Also, instead of upweighting an example, our network upweights the weight associated to the probability $`P(U_mC_k)`$ of each attribute of the example. Thus the modified weight will affect all the examples that have the same attribute value even if its other attributes are different. During the training cycle, there is a competitive update of attribute weights to reduce the error produced by each example. It is expected that at the end of the training epoch the weights associated to the probability function of each attribute will stabilize to some value that produces the minimum error in the entire training set. Identical feature values compete with each other and the differences get boosted up. Thus the classification becomes more and more dependent on the differences rather than on similarities. This is analogous to the way in which the human brain differentiates between almost similar objects by sight, like for example, rotten tomatoes from a pile of good ones.

Let us consider a misclassified example in which $`P_k`$ represent the computed probability for the actual class $`k`$ and $`P_k^{}`$ that for the wrongly represented class. Our aim is to push the computed probability $`P_k`$ to some value greater than $`P_k^{}`$. In our network, this is done by modifying the weight associated to each $`P(U_mC_k)`$ of the misclassified item by the negative gradient of the error, i.e. $`\mathrm{\Delta }W_m=\alpha \left[1\frac{P_k}{P_k^{}}\right]`$. Here $`\alpha `$ is a constant which determines the rate at which the weight changes. The process is repeated until all items are classified correctly or a predefined number of rounds completes.

## 4 The classifier network.

Assuming that the occurrences of the classes are equally probable, we start with a flat prior distribution of the classes ,i.e. $`P(C_k)=\frac{1}{N}`$. This might appear unrealistic, since this is almost certain to be unequal in most practical cases. The justification is that since $`P(C_K)`$ is also a weighting function, we expect this difference also to be taken care of by the connection weights during the boosting process. The advantage on the otherhand is that it avoids any assumptions on the training set regarding the prior estimation. Now, the network presented in this paper may be divided into three units. The first unit computes the Bayes’ probability for each of the training examples. If there are $`M`$ number of attributes with values ranging from $`m_{min}`$ to $`m_{max}`$ and belonging to one of the $`K`$ discrete classes, we first construct a grid of equal sized bins for each $`k`$ with columns representing the attributes and rows their values. Thus a training example $`S_i`$ belonging to a class $`k`$ and having one of its attributes $`l`$ with a value $`m`$ will fall into the bin $`B_{klm}`$ for which the Euclidean distance between the center of the bin and the attribute value is a minimum. The number of bins in each row should cover the range of the attributes from $`m_{min}`$ to $`m_{max}`$. It is observed that there exist an optimum number of bins that produce the maximum classification efficiency for a given problem. For the time being, it is computed by trial and error. Once this is set, the training process is simply to distribute the examples in the training sets into their respective bins. After this, the number of attributes in each bin $`i`$ for each class $`k`$ is counted and this gives the probability $`P(U_mC_k)`$ of the attribute $`m`$ with value $`U_mi`$ for the given $`C_k=k`$. The basic difference of this new formalism with that of the popular gradient descent backpropagation algorithm and similar Neural Networks is that, here the distance function is the distance between the probabilities, rather than the feature magnitudes. Thus the new formalism can isolate overlapping regions of the feature space more efficiently than standard algorithms.

The naive Bayesian learning fails when the data set represent an XOR like feature. To overcome this, associated to each row of bins of the attribute values we put a tag that holds the minimum and maximum values of the other attributes in the data example. This tag acts as a level threshold window function. In our example, if an attribute value in the example happens to be outside the range specified in the tag, then the computed $`P(U_mC_k)`$ of that attribute is reduced to one-forth of its actual value (gain of 0.25). Applying such a simple window enabled the network to handle the XOR kind of problems efficiently.

The second unit in the network is the gradient descent boosting algorithm. To do this, each of the probability components $`P(U_mC_k)`$ is amplified by a connection weight before computing $`P(UC_k)`$. Initially all the weights are set to unity. For a correctly classified example, $`P(UC_k)`$ will be a maximum for the class specified in the training set. For the misclassified items, we increment its weight by a fraction $`\mathrm{\Delta }W_m`$. The training set is read repeatedly for a few rounds and in each round the connection weights of the misclassified items are incremented by $`\mathrm{\Delta }W_m=\alpha \left[1\frac{P_k}{P_k^{}}\right]`$ as explained in section 3, until the item is classified correctly.

The third unit computes $`P(C_kU)`$ as :

$$P(C_kU)=\frac{_mP(U_mC_k)W_m}{_K_mP(U_mC_k)W_m}$$

If this is a maximum for the class given in the training set, the network is said to have learned correctly. The wrongly classified items are re-submitted to the boosting algorithm in the second unit.

## 5 Results on the letters dataset

The letters dataset consists of 20,000 unique letter images generated randomly distorting pixel images of the 26 uppercase letters from 20 different commercial fonts. Details of these dataset may be found in . The parent font represented a full range of character types including script, italic, serif and Gothic. The features of each of the 20,000 characters were summarized in terms of 16 primitive numerical attributes. The attributes are:

1. The horizontal position, counting pixels from the left edge of the image, of the center of the smallest rectangular box that can be drawn with all "on" pixels inside the box.
2. The vertical position, counting pixels from the bottom, of the box.
3. The width, in pixels, of the box.
4. The height, in pixels, of the box.
5. The total number of "on" pixels in the charecter image.
6. The mean horizontal position of all "on" pixels relative to the center of the box and divided by the width of the box. This feature has a negative value if the image is "left heavy" as would be the case for the letter L.
7. The mean vertical position of all "on" pixels relative to the center of the box and divided by the height of the box.
8. The mean squared value of the horizontal pixel distances as measured in 6 above. This attribute will have a higher value for images whose pixels are more widely separated in the horizontal direction as would be the case for the letters W and M.
9. The mean squared value of the vertical pixel distances as measured in 7 above.
10. The mean product of the horizontal and vertical distances for each "on" pixel as measured in 6 and 7 above. This attribute has a positive value for diagonal lines that run from bottom left to top right and a negative value for diagonal lines from top left to bottom right.
11. The mean value of the squared horizontal distance times the vertical distance for each "on" pixel. This measures the correlation of the horizontal variance with the vertical position.
12. The mean value of the squared vertical distance times the horizontal distance for each "on" pixel. This measures the correlation of the vertical variance with the horizontal position.
13. The mean number of edges (an "on" pixel immediately to the right of either an "off" pixel or the image boundary) encountered when making systematic scans from left to right at all vertical positions within the box. This measure distinguishes between letters like "W" or "M" and letters like "I" or "L".
14. The sum of the vertical positions of edges encountered as measured in 13 above. This feature will give a higher value if there are more edges at the top of the box, as in the letter "Y".
15. The mean number of edges ( an "on" pixel immediately above either an "off" pixel or the image boundary ) encountered when making systematic scans of the image from bottom to top over all horizontal positions within the box.
16. The sum of horizontal positions of edges encountered as measured in 15 above.

Using a Holland-style adaptive classifier and a training set of 16,000 examples, the classifier accuracy reported on this dataset is a little over 80%. The naive Bayesian classifier produces an error rate of 25.26% while when boosted with AdaBoost reduces the error to 24.12%. Using AdaBoost on the C4.5 algorithm could reduce the error to 3.1% on the testset. However the computational power required over 100 machines to generate the tree structure for its effectuation. A fully connected MLP with 16-70-50-26 topology gave an error of 2.0% with AdaBoost and required 20 machines to implement the system.

The proposed algorithm on a single Celeron processor running at 300MHz and Linux 6.0 attained an error rate of 14.2 % on the independent testset of 4000 examples in less than 15 minutes. Applying the rules mentioned in section one resulted in an overall error of 5.9 % on 20,000 examples. With two chances, the error went as low as 1.65 %. The result is promising taking into consideration the low computational power required by the system. Since bare character recognition of this rate can be improved with other techniques such as grammer and cross-word lookup methods, we expect a near 100 % recognition rate on such systems. Further work is to look into this aspect in detail.

## 6 Conclusion

Bayes’ rule on how the degree of belief should change on the basis of evidences is one of the most popular formalism for brain modeling. In most implementations, the degree of belief is computed in terms of the degree of agreement to some known criteria. However, this has the disadvantage that some of the minor differences might be left unnoticed by the classifier. We thus device a classifier that pays more attention to differences rather than similarities in identifying the classes from a dataset. In the training epoch, the network identifies the apparent differences and magnify them to separate out classes. We applied the classifier on many practical problems and found that this makes sense. The application of the method on the letter dataset produced an error as low as 1.65 % when two chances were given to make the prediction. Further study is to look into the application of other language recognition techniques in conjunction with the network.

Acknowledgment

Ninan Sajeeth Philip would like to thank David J Slate (Pattern Recognition Group, Odesta Corporation, Evanston) for sending him the original of their paper and also for the useful comments and discussions.


text:
# Absolutely Abnormal Numbers

## 1. Introduction

A normal number is one whose decimal expansion (or expansion to some base other than 10) contains all possible finite configurations of digits with roughly their expected frequencies. More formally, when $`b2`$ is an integer, let

(1)
$$N(\alpha ;b,a,x)=\mathrm{\#}\{1nx:\text{the }n\text{th digit in the base-}b\text{ expansion of }\alpha \text{ is }a\}$$

denote the counting function of the occurrences of the digit $`a`$ ($`0a<b`$) in the $`b`$-ary expansion of the real number $`\alpha `$, and define the corresponding limiting frequency

(2)
$$\delta (\alpha ;b,a)=\underset{x\mathrm{}}{lim}x^1N(\alpha ;b,a,x),$$

if the limit exists. The number $`\alpha `$ is simply normal to the base $`b`$ if the limit defining $`\delta (\alpha ;b,a)`$ exists and equals $`1/b`$ for each $`0a<b`$. (When $`\alpha `$ is a $`b`$-adic fraction $`a/b^n`$, which has one $`b`$-ary expansion with all but finitely many digits equaling zero and another $`b`$-ary expansion with all but finitely many digits equaling $`b1`$, these limiting frequencies are not uniquely defined; however, such an $`\alpha `$ will not be simply normal to the base $`b`$ in either case.) A number is normal to the base $`b`$ if it is simply normal to each of the bases $`b`$, $`b^2`$, $`b^3`$, …. This is equivalent (see \[6, Chapter 8\]) to demanding that for any finite string $`b_1b_2\mathrm{}b_k`$ of base-$`b`$ digits, the limiting frequency of occurrences of this string in the $`b`$-ary expansion of $`\alpha `$ (defined analogously to equation (2) above) exists and equals $`1/b^k`$.

For instance, it was shown by Champernowne  that the number $`0.12345678910111213\mathrm{}`$ formed by concatenating all of the positive integers together into a single decimal is normal to base 10 (the analogous construction works for any base $`b2`$), and this sort of example has been generalized . It is known that almost all real numbers are normal to any given base $`b`$ (see for instance \[6, Theorem 8.11\]), and consequently almost all real numbers are absolutely normal, i.e., normal to all bases $`b2`$ simultaneously. On the other hand, we have not proven a single naturally occurring real number to be absolutely normal.

Let us call a number abnormal to the base $`b`$ if it is not normal to the base $`b`$, and absolutely abnormal if it is abnormal to all bases $`b2`$ simultaneously. For instance, every rational number $`r`$ is absolutely abnormal: any $`b`$-ary expansion of $`r`$ will eventually repeat, say with period $`k`$, in which case $`r`$ is about as far from being simply normal to the base $`b^k`$ as it can be. Even though the set of absolutely abnormal numbers is the intersection of countably many sets of measure zero, it was pointed out by Maxfield  that the set of numbers normal to a given base $`b`$ is uncountable and dense; later, Schmidt  gave a complicated constructive proof of this fact. In this paper we exhibit a simple construction of a specific irrational (in fact, transcendental) real number that is absolutely abnormal:

Theorem. The number $`\alpha `$ defined in equation (8) below is irrational and absolutely abnormal.

In fact, our construction easily generalizes to produce concretely an uncountable set of absolutely abnormal numbers in any open interval.

It is instructive to consider why constructing an irrational, absolutely abnormal number is even difficult. Since we already know that rational numbers are absolutely abnormal, our first thought might be to choose an irrational number whose $`b`$-ary expansions mimic those of rational numbers for long stretches, i.e., an irrational number with very good rational approximations. Thus a natural class to consider is the Liouville numbers, defined to be those real numbers $`\beta `$ such that for every positive integer $`m`$, there exists a rational number $`\frac{p}{q}`$ (not necessarily in lowest terms) satisfying

(3)
$$0<\left|\beta \frac{p}{q}\right|<\frac{1}{q^m}.$$

These Liouville numbers are all transcendcental (see Lemma 6 below)—in fact Liouville introduced these numbers precisely to exhibit specific transcendental numbers, and the off-cited example

$$\beta =\underset{n=1}{\overset{\mathrm{}}{}}10^{n!}=0.11000100000000000000000100\mathrm{}$$

is usually the first number that students see proven transcendental.

Clearly $`\beta `$ is abnormal to the base 10; how would we go about showing, for example, that $`\beta `$ is abnormal to the base 2? We would try to argue that the binary expansion of $`\beta `$ agrees with that of each of the rational numbers

(4)
$$\beta _k=\underset{n=1}{\overset{k}{}}10^{n!}$$

through about the $`((n+1)!\mathrm{log}_210)`$-th binary digit. Since each $`\beta _k`$ is rational and thus abnormal to the base 2, can we conclude that $`\beta `$ itself is abnormal to the base 2?

Not quite: it seems that we would have to show that there is a fixed power $`2^n`$ such that infinitely many of the $`\beta _k`$ were not simply normal to the base $`2^n`$. (For each $`\beta _k`$ there is some power $`2^{n_k}`$ such that $`\beta _k`$ is not simply normal to the base $`2^{n_k}`$, but these exponents $`n_k`$ might very well grow with $`k`$.) In fact, it is not hard to show (using the fact that 2 is a primitive root modulo every power of 5) that any 10-adic fraction that is not a 2-adic fraction—including each $`\beta _k`$is simply normal to the base 2! In general, without actually computing binary expansions of specific fractions, it seems impossible to rule out the incredible possibility that the $`\beta _k`$ are accidentally simply normal to bases that are high powers of 2. In summary, any Liouville number we write down is almost certain (morally) to be absolutely abnormal, but actually proving its absolute abnormality is another matter.

To circumvent this difficulty, we construct a Liouville number whose successive rational approximations are $`b`$-adic fractions with $`b`$ varying, rather than all being 10-adic fractions as in equation (4). The existence of such Liouville numbers can certainly be proven using just the fact that the $`b`$-adic fractions are dense for any integer $`b2`$; however, our construction is completely explicit. We first give the complete construction of our irrational, absolutely abnormal number $`\alpha `$ and then show afterwards that $`\alpha `$ has the required properties.

## 2. The construction and proof

We begin by defining a sequence of integers

$$d_2=2^2,d_3=3^2,d_4=4^3,d_5=5^{16},d_6=6^{\text{30,517,578,125}},\mathrm{}$$

with the recursive rule

(5)
$$d_j=j^{d_{j1}/(j1)}(j3).$$

This sequence exhibits the pattern

$$d_4=4^{3^{21}},d_5=5^{4^{\left(3^{21}1\right)}},d_6=6^{5^{(4^{\left(3^{21}1\right)}1)}},\mathrm{}$$

which in general gives the typesetting nightmare

(6)
$$d_j=j^{(j1)^{\left(\left(j2\right)^{\left(\left(j3\right)^{\left(\text{.}\text{.}\text{.}^{\left(4^{\left(3^{21}\right)}1\right)}\text{.}\text{.}\text{.}\right)}1\right)}1\right)}}.$$

Using these integers, we define the sequence of rational numbers

(7)
$$\alpha _k=\underset{j=2}{\overset{k}{}}\left(1\frac{1}{d_j}\right),$$

so that $`\alpha _2=\frac{1}{4}`$, $`\alpha _3=\frac{2}{3}`$, $`\alpha _4=\frac{21}{32}`$, $`\alpha _5=\frac{\text{100,135,803,222}}{\text{152,587,890,625}}`$, and so on.

We now nominate

(8)
$$\alpha =\underset{k\mathrm{}}{lim}\alpha _k=\underset{j=2}{\overset{\mathrm{}}{}}\left(1\frac{1}{d_j}\right)$$

as our candidate for an irrational, absolutely abnormal number. The first few digits in the decimal expansion of $`\alpha `$ are

(9)
$$\alpha =0.6562499999956991\underset{\text{23,747,291,559 9s}}{\underset{}{99999\mathrm{}99999}}8528404201690728\mathrm{},$$

from which we can get an inkling of the extreme abnormality of $`\alpha `$ (at least to the base 10). We need to prove three things concerning this number $`\alpha `$: first, that the infinite product (8) defining $`\alpha `$ actually converges; second, that $`\alpha `$ is irrational; and finally, that $`\alpha `$ is absolutely abnormal.

It is apparent from the expressions (5) and (6) that the $`d_j`$ grow (ridiculously) rapidly and hence that the infinite product (8) should indeed converge. The following lemma provides a crude inequality relating the integers $`d_j`$ that we can use to prove this assertion rigorously.

###### Lemma 1.

For $`j5`$ we have $`d_j>2d_{j1}^2`$.

Proof: We proceed by induction, the case $`j=5`$ being true by inspection. For $`j>5`$ we surely have

$$d_j=j^{d_{j1}/(j1)}>5^{d_{j1}/(j1)}.$$

Notice that from the definition (5) of the $`d_j`$,

$$\frac{d_{j1}}{j1}=(j1)^{\frac{d_{j2}}{j2}1}>(j1)^{\frac{d_{j2}}{2\left(j2\right)}}=\sqrt{d_{j1}},$$

and therefore

$$d_j>5^{\sqrt{d_{j1}}}.$$

Now using the fact (easily proven by your favorite calculus student) that $`5^xx^5`$ for $`x5`$, we conclude that

$$d_j>\left(\sqrt{d_{j1}}\right)^5>2d_{j1}^2,$$

as desired. ∎

Equipped with this inequality, we can now show that the infinite product (8) defining $`\alpha `$ converges. Moreover, we can show that the number $`\alpha `$ is well approximated by the rational numbers $`\alpha _k`$. (Notice that $`\alpha _4`$ is exactly $`0.65625`$ and $`\alpha _5`$ is exactly $`0.6562499999956992`$—cf. the decimal expansion (9) of $`\alpha `$.)

###### Lemma 2.

The product (8) defining $`\alpha `$ converges. Moreover, for $`k2`$ we have

(10)
$$\alpha _k>\alpha >\alpha _k\frac{2}{d_{k+1}}.$$

Proof: To show that the product (8) converges, we must show that the corresponding sum $`_{j=2}^{\mathrm{}}1/d_j`$ converges. But by Lemma 1 we certainly have $`d_j>2d_{j1}`$ for $`j5`$, and therefore

$$\underset{j=2}{\overset{\mathrm{}}{}}\frac{1}{d_j}\frac{1}{d_2}+\frac{1}{d_3}+\underset{j=4}{\overset{\mathrm{}}{}}\frac{1}{2^{j4}d_4}=\frac{1}{d_2}+\frac{1}{d_3}+\frac{2}{d_4}<\mathrm{}.$$

Similarly, using the fact that $`1(1x_j)1x_j`$ for any real numbers $`0x_j1`$, we see that for $`k3`$

$$\begin{array}{c}\alpha _k>\alpha =\alpha _k\underset{j=k+1}{\overset{\mathrm{}}{}}\left(1\frac{1}{d_j}\right)\alpha _k\left(1\underset{j=k+1}{\overset{\mathrm{}}{}}\frac{1}{d_j}\right)\hfill \\ \hfill >\alpha _k\left(1\underset{j=k+1}{\overset{\mathrm{}}{}}\frac{1}{2^{jk1}d_{k+1}}\right)=\alpha _k\left(1\frac{2}{d_{k+1}}\right)>\alpha _k\frac{2}{d_{k+1}}.\end{array}$$

The inequalities (10) for $`k=2`$ follow from those for $`k=3`$, as it is easily verified by hand that $`\alpha _2>\alpha _3>\alpha _3\frac{2}{d_4}>\alpha _2\frac{2}{d_3}`$. ∎

It turns out that both the proof that $`\alpha `$ is irrational and the proof that $`\alpha `$ is absolutely abnormal hinge on the fact that each rational approximation $`\alpha _k`$ is in fact a $`k`$-adic fraction—that is, when $`\alpha _k`$ is expressed in lowest terms, its denominator divides a power of $`k`$. In other words, each time we multiply $`\alpha _{k1}`$ by $`1\frac{1}{d_k}=\frac{d_k1}{d_k}`$ to obtain $`\alpha _k`$, the numerator of the latter fraction completely cancels out the denominator of $`\alpha _{k1}`$, so that all that can remain in the denominator of $`\alpha _k`$ are the powers of $`k`$ present in $`d_k`$. Proving that this always happens is an exercise in elementary number theory, which we present in the next three lemmas.

###### Lemma 3.

Let $`k`$ and $`r`$ be positive integers, and let $`p`$ be a prime. If $`k`$ is divisible by $`p^r`$, then $`(k+1)^p1`$ is divisible by $`p^{r+1}`$.

Proof: Writing $`k=p^rn`$, we have from the binomial theorem

$$\begin{array}{cc}\hfill (k+1)^p1& =(p^rn+1)^p1\hfill \\ & =\left\{(p^rn)^p+\left(\genfrac{}{}{0pt}{}{p}{p1}\right)(p^rn)^{p1}+\mathrm{}+\left(\genfrac{}{}{0pt}{}{p}{2}\right)(p^rn)^2+\left(\genfrac{}{}{0pt}{}{p}{1}\right)p^rn+1\right\}1\hfill \\ & =p^{rp}n^p+\left(\genfrac{}{}{0pt}{}{p}{p1}\right)p^{r(p1)}n^{p1}+\mathrm{}+\left(\genfrac{}{}{0pt}{}{p}{2}\right)p^{2r}n^2+pp^rn.\hfill \end{array}$$

Since all of these binomial coefficients $`\left(\genfrac{}{}{0pt}{}{p}{k}\right)`$ are integers, each term in this last sum is visibly divisible by $`p^{r+1}`$. ∎

###### Lemma 4.

For any positive integers $`k`$ and $`m`$, the integer $`(k+1)^{k^m}1`$ is divisible by $`k^{m+1}`$.

Proof: If $`p^r`$ is any prime power dividing $`k`$, an $`rm`$-fold application of Lemma 3 shows us that $`(k+1)^{p^{rm}}1`$ is divisible by $`p^{r+rm}`$. Then, since

$$(k+1)^{k^m}1=\left((k+1)^{p^{rm}}1\right)\left((k+1)^{k^mp^{rm}}+(k+1)^{k^m2p^{rm}}+\mathrm{}+(k+1)^{p^{rm}}+1\right),$$

we see that $`(k+1)^{k^m}1`$ is also divisible by $`p^{r(m+1)}`$.

In particular, since $`p^r`$ was an arbitrary prime power dividing $`k`$, we see that $`(k+1)^{k^m}1`$ is divisible by every prime power that divides $`k^{m+1}`$. This is enough to verify that $`(k+1)^{k^m}1`$ is divisible by $`k^{m+1}`$ itself. ∎

###### Lemma 5.

For each $`k2`$, the product $`d_k\alpha _k`$ is an integer. In particular, since $`d_k`$ is a power of $`k`$, we see that $`\alpha _k`$ is a $`k`$-adic fraction.

Proof: We proceed by induction on $`k`$, the cases $`k=2`$ and $`k=3`$ being evident by inspection. For the inductive step, suppose (as our induction hypothesis) that $`d_k\alpha _k`$ is indeed an integer for a given $`k3`$. We may write

(11)
$$d_{k+1}\alpha _{k+1}=(d_{k+1}1)\alpha _k=\left((k+1)^{d_k/k}1\right)\alpha _k=\frac{(k+1)^{d_k/k}1}{d_k}d_k\alpha _k$$

by the definitions (5) and (7) of $`d_k`$ and $`\alpha _k`$, respectively. The second factor $`d_k\alpha _k`$ is an integer by the induction hypothesis. On the other hand, we may rewrite

$$(k+1)^{d_k/k}1=(k+1)^{k^{d_{k1}/(k1)1}}1.$$

Applying Lemma 4 with $`m=d_{k1}/(k1)1`$, we see that this expression is divisible by $`k^{d_{k1}/(k1)}=d_k`$. Therefore the fraction on the right-hand side of equation (11) is in fact an integer, and so $`d_{k+1}\alpha _{k+1}`$ is itself an integer, which completes the proof. ∎

As mentioned in the introduction, the key to proving that $`\alpha `$ is irrational is to show that it is in fact a Liouville number. It is a standard fact that any Liouville number is transcendental (see for instance \[6, Theorem 7.9\]); for the sake of keeping this paper self-contained, we include a proof.

###### Lemma 6.

Every Liouville number is transcendental.

Proof: We shall prove the contrapositive, that no algebraic number can satisfy the Liouville property (3) for all positive $`m`$. Suppose that $`\beta `$ is algebraic. Without loss of generality, we may suppose that $`|\beta |\frac{1}{2}`$ by adding an appropriate integer. Let

$$m_\beta (x)=c_dx^d+c_{d1}x^{d1}+\mathrm{}+c_2x^2+c_1x+c_0$$

be the minimal polynomial for $`\beta `$, where the coefficients $`c_i`$ are integers. Now suppose that $`\frac{p}{q}`$ is a rational approximation to $`\beta `$, say $`|\beta \frac{p}{q}|<\frac{1}{2}`$. Then

$$\begin{array}{cc}\hfill m_\beta \left(\frac{p}{q}\right)& =m_\beta \left(\frac{p}{q}\right)m_\beta (\beta )\hfill \\ & =c_d\left(\left(\frac{p}{q}\right)^d\beta ^d\right)+\mathrm{}+c_2\left(\left(\frac{p}{q}\right)^2\beta ^2\right)+c_1\left(\frac{p}{q}\beta \right)\hfill \\ & =\left(\frac{p}{q}\beta \right)\left(c_d\left(\left(\frac{p}{q}\right)^{d1}+\left(\frac{p}{q}\right)^{d2}\beta +\mathrm{}+\beta ^{d1}\right)+\mathrm{}+c_2\left(\frac{p}{q}+\beta \right)+c_1\right).\hfill \end{array}$$

Since neither $`\beta `$ nor $`\frac{p}{q}`$ exceeds 1 in absolute value, we see that

(12)
$$\left|m_\beta \left(\frac{p}{q}\right)\right|\left|\frac{p}{q}\beta \right|C(\beta ),$$

where we have defined the constant

$$C(\beta )=d|c_d|+(d1)|c_{d1}|+\mathrm{}+2|c_2|+|c_1|.$$

On the other hand, $`m_\beta \left(\frac{p}{q}\right)`$ is a rational number with denominator at most $`q^d`$, and it is nonzero since $`m_\beta `$ is irreducible. Therefore

(13)
$$\left|m_\beta \left(\frac{p}{q}\right)\right|\frac{1}{q^d}.$$

Together, the inequalities (12) and (13) imply that

$$\left|\beta \frac{p}{q}\right|\frac{C(\beta )^1}{q^d},$$

which precludes the inequality (3) from holding when $`m`$ is large enough. ∎

To show that $`\alpha `$ is indeed a Liouville number, we will need an inequality somewhat stronger than the one given in Lemma 1. The following lemma furnishes a simple inequality that is strong enough for this purpose.

###### Lemma 7.

For $`j5`$ we have $`d_{j+1}>d_j^{d_{j1}}`$.

Proof: It is immediate that

$$d_{j+1}=(j+1)^{d_j/j}>j^{d_j/j}>j^{2d_{j1}^2/j}=(j^{d_{j1}/(j1)})^{d_{j1}2(j1)/j}=d_j^{d_{j1}2(j1)/j}>d_j^{d_{j1}},$$

where we have used Lemma 1 for the second inequality. ∎

###### Lemma 8.

$`\alpha `$ is a Liouville number; in particular, $`\alpha `$ is transcendental.

Proof: We can easily show show that the $`\alpha _k`$ provide the very close rational approximations needed in equation (3) to make $`\alpha `$ a Liouville number. Indeed, $`\alpha _k`$ can be written as a fraction whose denominator is $`d_k`$ by Lemma 5, while Lemma 10 tells us that for $`k5`$

$$0<|\alpha \alpha _k|<\frac{2}{d_{k+1}}<\frac{2}{d_k^{d_{k1}}},$$

where the last inequality is by Lemma 7. Since $`d_{k1}`$ tends to infinity with $`k`$, this shows that $`\alpha `$ is a Liouville number (and hence transcendental by Lemma 6). ∎

At last we have all the tools we need to establish the theorem stated in the introduction:

Theorem. The number $`\alpha `$ defined in equation (8) is irrational and absolutely abnormal.

Proof: We have just shown in Lemma 8 that $`\alpha `$ is irrational. As for proving that $`\alpha `$ is absolutely abnormal, the idea is that for every integer base $`b2`$, the number $`\alpha `$ is just a tiny bit less than the $`b`$-adic fraction $`\alpha _b`$. Since the $`b`$-ary expansion of $`\alpha _b`$ terminates in an infinite string of zeros, the slightly smaller number $`\alpha `$ will have a long string of digits equal to $`b1`$ before resuming a more random behavior. (This is evident in the decimal expansion (9) of $`\alpha `$, as $`\alpha _5`$ is a 10-adic fraction as well as a 5-adic fraction.) This happens more than once, as each of $`\alpha _b`$, $`\alpha _{b^2}`$, $`\alpha _{b^3}`$, and so on is a $`b`$-adic fraction. Consequently, the $`b`$-ary expansion of $`\alpha `$ will have increasingly long strings consisting solely of the digit $`b1`$, which will prevent it from being even simply normal to the base $`b`$.

More quantitatively, let $`b2`$ and $`r`$ be positive integers. Since $`d_{b^r}\alpha _{b^r}`$ is an integer by Lemma 5, and since $`d_{b^r}=(b^r)^{d_{b^r1}/(b^r1)}`$ by definition, the $`b`$-ary expansion of $`\alpha _{b^r}`$ terminates after at most $`rd_{b^r1}/(b^r1)`$ nonzero digits. On the other hand, by Lemma 10 we know that $`\alpha `$ is less than $`\alpha _{b^r}`$ but by no more than $`2/d_{b^r+1}=2/(b^r+1)^{d_{b^r}/b^r}<2/b^{rd_{b^r}/b^r}`$. Therefore, when we subtract this small difference from $`\alpha _{b^r}`$, the resulting $`b`$-ary expansion will have occurrences of the digit $`b1`$ beginning at the $`(rd_{b^r1}/(b^r1)+1)`$-th digit at the latest, and continuing through at least the $`(rd_{b^r}/b^r1)`$-th digit since the difference will start to show only in the $`(rd_{b^r}/b^r)`$-th digit at the soonest. Using the notation defined in equation (1), this implies that

$$N(\alpha ;b,b1,\frac{rd_{b^r}}{b^r})\frac{rd_{b^r}}{b^r}\frac{rd_{b^r1}}{b^r1}1>\frac{rd_{b^r}}{b^r}\frac{2rd_{b^r1}}{b^r}.$$

At this point we can calculate that

$$\begin{array}{cc}\hfill \underset{x\mathrm{}}{lim\; sup}x^1N(\alpha ;b,b1,x)& \underset{r\mathrm{}}{lim\; sup}\left(\frac{b^r}{rd_{b^r}}N(\alpha ;b,b1,\frac{rd_{b^r}}{b^r})\right)\hfill \\ & \underset{r\mathrm{}}{lim\; sup}\left(1\frac{2d_{b^r1}}{d_{b^r}}\right).\hfill \end{array}$$

Using Lemma 1, we see that

$$\underset{x\mathrm{}}{lim\; sup}x^1N(\alpha ;b,b1,x)\underset{r\mathrm{}}{lim\; sup}\left(1\frac{2d_{b^r1}}{2d_{b^r1}^2}\right)=\underset{r\mathrm{}}{lim\; sup}\left(1\frac{1}{d_{b^r1}}\right)=1.$$

In particular, the frequency $`\delta (\alpha ;b,b1)`$ defined in equation (2) either does not exist or else equals 1, either of which precludes $`\alpha `$ from being simply normal to the base $`b`$. Since $`b2`$ was arbitrary, this shows that $`\alpha `$ is absolutely abnormal. ∎

## 3. Generalizations and further questions

We mentioned in the introduction that our construction of an irrational, absolutely abnormal number can be generalized to exhibit an uncountable set of absolutely abnormal numbers in any open interval, and we now describe that extension. Clearly we may limit our attention to subintervals of $`[0,1]`$, since the set of normal numbers to any base is invariant under translation by an integer. In the original construction at the beginning of Section 2, we began with $`d_2=2^2`$ and $`\alpha _2=\frac{3}{4}`$; to be more general, let $`\alpha _2`$ be any 2-adic fraction $`\frac{a}{d_2}`$, where $`d_2=2^{n_2}`$ for some positive integer $`n_2`$. Next fix any sequence $`n_3`$, $`n_4`$, …of positive integers and modify the recursive definition (5) of the $`d_j`$ to

(14)
$$d_j=j^{n_jd_{j1}/(j1)}(j3).$$

If we now set

$$\alpha _k=\alpha _2\underset{j=3}{\overset{k}{}}\left(1\frac{1}{d_j}\right)$$

(where of course the numbers $`\alpha _k`$ now depend on $`\alpha _2`$ and the $`n_j`$), then the presence of the integers $`n_j`$ will not hinder the proof of Lemma 5 that $`d_k\alpha _k`$ is always a $`k`$-adic fraction (this is a consequence of the fact that $`x1`$ always divides $`x^n1`$). Therefore the new limit $`\alpha =lim_k\mathrm{}\alpha _k`$ can be shown to be a transcendental, absolutely abnormal number in exactly the same way, the modifications only accelerating the convergence of the infinite product and enhancing the ease with which the various inequalities in the Lemmas are satisfied. (When we make this modification, then the one case we must avoid is $`\alpha _2=\frac{1}{2}`$ and $`n_2=n_3=\mathrm{}=1`$, for in this case it will happen that $`d_j=j^1`$ for every $`j2`$. Then each product $`\alpha _k`$ is a telescoping product with value $`\frac{1}{k}`$, and their limit $`\alpha =0`$, while certainly absolutely abnormal, will be uninterestingly so.)

In particular, Lemma 10 applied with $`k=2`$ would show in this context that $`\frac{a}{2^{n_2}}>\alpha >\frac{a2}{2^{n_2}}`$; thus by choosing $`\alpha _2=\frac{a}{2^{n_2}}`$ appropriately, we can ensure that the resulting number $`\alpha `$ lies in any prescribed open subinterval of $`[0,1]`$. Moreover, the various choices of the integers $`n_3`$, $`n_4`$, …will give rise to distinct limits $`\alpha `$; one can show this by considering the first index $`j3`$ at which the choices of $`n_j`$ differ, say, and then applying Lemma 10 with $`k=j`$ to each resulting $`\alpha `$. This generalization thus permits us to construct uncountably many transcendental, absolutely abnormal numbers in any prescribed open interval.

One interesting special case of this generalized construction arises from the choices $`\alpha _2=\frac{1}{2}`$ and $`n_j=\varphi (j1)`$ for all $`j3`$, where $`\varphi `$ is the Euler totient function; these choices give the simple recursive rule $`d_j=j^{\varphi (d_{j1})}`$ for $`j3`$. In this special case, the crucial property that $`d_k\alpha _k`$ is always an integer is in fact a direct consequence of Euler’s theorem that $`a^{\varphi (n)}`$ is always congruent to 1 modulo $`n`$ as long as $`a`$ and $`n`$ have no common factors. In general, the smallest exponent $`e_k`$ we can take in the recursive rule $`d_k=k^{e_k}`$ so that this crucial property is satisfied is the multiplicative order of $`k`$ modulo $`n`$, which might be smaller than $`d_{k1}/(k1)`$; however, our construction given in Section 2 has the advantage of being more explicit, as it is not necessary to wait and see the exact value of $`d_{k1}`$ before knowing how we will construct $`d_k`$.

We remark that Schmidt’s construction  mentioned in the introduction actually gives the following more powerful result: given any set $`S`$ of integers exceeding 1 with the property that an integer $`b`$ is in $`S`$ if and only if every perfect power of $`b`$ is in $`S`$, Schmidt constructed real numbers that are normal to every base $`bS`$ and abnormal to every base $`bS`$. (The problem considered herein is the special case where $`S=\mathrm{}`$.) It would be interesting to see if the construction in this paper could be modified to produce these “selectively normal numbers” as well.

We conclude with a few remarks about absolutely simply abnormal numbers, numbers that are simply normal to no base whatsoever. As we saw in the proof of our Theorem, the number $`\alpha `$ does in fact meet this stronger criterion of abnormality. On the other hand, while all rational numbers are absolutely abnormal, many of them are in fact simply normal to various bases. For example, $`1/3`$ is simply normal to the base 2, as its binary representation is $`0.010101\mathrm{}`$. In fact, one can check that every fraction in reduced form whose denominator is 3, 5, 6, 9, 10, 11, 12, 13, 17, 18, 19, 20, …is simply normal to the base 2 (presumably there are infinitely many such odd denominators—can it be proven?); every fraction whose denominator is 7, 14, 19, 21, 31, …is simply normal to the base 3; and so on. Somewhat generally, if $`p`$ is a prime such that one of the divisors $`b`$ of $`p1`$ is a primitive root for $`p`$, then every fraction whose denominator is $`p`$ is simply normal to the base $`b`$ (although this is not a necessary condition, as the normality of fractions with denominator 17 to base 2 shows).

For a fraction with denominator $`q`$ to be simply normal to the base $`b`$ (we can assume, by multiplying by $`b`$ a few times if necessary, that $`b`$ and $`q`$ are relatively prime), it is necessary for $`b`$ to divide the multiplicative order of $`b`$ modulo $`q`$, and hence $`b`$ must certainly divide $`\varphi (q)`$ by Euler’s theorem. Therefore, we immediately see that every fraction whose denominator is a power of 2 is absolutely simply abnormal. One can also verify by this criterion that every fraction whose denominator in reduced form is 15 or 28, for example, is absolutely simply abnormal. It seems to be a nontrivial problem to classify, in general, which rational numbers are absolutely simply abnormal. Since some fractions with denominator 63 are simply normal to the base 2 while others are not, as one can check, absolute simple abnormality probably depends in general on the numerator as well as the denominator of the fraction.

Acknowledgements: Glyn Harman gave a survey talk on normal numbers at the Millennial Conference on Number Theory at the University of Illinois in May 2000 (see ), at the end of which Andrew Granville asked the question about a specific absolutely abnormal number that spurred this paper. Carl Pomerance suggested the number $`_{n=1}^{\mathrm{}}(n!)^{n!}`$, a Liouville number which again is almost surely absolutely abnormal, but a proof of this seems hopeless. The author would like to thank all three for their interest in this construction, and also an anonymous referee for several helpful comments on a preliminary version of this paper.