1
$\begingroup$

I need to generate a binary array of size N with K numbers 1 and (n-k) numbers 0 on it,does not matter in which position. The amount of K numbers 1s belongs to an interval Min <= K <= Max , and Max <= N .

Since these values is represented by a binary variable, the probability of array position has 0 is P(x=0) = 0.5 and it has 1 is P(x=1) = 1-P(x=0) = 0.5.

Let's suppose an array size of N=100 must have K numbers 1s on it according 20 <= K <= 30 ,i.e. Min=20 and Max=30.

My first idea to use a probability function to generate the values for this array was developed according to the following considerations, which I'm not sure if it is correct :

(1) for the MIN constraint K>=20, since the probability of 1s is P(x=1)=0.5 and it is required that at least 20 positions been filled with 1s then , at least 20/100 =20% , (Min/N) positions must have 1s, However, for a random binary variable P(X=1) = 0.5 , so how to combine this with the constraint of 20% must be 1 ?

(2) for the MAX constraint K<=30, it means that the (100 - 30) remaining positions must be 0, i.e. 70/100 = 70%, (1 - Max/N) positions must have zero. However, for a random binary variable P(X=0)=0.5, how to combine this with the constraint of 70% must be 0 ?

(3) the interval 20 <= K <= 30 , can be either 0 or 1, i.e. (30 - 10)/100= 20% , (Max - Min)/N positions can be filled 0 or 1.

After found the probability of 1s "prob_one", I'd like to write my code using a "rand" function (which returns a random number between 0 and 1) to fill each position of the binary array like this :

"if rand <= prob_one then myarray[position] := 1 else myarray[position] = 0" .

My Questions :

Q1) Do considerations (1) , (2) and (3) make sense ?

Q2) Is there any probability distribution function that can solve this problem and give a direct answer like P(X=1) = prob_one and P(X=0)= prob_zero ?

I appreciate solutions, explanations, examples and material references on how to solve this.

$\endgroup$
  • $\begingroup$ Is there anything wrong with choosing p=(lower limit+upper limit)/2, in this case p=25%, with rethrows if the number fails? $\endgroup$ – JMP May 2 at 19:42
  • $\begingroup$ This array must have at least lower limit of 1s . So I think there could be an option to have (L+U)/2 number 1s. But I'm searching first the probabilistic formula. Thanks or now ! $\endgroup$ – JRG May 2 at 19:52
0
$\begingroup$

The number of arrays which contains exactly $k$ times the digit $1$ is given by:

$$n(k) = {N \choose k} = \frac{N!}{k!(N-k)!},$$

where $a!$ is the factorial of the number $a$.

If you want to find the number of arrays with $20 \leq k \leq 30,$ then you must evaluate:

$$\sum_{k=20}^{30} n(k) = ...$$

In order to arrive to the same result using a probabilistic approach, you should first notice that the number of $N$-arrays composed by "0" and "1" digits only is $2^N$. Moreover, the probability that one of these array contains exactly $k$ digits $1$ is given by the binomial distribution:

$$P(k) = {N \choose k}p^k (1-p)^{N-k},$$

where $p = \frac{1}{2}$ is the probability of having a $1$. Therefore, the number of arrays which contains exactly $k$ times the digit $1$ is given by: $$n(k) = 2^N \cdot P(k) = 2^N {N \choose k}p^k (1-p)^{N-k} = 2^N {N \choose k} \left(\frac{1}{2}\right)^k \left(\frac{1}{2}\right)^{N-k} = {N \choose k} 2^{N - k - N + k} = {N \choose k},$$

which is exactly the same result presented at the beginning of this answer.

If you want to find the probability to extract one array with $20 \leq k \leq 30$, then you should evaluate:

$$\sum_{k=20}^{30} P(k) = \frac{1}{2^N}\sum_{k=20}^{30}n(k) = ...$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ tks for the prompt reply. I'm not sure if I clearly described my point or if you didn't got he point> I'm NOT looking for the the number of arrays which has 20<=K<= 30 numbers of 1s whithin , as your answer proposed. I'm interested in a single array only that has 20<=K<=30 number 1s on it and I want to find the probability of such K . In other words given a single array of 100 positions, I want fill K positions of this single array with number 1, considering Lower <= K <= Upper . What is the the probability of having K number 1s in one single array of size N ? $\endgroup$ – JRG May 2 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.