Q.6.10 - A First Course in Probability

Question

The “random” parts of the algorithm in Self-Test Problem 6.8 can be written in terms of the generated values of a sequence of independent uniform (0, 1) random variables, known as random numbers. With [x] defined as the largest integer less than or equal to x, the first step can be written as follows: 

Step 1. Generate a uniform (0, 1) random variable U. Let X = [mU] + 1, and determine the value of n(X). 

(a) Explain why the above is equivalent to step 1 of Problem 6.8. Hint: What is the probability mass function of X?

 (b) Write the remaining steps of the algorithm in a similar style 

Step-by-Step Solution

Answer

a) The probability mass function of X is $P=\frac{1}{m}$

b) The remaining steps of the algorithm in a similar style are:

Step 2:

Generate a uniform (0,1) random variable$U if U<\frac{n\left(X\right)}{n}$go to step 3 (repeat to step 1).

Step 3:

Generate a uniform variable (0,1) which is randomly generated and select the element on page X in position $\left[n\right(x) U+1]$

Part (a)- Step 1: To find

probability mass function of X.

Part (a) Step 2: Explanation

The probability mass function of$\mathrm{X}(\mathrm{X}=[\mathrm{mU}]+1)$ is same as that of selecting a page out of m pages,

$P=\frac{1}{m}$

Part (b) - Step 3: To find

Remaining steps of the algorithm in a similar style.

Part (b) - Step 4: Explanation

Step:1  Generate a uniform (0,1) Random variable U If $U<\frac{n\left(X\right)}{n}$ go to

Step:2 other return to step-1.

Step:3 Generate a uniform variable (0,1) which is Randomly generated and select the element on page $\mathrm{X}$ in position $\left[n\right(X)U+1]$