Generating probability distributions from a given probability distributions

Here, we contemplate on generating a new uniform distribution given another uniform distribution. Specifically, for example, when we have a function rand7(), which generates random numbers from 1 to 7 (or 0 to 6), we want to compute rand5(), that generated random numbers from 1 to 5. Later, we look at the reverse problem - given rand5(), can we generated rand7().

First problem: Given rand7(), can we generate rand5() i.e. random numbers between 1 and 5?. This is easy - use rand7() to generate a random number, say x, and then output the result as y = x if x <=5. What if x = 6 or 7? Then, we simply repeat the experiment, i.e. we keep calling rand7() until we get a random number between 1 to 5. So that was simple? But, we still have to prove mathematically that this definition of rand5(), generates uniform random numbers i.e. the function outputs the numbers between 1 and 5 with probability 1/5 each. Let's try!

Let, A be the probability that rand5() outputs number 1, then

A=

Pr[rand5() outputs 1]
= Pr[y = 1 ]
=  Pr[ x= 1 ] + Pr[ x = 6 or 7] . Pr [ rand5() outputs 1]

= 1/7 + 2/7 * A

Thus,  A = 1/5. Similarly, Probability for other numbers 2 till 5 is same as 1/5 ! That was easy too! Right? Let's see a tough problem.

Now consider the reverse problem - Given rand5(), we want to implement rand7(). How do we go about it? Intuitively, we see that we need to use rand5() multiple times since we want to generate numbers 6 and 7 as well, which cannot be generated by a single call to rand5(). The idea is, since rand5() generates numbers till 5, we want a formula such that it produces the remaining numbers i.e. 6 and 7. For example, if we wanted to implement rand19() using rand5(), then this formula should generate all the numbers after 5 as well. We won't mind if this formula generates number beyond 19, since we now know, how to generate only 19 numbers randomly from a big random generator (see first problem!). Coming back to rand7(), consider the formula:

F = 5 * [rand5() - 1] + rand5()

This formula uses rand5() two times. We see that, it generates all the numbers from 1 to 25 only once. You can verify this. (Actually, this formula resembles, formula for Base-5 representation, and, in fact,  it draws inspirations from it). Hence this is rand25(), each number has probability of 1/25. Now, using rand25(), we can easily generate rand7(), by using first problem's solution i.e. use rand25() and output the number if it is less than equal to 7 or else call rand25() again. But, we will be little more smarter for this problem. This approach has a subtle issue that we will talk about later. But for now consider new solution for generating rand7() from rand25():

Use rand25() and let y be the output number of rand25(). If y <= 21, then rand7() outputs number x = y mod 7. A subtlety here, set x = 1 when (y mod 7) = 0. Or else, we repeat the call to rand25(). The idea is, 21 is multiple of 7 and hence when we do mod 7 to the number between 1 and 21, then we see that each number between 1 and 7 has occurred equally i.e. 3 times

Why is second idea more smarter than the first one? Because, if we implement rand7() using rand25() in computer program, then second solution is faster! The reason is, for first solution, the probability of getting a number between 1 and 7 using rand25() in first call, is only 7/25 whereas for the second solution, it is 21/25. Hence, on an expectation, second solution would produce output within 2 iterations whereas first solution would take more than 3 iterations!

Generating probability distributions from a given probability distributions

Here, we contemplate on generating a new uniform distribution given another uniform distribution. Specifically, for example, when we have a function rand7(), which generates random numbers from 1 to 7 (or 0 to 6), we want to compute rand5(), that generated random numbers from 1 to 5. Later, we look at the reverse problem - given rand5(), can we generated rand7().

First problem: Given rand7(), can we generate rand5() i.e. random numbers between 1 and 5?. This is easy - use rand7() to generate a random number, say x, and then output the result as y = x if x <=5. What if x = 6 or 7? Then, we simply repeat the experiment, i.e. we keep calling rand7() until we get a random number between 1 to 5. So that was simple? But, we still have to prove mathematically that this definition of rand5(), generates uniform random numbers i.e. the function outputs the numbers between 1 and 5 with probability 1/5 each. Let's try!

Let, A be the probability that rand5() outputs number 1, then

A=

Pr[rand5() outputs 1]
= Pr[y = 1 ]
=  Pr[ x= 1 ] + Pr[ x = 6 or 7] . Pr [ rand5() outputs 1]

= 1/7 + 2/7 * A

Thus,  A = 1/5. Similarly, Probability for other numbers 2 till 5 is same as 1/5 ! That was easy too! Right? Let's see a tough problem.

Now consider the reverse problem - Given rand5(), we want to implement rand7(). How do we go about it? Intuitively, we see that we need to use rand5() multiple times since we want to generate numbers 6 and 7 as well, which cannot be generated by a single call to rand5(). The idea is, since rand5() generates numbers till 5, we want a formula such that it produces the remaining numbers i.e. 6 and 7. For example, if we wanted to implement rand19() using rand5(), then this formula should generate all the numbers after 5 as well. We won't mind if this formula generates number beyond 19, since we now know, how to generate only 19 numbers randomly from a big random generator (see first problem!). Coming back to rand7(), consider the formula:

F = 5 * [rand5() - 1] + rand5()

This formula uses rand5() two times. We see that, it generates all the numbers from 1 to 25 only once. You can verify this. (Actually, this formula resembles, formula for Base-5 representation, and, in fact,  it draws inspirations from it). Hence this is rand25(), each number has probability of 1/25. Now, using rand25(), we can easily generate rand7(), by using first problem's solution i.e. use rand25() and output the number if it is less than equal to 7 or else call rand25() again. But, we will be little more smarter for this problem. This approach has a subtle issue that we will talk about later. But for now consider, new solution for generating rand7() from rand25():

Use rand25(), let y be the output number of rand25(). If y <= 21, then rand7() outputs number x = y mod 7. Or else, we repeat the call to rand25(). The idea is, 21 is multiple of 7 and hence when we do mod 7 to the number between 1 and 21, then we see that each number between 1 and 7 has occurred equally i.e. 3 times

Why is second idea more smarter than the first one? Because, if we implement rand7() using rand25() in computer program, then second solution is faster! The reason is, for first solution, the probability of getting a number between 1 and 7 using rand25() is only 7/25 whereas for the second solution, it is 21/25. Hence, on an expectation, second solution would produce output within 2 iterations whereas first solution would take more than 3 iterations!

Generating probability distributions from a given probability distributions

Here, we contemplate on generating a new uniform distribution given another uniform distribution. Specifically, for example, when we have a function rand7(), which generates random numbers from 1 to 7 (or 0 to 6), we want to compute rand5(), that generated random numbers from 1 to 5. Later, we look at the reverse problem - given rand5(), can we generated rand7().

First problem: Given rand7(), can we generated rand5() i.e. random numbers between 1 and 5?. This is easy - use rand7() to generate a random number, say x, and then output the result as y = x if x <=5. What if x = 6 or 7? Then, we simply repeat the experiment, i.e. we keep calling rand7() until we get a random number between 1 to 5. So that was simple? But, we still have to prove mathematically that this definition of rand5(), generates uniform random numbers i.e. the function outputs the numbers between 1 and 5 with probability 1/5 each. Let's try!

Let, A be the probability that rand5() outputs 1, then

A=

Pr[rand5() outputs 1] = Pr[y = 1 ]
=  Pr[ x= 1 ] + Pr[ x = 6 or 7] . Pr [ rand5() outputs 1]

= 1/7 + 2/7 * A

Thus,  A = 1/5. Similarly, Probability for other numbers 2 to 5 is same as 1/5 ! That was easy too! Let's see a tough problem.

Now consider the reverse problem - Given rand5(), we want to implement rand7(). How do we go about it? Intuitively, we see that we need to use rand5() multiple times since we want to generate numbers 6 and 7, which cannot be generated by a single call of rand5(). The idea is, since rand5() generates numbers till 5, we want a formula such that it produces the next consequent numbers i.e. 6 and 7. For example, if we wanted to implement rand19() using rand5(), then this formula should generate all the numbers 6 onwards. We won't mind if this formula generates number beyond 19, since we now, know how to generate only 19 numbers randomly from a big random generator (see first problem!). Coming back to rand7(), consider the formula:

F = 5 * [rand5() - 1] + rand5()

This formula uses rand5() two times. We see that, it generates all the numbers from 1 to 25 only once. You can verify this. Hence this is rand25(), each number has probability of 1/25. Now, using rand25(), we can easily generate rand7(), by using first problem's solution i.e. use rand25() and output the number if it is less than equal to 7 or else call rand25() again. But, we will be little more smarter for this problem. This approach has a subtle issue that we will talk about later. But for now consider, new solution for generating rand7() from rand25():

Use rand25(), let y be the output number of rand25(). If y <= 21, then rand7() outputs number x = y mod 7. Or else, we repeat the call to rand25(). The idea is, 21 is multiple of 7 and hence when we do mod 7 to the number between 1 and 21, then we see that each number between 1 and 7 has occurred equally i.e. 3 times

Why is second idea more smarter than the first one? Because, if we implement rand7() using rand25() in computer program, then second solution is faster! The reason is, for first solution, the probability of getting a number between 1 and 7 using rand25() is only 7/25 whereas for the second solution, it is 21/25. Hence, on an expectation, second solution would produce output within 2 iterations whereas first solution would take more than 3 iterations!

if...and only if

I always get confused with these things. I read it, understand it and then forget it. So that's why I wrote it down.

p -> q
This means if p then q. Two views on this implication:

1. Here p is the sufficient condition, in the sense that it is sufficient to conclude that q happened if we are sure that p happened. This also means, that there are other ways of making q happen and one of them is p.

2. Here q is the neccessary condition, in the sense that q is necessary condition for p to happen. But p may either choose to happen or not choose to happen and hence q is not sufficient condition for p.

Eg: Amit will eat the fruit -> fruit is an apple
1.  To conclude that the fruit is an apple, it is sufficient to find if Amit ate the fruit. So Amit will eat the fruit is sufficient condition for fruit to be an apple. Note that it is not the necessary condition as fruit could be apple but Amit did not eat it.
2. Here fruit being apple is necessary condition for Amit to eat the fruit since it means Amit will only eat apples. Note that, Amit will only eat apples and the given fruit being apple is not sufficient as Amit might choose not eating all the apples given to him.

In short, for q to happen, it is sufficient that p happens (and there could be other ways of making q happen). And, for p to happen, it is necessary that q happens (this is the only condition to make p happen and nothing else).

p <-> q
Here q is both necessary and sufficient condition for p. Consider:
Eg: Amit will eat fruit <-> fruit is an apple
It means that Amit will eat all and only those fruits that are apples. He will not leave any apple uneaten and he will not eat any other fruit. Hence, given fruit is apple is both a necessary and sufficient condition for Amit to eat the fruit.



P.S. p -> q means (a) if p then q or (b) q if p or (c) p only if q.
P.P.S. The 'if' in the above statements can be replaced by 'when' or 'whenever'.


Source: wikipedia.org

Unary Subset Sum: myth or reality?

Subset Sum problem [SUBSET SUM ]:
Given a list of n numbers and a number k, is there a subset of the numbers that
adds to exactly k? For example, the answer is yes for  <(3, 4, 12, 7, 4), 20> and no
for <(3, 4, 12, 7, 4), 6>.

When the input is expressed in binary (or any other base except unary), it takes exponential time to solve this problem. But hang on!

Unary Subset Sum problem [UNARY SSUM]:
Same problem but the input is expressed in unary!

Result: UNARY SSUM is in P!

Here are the details, that are taken from http://www.cs.virginia.edu/~evans/cs3102-s10/ps/ps6/ps6-comments.pdf

• Why does the NP-completeness proof for SUBSET SUM fail to show UNARY SSUM is NP-complete?
  Answer. The crux of the question is that we measure complexity as a function from the size of the input to the number of steps required to run the decided on that input. When the input is represented in unary, the size of the input is equal to the value (that is, it takes x squares to represent the input value x). When the input is represented in binary (or any higher base), it takes log x squares to represent the input value x. Hence, the if size of the input in binary is N, the size of the same input in unary is 2^N. This, the size of the input increases exponentially, even though the problem is of the same difficulty as it would be for the corresponding binary input. The reduction proof fails because the reduction from 3SAT to UNARY SSUM requires more than polynomial time. The input size increases exponentially, so the transformation to generate the corresponding input for UNARY SSUM requires a number of steps that is exponential in the size of the input.
• Show that UNARY SSUM ∈ P.
  Answer. To show a language is in P, we need to show there is a polynomial-time algorithm that decides it. Note the we can simulate a nondeterministic TM in exponential time using a deterministic TM. Hence, if SUBSET SUM is in NP, we know UNARY SSUM (the same problem, but with exponentially larger input size) is in P, since we can solve it by first converting the input to binary representation (which can be done in polynomial time) and shrinks the input size to log N. Then, we can simulate the nondeterministic polynomial-time TM running on this input (which has size log N) in time that is exponential in its input size, which is polynomial in log N.

the sorted Array and the scanner problem continued…

Wherein the previous post gave the efficient step size for this problem, but there is still a scope of improvement.  Suppose the array size is 100, with our approach the maximum number of comparisons required would be 10+9 = 19. Could we beat this? Yes, I suppose. What if rather than having a fixed step size of sqrt(n) throughout the algorithm, we opt for dynamic step size. Let’s start with step size 18 and see if we could beat our previous answer of 19. The first comparison will happen at 18^th element and if the search element lies in this group then we need another 17 linear comparisons in worst case to find the element in that group making a total of 18 comparisons. Now if the search element is greater than 18^th element then we have to consider the next group. And here lies the secret.  We decide to shrink the next group size by 1, so that this group has 17 elements rather than 18. The reason for this is, we want the total comparisons to be strictly 18 in worst case and since we have already used up one comparison at 18^th element, we have only 17 remaining. Thus to search the element in the second group we need 16 more comparisons and hence making the total comparisons equal to 16+1+1=18 in worst case. Now what we really have to do is to continue this idea until all 100 elements are exhausted. So the group size continues to reduce by 1 at each stage. Hence the third group would have 16, fourth would have 15, fifth would have 14 and so on and so forth.

This algorithm makes sure that we won’t cross the count of 18 comparisons at any cost. But why is it only the number 18? Why not 17? Yes 17 would just do fine. Even the number 16 does remarkably well. But again, as with the previous post what’s the ideal value to start with, since we cannot go forever reducing the number. The only cue we have at this point is whatever count we start with, it should assure us that it covers all the 100 elements. Suppose we start with step size equal to 10 and at each successive group we reduce the group size by 1 to maintain the count. But all the groups so formed doesn’t cover all the 100 elements since the total elements covered in all groups is

10 + 9 + 8 + . . . . . . + 3 + 2  + 1 = (10*11)/2 = 55

So step size 10 covers only 55 elements. Though it failed to be an ideal answer it did give us an insight to find the one. If we start with step size equal to x then the total number of elements covered by the groups formed by x is

x + (x-1) + (x-2) + . . . . . . + 3 + 2 + 1

=∑ x 

Thus the only condition that makes x the ideal choice is that the above summation should cover all the n elements in the array. Hence we have a new equation –

∑ x ≥ n

(x*(x+1))/2 ≥ n

=>  x² + x ≥ 2n

i.e.  x² + x  - 2n ≥ 0

Since we are looking for least value of x,

x² + x  - 2n = 0

And the solution for this is

x = (-1 ± √ (–1 – 8n))/2

For integer value,

x = ceil ((√ (8n + 1) -1)/2)

Thus for n = 100, x comes to be 14 and I bet you can’t beat this!

the sorted Array and the scanner problem

I came across this puzzle during my Msc(Engg) interview in IISc Bangalore. The puzzle was simple and stated as -

"You are given a sorted array of length n and a pointer that points to the first element in the array. This is a special pointer that can be reversed in direction only once. That means if it was moving to right and then it decides to move towards left then it keeps on moving to left. It cannot change its direction again."

The problem is to come up with an efficient algorithm to search a number in the array.

While it took me fews seconds to put all the conditions and situations together, my first response was to do a linear search. And that was accepted quite generously. Of course, the next question as anticipated was "Can you do better?"

This algorithm had a running time of n. So I decided to divide the array into two parts. I suggested directly compare the middle element with the search element and depending upon the outcome, we move into either of the half. This reduced the running time to n/2. That too was accepted cordially and followed by the same question!

Instead of targeting the middle element, we could target, say n/3^th element. So running time is down to n/3 from my first response of n. Next question was a bouncer.

"So what's the appropriate step size that gives the best efficiency?"

He meant, we could go endlessly by choosing n/5 ^th, n/10 ^th, n/20 ^th and so on. Which one of them would be the best?

Suddenly I recalled a similar problem that I had read long back on 20bits.com, which tries to find similar solution. But I couldn’t recollect the way he had solved, probably because four IIsc professors were continuously gazing me. I tried recollecting and gave up. But I gave them a brief idea how could we find the solution. They looked satisfied with my broken answer and asked me to ponder upon it after the interview.

Soon, I was heading back home in a BMTC bus. My mind was completely occupied with calculations and trying to find the solution for that problem. But I did it! I found it in BMTC!!

It was not that difficult as it sounded in the interview room. We wanted to find the step size that would lead best efficiency. So If I choose n/3 step size, then once finding the appropriate partition I had to do a linear search for remaining 2 elements in the partition. The explanation being, since each partition had 3 elements and one of them gets compared at each step size, I had to check the remaining 2 using linear search. What if I take step size n/10? I needed to check another 9 elements using linear search in the partition.

So, mathematically put, the total number of comparisons required –

n/s + (s-1)

where

n -> array length and s -> step size.

This equation preciously defines the number of comparisons required for a generic step size s. The first part of the equation: n/s, indicates the number of partitions that are formed due to step size s and these were the number of comparisons required on the step size in worst case, as the search element could be in the last partition. The other part: (s-1), indicates the number of linear comparisons required once we found our partition. Since each partition had s elements and one of them was already compared during partition searching, we required only s-1 more comparisons.

Now we have a mathematical representation of the problem we are dealing with and we just needed to find the step size that resulted into minimum comparisons. Hence we simply needed to find the value of s where the above equation had a minima. And that’s typical differentiation stuff. We differentiate the above equation wrt s and equate it to zero to get the required value of s.

Thus on differentiating and equating the above equation to zero,

-n/s² +1 =0

=> n = s²

Or s = √n

 i.e. s = sqrt(n)

And that’s it!

continued...