What is the "best" way to Generate a Bernoulli Process?

42 views (last 30 days)
A Bernoulli Process is a sequence of iid (independent, identically-distributed) random variables x1,x2,...,xi,..., where the probability mass function of xi is
xi = S(success) with probability p,
xi = F(failure) with probability q,
with p+q = 1.
Depending on the application, (S,F) may be (1,0), (H,T), (true, false), etc.
Here are two obvious ways to generate a (1,0) Bernoulli process in Matlab:
  1. Vectorized Form: bernp1 = rand(n,1) <= p; Process vector bernp1
  2. Component Form: for k = 1:n, bernp2 = rand <= p; Process scalar bernp2; end;
The "best" answer will depend on the application and computer at hand.
If the computer has lots of memory then the vectorized version is the simplest, and may be the fastest.
If "Process vector or scalar" takes a lot of time then the time to generate bernp by either method may be negligible.
If a fixed amount of memory is available for bernp then we must use the component form or a mini-vectorized form.
Using rand to generate 1 random bit seems wasteful, given that rand returns a double precision floating point number which has about 53 random bits. Can we use rand more efficiently?
My interest in the Bernoulli process was sparked by re-reading Feller Volume 1. At the bottom of page 18 Feller says: "In this volume we shall consider only discrete sample spaces". A closer examination shows that Feller derives (nearly) everything in this book from the Bernoulli process.
Derek O'Connor

Answers (4)

Andrew Newell
Andrew Newell on 3 Mar 2011
Interesting question. The number of wasted bits depends on the number of bits you need to define p. If p = 1/sqrt(3), no wasted bits! Any algorithm trying to beat your algorithm 1 would require a lot of special cases, and would be competing with a built-in algorithm.
The Statistics Toolbox uses a variation on your first algorithm.
( edited to expand on answer )
  2 Comments
Derek O'Connor
Derek O'Connor on 4 Mar 2011
Andrew,
I don't understand the first part of your answer.
The value of p would be represented by a double precision f.p. number, i.e., a 64-bit string. This same string is used repeatedly for each rand generated.
Derek O'Connor
Andrew Newell
Andrew Newell on 4 Mar 2011
Each time you generate a new random number, you need to compare it with p, and you don't know in advance how many bits you'll need to compare. It might be all 53.

Sign in to comment.


Walter Roberson
Walter Roberson on 4 Mar 2011
Yes, you can make better use of rand.
If the probability is expressible in lowest terms with a denominator of 2^n, n <= 26. With the 2^n denominator, you take n consecutive bits at a time out of the float representation.
For other probabilities, you use Arithmetic Coding
  1 Comment
Andrew Newell
Andrew Newell on 4 Mar 2011
I don't know what you mean. Float representation of what? And what do you do with the bits?

Sign in to comment.


Bilal Siddiqui
Bilal Siddiqui on 2 Oct 2018
It's simple. A Bernoulli trial produces one of only two outcomes (say 0 or 1). You can use binord. For example p=0.2; n=100; A=binornd(1,p*ones(n,1));
produces an nx1 array of Bernoulli trials which are either 0 or 1 in each outcome. Hope this answers your question.

Gagan Sadhrush
Gagan Sadhrush on 19 Nov 2022
i have to find out number of bernoulli trials untill '101' pattern is obtained ,how do i do this ??

Categories

Find more on Matrices and Arrays in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!