Introduction

Probabilistic

analysis:-

This algorithm mostly used in that algorithm that is

complex and difficult to understand. In this algorithm we have to understand

the problem and have to observe the inputs of that algorithm. Those

observations used to design the efficient and attractive algorithm and finish

the complexities of the algorithm.

Here we know that, two cases are occurred, 1st

one is “BEST CASE” and the 2nd one is ”WORST CASE”. One other

situation takes place between the Best and the Worst case, which is “AVERAGE

CASE”. We analyze the Average case very rarely.

So we can say that, probabilistic analysis is used

to understand and describe the Average case behavior.

Moreover we should say that there is no input in

these types of algorithms, we have to estimate the input by our self. Then we

apply the probability to get the efficient and attractive algorithm. We have to assume the input of any problem

which we have to get from known probability distribution and the output which

is get from assuming the input of any problem should be more efficient and

attractive. By probabilistic, how much we can achieve the target from any

input.

Randomized

Algorithm:-

When we have to design the algorithm then we used

the randomized technique. Sometime we

have to choose the good option, when we have many options for randomization. We

have the coin toss example, coin has two faces (head and tail) and there is a

two possibilities it should be head and tail (Random). So in that situations

randomized algorithm used.

We can also say that if we have the one fixed input

then we have the possibility that there should be a many outputs in the random

way. In this we don’t have need to assume the input.

Randomized algorithm is applicable where the input

size is finite; the reason is that as have to select a randomized or random

number from the input. Suppose we have to select the last number from the input

size, we can select the last number even if we know the size or last value so

that’s why the randomized algorithm is applicable where the input size is fixed

or finite.

The selection behavior is not only depends on the

input size but also depends on the value produced by Randomized algorithm

(Random number generator).

Suppose we have given the array of 10 elements or

more than 10 elements then the selection of the random number not depends on

the size of array but also depends upon the random number generator which can

either be selected from start or mid or from end.

The

Hiring Problem

There is problem is that, we want to hire a

assistant. And we decided to use a agency. The agency send the unemployed

person one by one. But the company ignore the academic and other ability of

employee and send them one by one for interview. But it is over budget for us

to interview and hire a person because we have paid a few charges for

interviewing a person to the company and also pay the charges to person if we

hire him. If the cost which we pay to company for interview a person is ci

and we interviewed N number of person then the total cost which paid to

company is cin. It is not matter that how many people have hire. But

if the charges that pay to hired assistant is ch then the total cost

that paid to n hired employee is chn. if we hired a assistant and

interview to next person and compare him with current assistance and hire him

if he has best ability as compare to current assistance then it is very costly

for us.

Hire-Assistant(n)

1

Best = 0

2

for k=1 to n

3

interview candidate k

4

if candidate k is better than best

5

best = k

6

hire best

if we analysis it then if the order of person is

increasing order then it will worst case that we hired every candidate which we

interviewed. And it is very costly because we have paid to every candidate who

has hired. So our task is to make such type of algorithm which decrease the

probability to reach worst case every time.

Solution

for Problem

As the worst case reach due to order of candidate.

We can avoid to reach worst case if we take the control over order of candidate

for interview. So for this, we request to agency to provide the list for

interview candidate and everyday call a candidate for interview randomly. For

example if we call RANDOM algorithm with input of candidate list such as ‘a’ to

‘b’ then there is possibility to hire assistant ‘a’ with probability ½ and ‘b’

with probability ½. A call RANDOM(2,6) return 2,3,4,5 or 6 with probability

1/5.

Birthday

Paradox

In analyzing of algorithms, most of the algorithms

are that in which we know the input values or parameters to analyze of that

algorithm, but sometimes we does not know the input values which we have to use

in analyzing of the algorithm. But in sometimes exact input values for the

algorithms are unknown, in that case we take some assumptions that are the

probabilistic distribution of all the inputs and then analyze the performance

of our algorithm by applying to any random input which we have from the

distribution. And this assumption then lead to design an efficient algorithm.

Now we take the example of birthday paradox to prove

that we have discussed above. The birthday paradox or birthday problem is that

we have a small group of random people and there are 50% chances that two of

them have the same birthday. This is very rare that two persons from a small

group have same birthday. To solve this problem we assume that there are k

people in the room and we take n as total days of year as 365. Let i and j be

the two persons that we compares that they have the same birthday, the

probability that i and j have same birthday is surprisingly few. The

probability that given two persons I and j have same birthday is totally

depends on the random selection of birthdays that it is independent. The

probability that I and j have same birthday is 1/n. It means that if bi

is chosen, then the probability that bj also chose on the same day

is 1/n. If for example there are 23 people in the room then the probability is

at least ½ that 2 people have same birthday.

To solve this problem we define the indicator random

variable Xij that person i and j have the same birthday in which 1

indicates the same birthday and 0 indicates that they have different birthdays.

The probability that I and j have the same birthday is 1/n where n is the total

number of days in a year. Let X be a random variable that will counts the pairs

the persons individually that have the same birthday. So the pair which have

the same birthday from expected number of pairs is at least 1. If for example

we have 28 persons in a room, then we have at least 1 pair that have the same

birthday from given pairs. So by analyzing using both the probability and

indicator random variable the expected number of matching birthdays is 1.

Similarly we have a process in which randomly toss

identical balls into b bin which are independent. We does not know that how

many balls fall into the bins, for this we take the probability. There are

equally likely chances that the tossed ball will fall into the bin or not fall

in the bin. The probability that the balls falls in the bin is 1/b. For example

if we toss n balls into the bin then the probability that the balls fall into

the bin is n/b. If we want that every bin have a ball then approximately blnb

tosses are required for every bin have a ball.