The following algorithm will generate a random permutation of the elements 1,2, ..., n. It is somewhat faster than the one presented in Example 1a, but is such that no position is fixed until the algorithm ends. In this algorithm, P ( i ) can be interpreted as the element in position i . Step 1. Set k = 1 Step 2. Set P ( 1 ) = 1 . Step 3. If k = n , stop otherwise, let k = k + 1 . Step 4. Generate a random number U and let P ( k ) = P ( [ k U ] + 1 ) P ( [ k U ] ÷ 1 ) = k Go to step 3. a. Explain in words what the algorithm is doing. b. Show that at iteration kâ€”that is. when the value of P(k) Is initially setâ€” P(1), P(2), ..., P(k) is a random permutation of 1, 2, ..., k. Hint: Use induction and argue that P k { i 1 , i 2 ... , i j − 1 , k , i j , ... , i k − 2 , i } = P k − 1 { i 1 , i 2 ... , i j − 1 , k , i j , ... , i k − 2 } 1 k = 1 k ! by the induction hypothesis

Question

Want to see more full solutions like this?

Answer 1

Textbook Question

Chapter 10, Problem 10.1P

The following algorithm will generate a random permutation of the elements 1,2, ..., n. It is somewhat faster than the one presented in Example 1a, but is such that no position is fixed until the algorithm ends. In this algorithm, P ( i ) can be interpreted as the element in position i.

Step 1. Set k = 1

Step 2. Set P ( 1 ) = 1 .

Step 3. If k = n , stop otherwise, let k = k + 1 .

Step 4. Generate a random number U and let P ( k ) = P ( [ k U ] + 1 ) P ( [ k U ] ÷ 1 ) = k

Go to step 3.

a. Explain in words what the algorithm is doing.

b. Show that at iteration kâ€”that is. when the value of P(k) Is initially setâ€”

P(1), P(2), ..., P(k) is a random permutation of 1, 2, ..., k.

Hint: Use induction and argue that P k { i 1 , i 2 ... , i j − 1 , k , i j , ... , i k − 2 , i } = P k − 1 { i 1 , i 2 ... , i j − 1 , k , i j , ... , i k − 2 } 1 k = 1 k ! by the induction hypothesis

(a)

Expert Solution

To determine

To find: the explanation that the algorithm is doing.

Explanation of Solution

Given:

Some steps of algorithm are given.

The algorithm starts by initially putting k=1 thus it sets p(1)=1 .

Then, until K=M it increases the value of K by one after each iteration. It generates a random number U and replaces p(k) by p([ku]+1) . Then, it puts p([ku]+1)=k . Then, it goes again to step 3.

This algorithm start by putting p(1)=1 , but it does not exclude this value in next interation the value of p(1) can change in any subsequent iteration. Thus, no position is fixed until the algorithm ends.

Therefore, therequired explanation is shown above.

(b)

Expert Solution

To determine

To prove:that the set p(1), p(2), ....., p(k) which is a random permutation of 1,2,....,k .

Explanation of Solution

Given:

It is given that pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×p{ik} .

As it is given that the condition pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×p{ik} .

It is known that;

p{ik}=1total sample space=1k

Then, the given condition becomes;

pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×1k

Similarly,

pk{i1, i2,......,ik}=1k×1k−1×.....11=1k!

This proves that at iteration k can be defined as p(1), p(2), ....., p(k) which is a random permutation of 1,2,....,k .

Therefore, the required identity has been proved.

Want to see more full solutions like this?

Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!

Students have asked these similar questions

A warranty is written on a product worth $10,000 so that the buyer is given $8000 if it fails in the first year, $6000 if it fails in the second, and zero after that. The probability of the product’s failing in a year is 0.15; failures are independent of those of other years. What is the expected value of the warranty?

The probability that a machine produces a defective item is 0.02. Each item is checked as it is produced. Assume that these are independent trials, and compute the probability that at least 90 items must be checked to find one that is defective.

Bowl A contains 3 white and 2 red chips, bowl B contains 4 white and 4 red chips, and bowl C contains 4 white and 5 red chips. The probabilities of selecting bowls A, B, and C are 1/3, 1/6, and 1/2 respectively. One chip is selected at random. Given that a white chip is selected what is the probability that it came from bowl C. Round your answer to three decimal places.

Answer 2

Textbook Question

Chapter 10, Problem 10.1P

The following algorithm will generate a random permutation of the elements 1,2, ..., n. It is somewhat faster than the one presented in Example 1a, but is such that no position is fixed until the algorithm ends. In this algorithm, P ( i ) can be interpreted as the element in position i.

Step 1. Set k = 1

Step 2. Set P ( 1 ) = 1 .

Step 3. If k = n , stop otherwise, let k = k + 1 .

Step 4. Generate a random number U and let P ( k ) = P ( [ k U ] + 1 ) P ( [ k U ] ÷ 1 ) = k

Go to step 3.

a. Explain in words what the algorithm is doing.

b. Show that at iteration kâ€”that is. when the value of P(k) Is initially setâ€”

P(1), P(2), ..., P(k) is a random permutation of 1, 2, ..., k.

Hint: Use induction and argue that P k { i 1 , i 2 ... , i j − 1 , k , i j , ... , i k − 2 , i } = P k − 1 { i 1 , i 2 ... , i j − 1 , k , i j , ... , i k − 2 } 1 k = 1 k ! by the induction hypothesis

(a)

Expert Solution

To determine

To find: the explanation that the algorithm is doing.

Explanation of Solution

Given:

Some steps of algorithm are given.

The algorithm starts by initially putting k=1 thus it sets p(1)=1 .

Then, until K=M it increases the value of K by one after each iteration. It generates a random number U and replaces p(k) by p([ku]+1) . Then, it puts p([ku]+1)=k . Then, it goes again to step 3.

This algorithm start by putting p(1)=1 , but it does not exclude this value in next interation the value of p(1) can change in any subsequent iteration. Thus, no position is fixed until the algorithm ends.

Therefore, therequired explanation is shown above.

(b)

Expert Solution

To determine

To prove:that the set p(1), p(2), ....., p(k) which is a random permutation of 1,2,....,k .

Explanation of Solution

Given:

It is given that pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×p{ik} .

As it is given that the condition pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×p{ik} .

It is known that;

p{ik}=1total sample space=1k

Then, the given condition becomes;

pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×1k

Similarly,

pk{i1, i2,......,ik}=1k×1k−1×.....11=1k!

This proves that at iteration k can be defined as p(1), p(2), ....., p(k) which is a random permutation of 1,2,....,k .

Therefore, the required identity has been proved.

Want to see more full solutions like this?

Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!

Answer 3

Textbook Question

Chapter 10, Problem 10.1P

The following algorithm will generate a random permutation of the elements 1,2, ..., n. It is somewhat faster than the one presented in Example 1a, but is such that no position is fixed until the algorithm ends. In this algorithm, P ( i ) can be interpreted as the element in position i.

Step 1. Set k = 1

Step 2. Set P ( 1 ) = 1 .

Step 3. If k = n , stop otherwise, let k = k + 1 .

Step 4. Generate a random number U and let P ( k ) = P ( [ k U ] + 1 ) P ( [ k U ] ÷ 1 ) = k

Go to step 3.

a. Explain in words what the algorithm is doing.

b. Show that at iteration kâ€”that is. when the value of P(k) Is initially setâ€”

P(1), P(2), ..., P(k) is a random permutation of 1, 2, ..., k.

Hint: Use induction and argue that P k { i 1 , i 2 ... , i j − 1 , k , i j , ... , i k − 2 , i } = P k − 1 { i 1 , i 2 ... , i j − 1 , k , i j , ... , i k − 2 } 1 k = 1 k ! by the induction hypothesis

(a)

Expert Solution

To determine

To find: the explanation that the algorithm is doing.

Explanation of Solution

Given:

Some steps of algorithm are given.

The algorithm starts by initially putting k=1 thus it sets p(1)=1 .

Then, until K=M it increases the value of K by one after each iteration. It generates a random number U and replaces p(k) by p([ku]+1) . Then, it puts p([ku]+1)=k . Then, it goes again to step 3.

This algorithm start by putting p(1)=1 , but it does not exclude this value in next interation the value of p(1) can change in any subsequent iteration. Thus, no position is fixed until the algorithm ends.

Therefore, therequired explanation is shown above.

(b)

Expert Solution

To determine

To prove:that the set p(1), p(2), ....., p(k) which is a random permutation of 1,2,....,k .

Explanation of Solution

Given:

It is given that pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×p{ik} .

As it is given that the condition pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×p{ik} .

It is known that;

p{ik}=1total sample space=1k

Then, the given condition becomes;

pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×1k

Similarly,

pk{i1, i2,......,ik}=1k×1k−1×.....11=1k!

This proves that at iteration k can be defined as p(1), p(2), ....., p(k) which is a random permutation of 1,2,....,k .

Therefore, the required identity has been proved.

Want to see more full solutions like this?

Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!

Answer 4

Textbook Question

Chapter 10, Problem 10.1P

The following algorithm will generate a random permutation of the elements 1,2, ..., n. It is somewhat faster than the one presented in Example 1a, but is such that no position is fixed until the algorithm ends. In this algorithm, P ( i ) can be interpreted as the element in position i.

Step 1. Set k = 1

Step 2. Set P ( 1 ) = 1 .

Step 3. If k = n , stop otherwise, let k = k + 1 .

Step 4. Generate a random number U and let P ( k ) = P ( [ k U ] + 1 ) P ( [ k U ] ÷ 1 ) = k

Go to step 3.

a. Explain in words what the algorithm is doing.

b. Show that at iteration kâ€”that is. when the value of P(k) Is initially setâ€”

P(1), P(2), ..., P(k) is a random permutation of 1, 2, ..., k.

Hint: Use induction and argue that P k { i 1 , i 2 ... , i j − 1 , k , i j , ... , i k − 2 , i } = P k − 1 { i 1 , i 2 ... , i j − 1 , k , i j , ... , i k − 2 } 1 k = 1 k ! by the induction hypothesis

(a)

Expert Solution

To determine

To find: the explanation that the algorithm is doing.

Explanation of Solution

Given:

Some steps of algorithm are given.

The algorithm starts by initially putting k=1 thus it sets p(1)=1 .

Then, until K=M it increases the value of K by one after each iteration. It generates a random number U and replaces p(k) by p([ku]+1) . Then, it puts p([ku]+1)=k . Then, it goes again to step 3.

This algorithm start by putting p(1)=1 , but it does not exclude this value in next interation the value of p(1) can change in any subsequent iteration. Thus, no position is fixed until the algorithm ends.

Therefore, therequired explanation is shown above.

(b)

Expert Solution

To determine

To prove:that the set p(1), p(2), ....., p(k) which is a random permutation of 1,2,....,k .

Explanation of Solution

Given:

It is given that pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×p{ik} .

As it is given that the condition pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×p{ik} .

It is known that;

p{ik}=1total sample space=1k

Then, the given condition becomes;

pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×1k

Similarly,

pk{i1, i2,......,ik}=1k×1k−1×.....11=1k!

This proves that at iteration k can be defined as p(1), p(2), ....., p(k) which is a random permutation of 1,2,....,k .

Therefore, the required identity has been proved.

Want to see more full solutions like this?

Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!

Answer 5

Textbook Question

Answer 6

Textbook Question

Answer 7

(a)

Expert Solution

To determine

To find: the explanation that the algorithm is doing.

Explanation of Solution

Given:

Some steps of algorithm are given.

The algorithm starts by initially putting k=1 thus it sets p(1)=1 .

Then, until K=M it increases the value of K by one after each iteration. It generates a random number U and replaces p(k) by p([ku]+1) . Then, it puts p([ku]+1)=k . Then, it goes again to step 3.

This algorithm start by putting p(1)=1 , but it does not exclude this value in next interation the value of p(1) can change in any subsequent iteration. Thus, no position is fixed until the algorithm ends.

Therefore, therequired explanation is shown above.

(b)

Expert Solution

To determine

To prove:that the set p(1), p(2), ....., p(k) which is a random permutation of 1,2,....,k .

Explanation of Solution

Given:

It is given that pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×p{ik} .

As it is given that the condition pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×p{ik} .

It is known that;

p{ik}=1total sample space=1k

Then, the given condition becomes;

pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×1k

Similarly,

pk{i1, i2,......,ik}=1k×1k−1×.....11=1k!

This proves that at iteration k can be defined as p(1), p(2), ....., p(k) which is a random permutation of 1,2,....,k .

Therefore, the required identity has been proved.

Answer 8

(a)

Expert Solution

To determine

To find: the explanation that the algorithm is doing.

Explanation of Solution

Given:

Some steps of algorithm are given.

The algorithm starts by initially putting k=1 thus it sets p(1)=1 .

Then, until K=M it increases the value of K by one after each iteration. It generates a random number U and replaces p(k) by p([ku]+1) . Then, it puts p([ku]+1)=k . Then, it goes again to step 3.

This algorithm start by putting p(1)=1 , but it does not exclude this value in next interation the value of p(1) can change in any subsequent iteration. Thus, no position is fixed until the algorithm ends.

Therefore, therequired explanation is shown above.

Answer 9

(a)

Expert Solution

Answer 10

(a)

Expert Solution

Answer 11

Expert Solution

Answer 12

To determine

To find: the explanation that the algorithm is doing.

Answer 13

Explanation of Solution

Given:

Some steps of algorithm are given.

The algorithm starts by initially putting k=1 thus it sets p(1)=1 .

Then, until K=M it increases the value of K by one after each iteration. It generates a random number U and replaces p(k) by p([ku]+1) . Then, it puts p([ku]+1)=k . Then, it goes again to step 3.

This algorithm start by putting p(1)=1 , but it does not exclude this value in next interation the value of p(1) can change in any subsequent iteration. Thus, no position is fixed until the algorithm ends.

Therefore, therequired explanation is shown above.

Answer 14

(b)

Expert Solution

To determine

To prove:that the set p(1), p(2), ....., p(k) which is a random permutation of 1,2,....,k .

Explanation of Solution

Given:

It is given that pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×p{ik} .

As it is given that the condition pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×p{ik} .

It is known that;

p{ik}=1total sample space=1k

Then, the given condition becomes;

pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×1k

Similarly,

pk{i1, i2,......,ik}=1k×1k−1×.....11=1k!

This proves that at iteration k can be defined as p(1), p(2), ....., p(k) which is a random permutation of 1,2,....,k .

Therefore, the required identity has been proved.

Answer 15

(b)

Expert Solution

Answer 16

(b)

Expert Solution

Answer 17

Expert Solution

Answer 18

To determine

To prove:that the set p(1), p(2), ....., p(k) which is a random permutation of 1,2,....,k .

Answer 19

Explanation of Solution

Given:

It is given that pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×p{ik} .

As it is given that the condition pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×p{ik} .

It is known that;

p{ik}=1total sample space=1k

Then, the given condition becomes;

pk{i1, i2,......,ik}=pk−1{i1,i2,.....,ik−1}×1k

Similarly,

pk{i1, i2,......,ik}=1k×1k−1×.....11=1k!

This proves that at iteration k can be defined as p(1), p(2), ....., p(k) which is a random permutation of 1,2,....,k .

Therefore, the required identity has been proved.

Answer 20

Ch. 10 - The following algorithm will generate a random...Ch. 10 - Prob. 10.2P Ch. 10 - Give a technique for simulating a random variable...Ch. 10 - Present a method for simulating a random variable...Ch. 10 - Use the inverse transformation method to present...Ch. 10 - Give a method for simulating a random variable...Ch. 10 - Let F be the distribution functionF(x)=xn0x1 a....Ch. 10 - Prob. 10.8P Ch. 10 - Suppose we have a method for simulating random...Ch. 10 - Prob. 10.10P

Videos

Explanation of Solution

Explanation of Solution

Want to see more full solutions like this?

Chapter 10 Solutions

Additional Math Textbook Solutions