-In this paper, the idea of solving birthday paradox problem is proposed. Presented method is based on the application of Computational Intelligence. For different parameters the proposed solution has been performed. Research results has been gathered and presented to show possible advantages.
Computational Intelligence (CI) is a methodology which involves computing to obtain systems with the ability to learn specific behavior and act like intelligent one. There are three main pillars of CI - fuzzy logic, neural networks and evolutionary computation. These methodologies are usually inspired by nature but we can find their application in the real - world problems in which mathematical or traditional modeling are impossible to employ for a few reasons: 1) process is to complex for traditional modeling or simply there is no mathematical algorithm available 2) imprecise or incomplete data 3) process might have stochastic nature and the optimal solution is unknown CI provides solutions for such problems by creating tools or systems which can imitate intelligent behavior and have some human - like abilities, i.e. learning, dealing with new situations or decision making.
CI methods take inspiration from our natural environment.
They are based on observations of human organism - i.e.
nervous or immune system and animals’ behavior - their
lifestyle, adaptation to new conditions and scrabbling.
They find their applications in many areas like optimization
[
Algorithm simulating cuckoo search for nests in the forest
was applied to intelligent video frames targeting [
The first version of simulated annealing algorithm was
presented in [
In this article simulated annealing algorithm was used to solve a birthday paradox, where implemented procedure was made to calculate possibility of similarity in dates.
Common probability problem, proposed by Richard von Mises in 1939 can be stated: what is the minimal number n of people in the randomly chosen group for whom the probability that some pair of them will share the same birthday is greater than there is no pair like that? In other words, probability that there are two people with the same birthday date must be greater than 50%. The answer is that there must be at least 23 people in the random group. Many people says that it is surprisingly little number and that is why problem is called paradox. Pigeonhole principle says that probability reaches 100% when there are at least 366 (or 367 at leap years) people in the group, so for 50% likelihood there should be 183 (184) people. The thing is that in the group of 23 people there is more than 22 comparisons. We have to compare everyone to everyone, not only one person. This way, for 23 people we have 23222 = 253 comparisons. Another counter - intuitive thing is that growth of the probabilities, which depends of number of people, is not linear. To simplify the problem we can make a few assumptions: 1) no leap years, every year has 365 days 2) two people have the same birthday when month and day are the same, year is ignored 3) all dates are equally likely (in fact, more babies are born in Spring then in other seasons) 4) multiple births are considered as one birthday
Sometimes it is easier to calculate probability of the opposite event to ours. In our case, instead of calculating probability that two people have birthday at the same day, we will find probability that they don’t. For showing it, we can use inequality that follows from probability: p(k; n) = pk = = 1 (1 = Qik=11(1 1 ) (1 n i ) n 2 ) : : : (1 n kn 1 ) = (1) where p(k; n) is the probability that sequence of k elements (number of people) chosen from n elements (365 days of the year) will be injective. Let’s note it pk using 1.
This event is opposite to ours. Because we want our event to be more probable than 50%, 0 pk 0; 5. We have to find minimal k for which pk 0; 5.
we can estimate pk: ex that is true 8x 2 R, pk = e = e = (1 1 3615 ) (1 3625 ) : : : (1 e 365 e 3625 : : : e k3651 = 1+2+:3::6+5(k 1) = k(k 1) 730 k3651 ) = 0; 5, we need to find the minimal k, for which
we have k2 k 730 0 The least positive solution of this inequality is 1 + p1 + 4 730 ln 2 2
Due to shortening operation time of every program, we are looking for the fastest solutions. This is the main reason for using CI to solve birthday paradox problem. We want to know how many people must be in the randomly chosen group to make sure that probability that there is a pair of people that have birthday at the same day is greater than 50%. By doing it on traditional way, we have to take many samples of 1,2,3,... person group (randomly chosen) and count the probability. By using CI we can get the minimum number of people much quicker. (2) (3) (4)
V. SIMULATED ANNEALING METHOD
Annealing is a metallurgical process based on heating the metal up to a high temperature, then keeping it at given conditions and after that, slow cooling it down. The last stage of this process is the most important step to achieve final conditions. It has to be monitored in order to keep the metal in the state similar to thermodynamic equilibrium, i.e. the state in which parameters such as volume and pressure are constant in time. We have three main elements that thermodynamic equilibrium consists of: 1) thermal equilibrium - constant temperature as a result of no heat exchange with the environment 2) mechanical equilibrium - constant pressure at any point 3) chemical equilibrium - no chemical reactions, no changes in the structure of the metal We can describe the thermodynamics of the whole process by equation below:
P (E)
E e kT (5) where E is the thermodynamic system, T is the absolute temperature and k is the Boltzmann’s constant.
Mathematical models are to describe processes and relations
that are present in nature, science and technology by
application of devoted sequences of equations describing modeled
situation in a mathematical way, where we use these equations to
calculate the state of the simulated objects in initial conditions
and convert it after changes in the following operations. These
operations are performed by application of various computer
procedures where we use computational power to perform
numerical experiments simulating the object. In the presented
approach one of important CI methods was implemented to
solve the birthday paradox in a way similar to annealing
processes i.e. discussed for application in verification systems
[
Simulated Annealing Method (SAM) assumes that temperature at the beginning of the process is high. It enables frequent changes in configurations. When the temperature is lower, there is less possibility for choosing the worst solution so it is the criterion of acceptation of the solution. Therefore, we use modified equation (5) in a simplified form:
P (E)
e T = f (x0) f (x) where is the difference between the value of fitness function calculated at the new random solution chosen from neighborhood x0 and current solution x according to: For a benchmark tests a simplified fitness condition was chosen x f (x) = (8) 2 This equation is enough to perform experiments since linear function is enough to simulate controlled growth of numerical (6) (7) data in this experiment. For a new solution we have criterion of acceptance: < e T (9) where is chosen randomly, and temperature we can denote as : 2 (0; 1). Change of Tk+1 = Tk r (10) where Tk is the temperature in the k-th iteration and r is constant given at the beginning, where r 2 (0; 1). For the benchmark test stop criterion was adapted to the modeled object.
In the test method presented in Algorithm 1 was implemented, for which we can also present a block diagram show in Fig. 1. Firstly we establish initial values and random initial solution x. The list date was created to remember x and next solutions which satisfy our algorithm. When new solution, y, gratify condition (9), we add it to the list date. After every iteration we check if there are two the same numbers in the list date. If so, we break our loop and save the length of the list in the next list average. After clearing date, we are doing the same as long as length of average is less then or equal to number of samples in each iteration which was given at the beginning. When average is complete, we take the average value of all elements from average and that is our result for given parameters.
Results of numerical experiments are shown in Tab. II Tab. III. For these results changes of probability that among selected population are people for whom birthday paradox can be encountered are presented in Tab. I and depicted in Fig. 2. For each set of parameters, 28 results has been received and then by taking the average of them, we get out final result number of people. Outcomes presented in Tab. II - Tab. III are very close to expected 23. In two cases we get exactly this number - presented in Tab. III for parameters T = 1050, p = 103, r = 0; 84, pr = 850 and T = 1049, p = 103, r = 0; 83, pr = 850, as we can see, very similar to each other.
We can state parameters for which, by rounding out we get the expected value for our paradox - 23. As a fitness function linear one was chosen but it turn out that for power and exponential function we obtain similar results. The most important was choosing optimal parameters. The greatest impact for value of result have initial temperature and radius of neighbourhood - along with their decrease, values of results are also lower. Drop of number of samples in each iteration causes bigger range of received solutions. What is surprising, different values of the temperature change, don’t change the results.
In this article simulated annealing method was used to solve a problem of birthday paradox. This is definitely better way to obtain solution than traditional counting probability by taking many samples of 1,2,3,... person groups. By using CI methods,we get the solution easier and what is very important, faster. Benchmark tests have been performed to indicate the best paramaters for our algorithm. 22 23 22 23 22 23 23 23 23 22 23 23 23 23 22 23 23 23 22 23 23 23 23 23 23 22 23 23