Deterministic Time

Question

If a problem must be solved in deterministic time, what exactly does it mean.

I am beginning to learn more in depth ML and came across this problem

Write a function sample_x( ) to draw independent samples of a random variable with probability density function

p(x) = 6(1/4 - (x - 1/2)^2) for 0 <= x <= 1 OR 0 otherwise

Assume you have a function RNG( ) that returns independent floats uniformly distributed in [0,1]. Can you find a way of doing this that runs in a deterministic amount of time?

What does it mean to run it in a deterministic amount of time??

Answer 1

To understand what deterministic time is helps to understand what both deterministic time and stochastic time are.

stochastic time and deterministic time are two polar opposites.

EXAMPLE OF STOCHASTIC TIME

A program runs in "stochastic" time if how-long-the-program takes-to-run is probabilistic. For example:

+-------------+--------------------------------------+
| 80% chance  |    it finishes in 2 hours or less    |
+-------------+--------------------------------------+
| 10% chance  | 2 hours < finish_time <= 2 days      |
+-------------+--------------------------------------+
| 5% chance   | 2 day < finish_time <= 2 weeks       |
+-------------+--------------------------------------+
| 2.5% chance | 2 weeks < finish_time <= 2 months    |
+-------------+--------------------------------------+
| 2.5% chance |       finish_time > 2 months         |
+-------------+--------------------------------------+

An example of a stochastic algorithm would be trying to sell 10 bottles of wonder window cleaner by going door to door.

The number of homes you must ring the doorbell at before all 10 bottles of wonder window cleaner are sold is stochastic

The phrase "stochastic time" can almost always be replaced by the phrase "an uncertain amount of time".

EXAMPLE OF DETERMINISTIC TIME

A program runs in deterministic time if how much time the program requires is predictable and certain, and does not change so long as different inputs are all the same size as other inputs.

Suppose that I write a function which takes a list of people's names and my function capitalizes the first letter of each person's name.

def capitalize_names(old_names):
    old_names = iter(old_names)
    out_names = list()
    for old_name in old_names:
        mid_name = "".join(str(ch) for ch in old_name)
        out_name = "".join(mid_name[0:1]).upper() + "".join(mid_name[1:]).lower()
        out_names.append(out_name)
    return out_names


names = filter(lambda x: len(x) > 0, "jane, ZACK, SaRaH, WILLiam, John, Able".split(", "))
out_names = capitalize_names(names)
print(out_names)
# prints ['Jane', 'Zack', 'Sarah', 'William', 'John', 'Able']

The capitalize_names() function runs in deterministic time.
Thus, the capitalize_names() function is NOT stochastic

---

Additional Notes

If you are expected to know what the phrases "stochastic time" and "deterministic time" mean then you will also be expected to understand what the following symbols and words mean:

• "linear time"
• "quadratic time"
• "exponential time"
• "polynomial time"
• "non-polynomial time"
• O(n)
• O(n^p)
• O(2^n)

What is "Linear Time"

Suppose again that you simply want to capitalize people names.

If the number of people's names to be capitalize is n, and names are all less than 100 characters long, then the amount of time it takes our program is t*n where t is the average number seconds per name.

We do not know exactly how much time it is (maybe we require t == 0.832 nanoseconds per name).

When talking about "linear time" it does not matter exactly how many nanoseconds are required per name.

Capitalizing names executes in "linear time"

"linear time" is also written as O(n)

O(n) and "linear time" mean the same thing, it is just that some people like mathematical looking symbols instead of Minglish (mathy-English).

If we have to capitalize n peoples names it will take us time equal to some number times n.

Suppose that you write two for-loops:

for name in names:
    print(capitalize(name))

for name in names:
    print(to_piglatin(name))

What does to_piglatin do?

Well...

to_piglatin()
INPUTS:   ['Jane', 'Zack', 'Sarah', 'William', 'John', 'Able']
OUTPUTS:  Anejay Ackzay Arahsay Illiamway Ohnjay Ableyay

That's what it does.

You might thing that the program runs on the order of 2*n

Well... sort of yes and no.

For "linear time" constant coefficients do not matter.

• n is O(n)
• 2*n is O(n)
• 4*n is O(n)
• 5*n is O(n)
• 500*n is O(n)
• 9083389475838495848 * n is O(n)

Also, 7*n + 36 is on the order of n

"on the order of n" is written as O(n).

Simply delete constant terms like 5 or 971.10

Note that if a computer program took a billion years to finish executing, then a billion and one years would not be much different.

That is, for very large values of n, n + 1 is basically the same as n.

100,000,000 ≈ 100,000,001

What is "polynomial time"?

Sometimes, if we have n people to process, a computer will require 0.686 nanoseconds times 9*n^5 + 5*n^2 + 82.

For very large values of n, + 82 does not matter.

9*n^5 + 5*n^2 + 82 becomes 9*n^5 + 5*n^2

For very large values of n, n^5 is like 99.999% of n^5 + n^2.

In the end, 9*n^5 + 5*n^2 + 82 is "on the order of n^5" which is also written as O(n^5)

If the amount of time your code takes to finish is O(n^5) and n is the number of peoples names you are processing, then your algorithm runs in polynomial time

• n is polynomial
• n^2 is polynomial
• n^3 is polynomial
• n^4 is polynomial
• n^9002181028 is polynomial
• n raised to any constant power greater than 1 is polynomial

What about your question

It is a trick question.

IF I hand you a number x can you calculate p(x) = 6(1/4 - (x - 1/2)^2) in deterministic time?

I sure hope so.

PYTHON!

def p(x):
     return 6*(1/4 - (x - 1/2)**2)

That does not take much time to calculate. Not much time at all.

Technically, x - 1/2 might take more time to calculate if x == 0.9374923 than if x == 0.2

If x is output from a random number generator, then how much time p requires to execute might be stochastic instead of deterministic

However, it is silly to say that p() is stochastic.

Whoever wrote that question probably lives in an ivory tower and will never write a self-documenting variable name in their entire life. Instead of "surface_area" they will write "a".

Also, they will use all global variables inside of one massive function which is more than 3,000 lines long.

Write a function sample_x() to draw independent samples of a random variable with probability density function

p(x) = 6(1/4 - (x - 1/2)^2) for 0 <= x <= 1
p(x) = 0 otherwise

Assume you have a function RNG( ) that returns independent floats uniformly distributed in [0,1]. Can you find a way of doing this that runs in a deterministic amount of time?

LATEX!

$$
p(n) =
\begin{cases}
6\begin{pmatrix}\frac{1}{4} - (x - \frac{1}{2})^{2} \end{pmatrix},  & \text{ for } 0 \leq x \leq 1  \\
0, & \text{ otherwise}
\end{cases}
$$

Boy, wouldn't it be nice if you could write "1/4" instead of "\frac{1}{4}"?