You should be Smart!

After discussing the random number, today we are going to discuss one of the application of random number in Game Theory. Although this article is more inclined toward probability but there is use of random number at crucial point. 

Today we are going discuss TRUEL (three-person "duels").

One morning, three bosom friends Mr. White, Mr. Black and Mr. Grey were decide to go for hunting. After few efforts they were able to find a deer. All the three shot blindly to the deer and one of the bullet hit it and the deer fell down. All the three flitted toward it but when they reached , there is a dispute among them for who will take the credit of hunting. The spark turn into blistering fire and  the bosom friends turn into sworn enemy and to resolve the conflict they agreed on truelling with pistols until only one of them survives.

Mr. Black is the worst shot, hitting his target on average only one time in three. Mr. Grey is a better shot hitting his target two times out of three. Mr. White is the best shot hitting his target every time. To make the truel fairer Mr. Black is allowed to shoot first, followed by Mr. Grey (if he is still alive), followed Mr. White (if he is still alive), and round again until only one of them is alive.

The question is where should Mr. Black aim his first shot? 

Although Mr. Black was a rookie shooter but he was smart. He examine the options. If he aim at Mr. Grey and if he is successful then the next shot will be taken by Mr. White. Mr. White has only one opponent left , Mr. Black himself and as Mr. White is a perfect shot he would be dead.

He consider another and better option, is to aim at Mr.White. If he is successful then the next shot will be taken by Mr. Grey. Mr. Grey hits his target only two times out of three and so there is a chance that he( Mr. Black) will survive to fire back at Mr. Grey and possibly win the truel.

Mr. Black was even much more smarter and he switch toward the third and much better option. He could aim into air.Mr. Grey has the next shot and he will aim at Mr. White , because he is more dangerous opponent. If Mr. White survives then he will aim at Mr. Grey because he is more dangerous opponent. By aiming inti the air , Mr Black is allowing Mr. Grey to eliminate Mr. White or vice-versa.

Whatever had be the result and whoever had won ..'main mudda ye hai' you should be smart!.
Now where is random number involves in it? Actually in this case we give priority to Mr. Baclk, but to choose who will shoot the first we decide it  randomly by generating random numbers.

What is Random Number??

It is hard to define a random number, actually there is no mathematical way to define a random number completely. In subjective we can say that:

         "A set where each of the element has equal probability of occurrence"

                     "A sequence in which each term is unpredictable"

The strength of random number is depend on the amount of information it carry, for example:

suppose that there two number one having infinite length and other having finite length  ".....1111111111......" and 11011111100111011. the first one consist of negligible information,while the second one has some significant information. So we can say that, randomness does not depend on the length of  a number but it depends on the information carried by it.

How to generate random number??       

    As we know some traditional method of generating random number such as flipping of coin, rolling of dice, shuffling of coin etc. But in the present world life is nothing without a computer. It is one of the basic need of Human Beings.

So how a computer is able to generate a random number? as it follows blindly its instructions.Without any input how it is able to generate random number? lets discuss it.

There are two methods to generate random number in a computer:

1. Pseudo random number generator.

2. True Random number generator.

Pseudo random number generator:  

"Anyone who considers arithmetical 
                                        methods of producing random digits is,
                                                                               of course, in a state of sin."  

 It is a algorithm of generating sequence of number that exhibit properties of random   number.But in technical terms it is nothing more than a "jugaad".

In PRNG, it generate a random number is generated using a 'seed' ( which is usually date and time) . On the basis of the seed, it do its calculation and produces  a sequence. And after some values it start repeating its cycle, it means that they are periodic.

There are several method of generating pseudo random number:

•      Linear Congruential Generator
•       Lagged Fibonnaci Generator
•    Shift Register Generator
•    Combined Generators 

Lets start with  the most easiest  one..

Linear Congruential Generator:

 LCG generate the next value using the previous one.

X_i=(aX _i-1+c)  Mod  m

where a is multiplier,c is addend and Mis modulous and X is 'seed'..

Let  a=1,c=5,m=16 and X₀=1

With Pseudo random number generator  it is easy to generate random number with low cost and it generate the random numbers with the velocity of light.. means at very fast speed.

Now..how our Modern computer generate random number..

 http://www.youtube.com/watch?v=Ac4Z1VMsE3E

but..but...there is a problem with Pseudo random number, means our jugaad gets fails when, one knows our key i.e. seed. One will be able to detect what is our number if he know seed.

There are some factors by which we can produce a random number of appropriate quality:

Uncorrelated Sequences - The sequences of random numbers should be serially uncorrelated.

Long Period –The generator should be of long period.

Uniformity - The random numbers should be uniformly distributed within a specified region.

Efficiency - As literally millions or even billions of random numbers are required in a large-scale simulation, the generator should be efficient.

Now, leave  jugaad and focus on generating true random number..

True random number:

                        "It is impossible to predict the unpredictable."

True random generator generate the random number from physical source,such as thermal 

noise,photoelectric effector, quantum mechanics etc... 

A hardware random number generator typically consists of a transducer to convert some aspect of the physical phenomena to an electrical signal, an amplifier and other electronic circuitry to increase the amplitude of the random fluctuations to a macroscopic level, and some type of analog to digital converter to convert the output into a digital number, often a simple binary digit 0 or 1. By repeatedly sampling the randomly varying signal, a series of random numbers is obtained.

In theoretical TRNG produce complete random number. As it solve the problem of PRNG  of security of key and produces good quality of random number,but..there is also a problem with TRNG they are very slow.

Applications..

Random number has wide application in every field....some of them are..

1.Simulation

2.Network Security

3.Data Encryption

4.Digital Signature

5.Gambling/Casino

6.Recreation/Games

7.Protocols

etc.................

So both method have their pros. and cons.  
According to the need they use. In Monte-Carlo simulation speed is major factor, so in this case pseudo random number is uses. 
While in digital signature for private key security is major factor  true random number are  use. 
In cryptography hybrid of them is use, means true random number gives seed and  and with this seed pseudo random number is produced.

And with various tests we can test the quality of random.