Aufgaben:Exercise 2.7: C Programs "z1" and "z2"

• Return to book

C programs for generating
discrete random variables

The two C programs given here are suitable for generating discrete random variables:

• The function  $z1$  generates an  $M$–level random variable with the value set  $\{0, 1$, ... , $M-1\}$.  The associated probabilities are passed in the array  $\text{p_array}$  with property  "Float"  The function  $\text{random()}$  returns equally distributed float–random variables  between  $0$  and  $1$.

• A second function  $z2$  (source code see below)  returns a special probability distribution specified by the two parameters  $I$  and  $p$.  This is done using the function  $z1$.

Hints:

• The exercise belongs to the chapter  Generation of Discrete Random Variables.
• In particular, reference is made to the page  Generation of multilevel random variables.

Questions

1

It is valid:  $M=4$,    $\text{p_array} = \big[0.2, \ 0.3, \ 0.4, \ 0.1 \big]$.
What result does the function  $z1$  return if the random function returns the  value  $x = 0.75$  ?

$z1 \ = \ $

2

Which of the following statements are true regarding  $z1$ ?

	You could omit the assignment  $\text{x = random()}$  in line 5 and compare directly with  $\text{random()}$  in line 8.
	If all probabilities passed to the function are equal,  there would be faster program realizations than  $z1$.
	The return value  $\text{random() = 0.2}$  leads to the result  $z1= 1$.

3

Which of the following statements are true regarding  $z2$ ?

	The program generates a  "binomially distributed random variable".
	The program generates a  "Poisson distributed random variable".
	With  $I = 4$  the values  $0, \ 1, \ 2, \ 3, \ 4$  are possible for  $z2$.
	The inclusion of the mathematical library  "math.h"  is required because in  $z2$  the function  "pow"  ("exponentiate")  is used in  $z2$.

4

What value has  $\text{p_array[2]}$  when the function  $z2$  is called with the parameters   $I = 4$  and  $p = 0.25$?

$\text{p_array[2]} \ = \ $

Solution

Solution

(1)  After the first iteration of the loop  $(m = 0)$  the variable  $\text{sum = 0.2}$, at the next iteration  $(m = 1)$  holds  $\text{sum = 0.2 + 0.3 = 0.5}$.

• In both cases, therefore, the variable  $\text{sum} < x = 0.75$. 
• Only when  $m = 2$  is the return (bin hier nicht sicher) condition satisfied:   $0.9 > x$.  Thus  $\underline{z1 = 2}$.

(2)  The correct solutions are solutions 2 and 3:

• Were we to dispense with the auxiliary variable  $x$  and write in line 8 instead  $\text{sum > random()}$  a new random value would be generated on each iteration of the loop, and  $z1$  would then not have the desired properties.
• $z1$  works according to the diagram on the page "Generation of multistage random variables" in the theory section.  There you find a much faster implementation for the case of equal probabilities  $(1/M)$.
• In the first run  $(m = 0)$  in this case the return condition is not satisfied due to the less/equal–query;  the output value is actually  $z1 = 1$.

(3)  The correct solutions are 1, 3, and 4:

• It results in a binomially distributed random variable, with the set of values  $\{0, 1, 2, 3, 4\}$.
• For the calculation of the probability ${\rm Pr}(z2 = 0) = (1 -p)^{I}$  one needs the mathematical library.
• But exponentiation could also be realized by  $I$–fold multiplication.

(4)  Because of line 6, the field element  $\text{p_array[0]}$  before the program loop  $(i = 0)$  contains the value  $(1 -p)^{I}$. 

• In the first iteration  $(i = 1)$  the following value is entered:

$$\text{p_array[1]}=\frac{ p\cdot I}{ 1- p}\cdot\text{p_array[0]}= I\cdot p\cdot(1- p)^{ I- 1}={\rm Pr}(z2= 1) .$$

• In the second iteration  $(i = 2)$  the probability for the result "$z2=2$" is calculated:

$$\text{p_array[2]}=\frac{p\cdot (I- 1)}{ 2\cdot ( 1- p)}\cdot\text{p_array[1]}= \left({ I \atop { 2}}\right)\cdot p^{\rm 2}\cdot( 1- p)^{\rm 2}={\rm Pr}( z2 = 2) .$$

• For  $I= 4$  and  $p = 0.25$  we get the following numerical value   ⇒   "$4$  over  $2$"   $=6$:

$$\text{p_array[2]}={\rm Pr}( z 2=2)=6\cdot\frac{1}{16}\cdot\frac{9}{16} \hspace{0.15cm}\underline{=0.211}.$$