Thread Subject: Growing elements in a vector

Dear All,

I have a tricky little issue I need to deal with:

I have a vector which goes something like this

vector = [1 2 3 1 2 3 2 3 1 3 2 1 2 3 1 3 2 1 2 3 1 1 3 1 2 1 3 1 2 3
1...];

Please note that the above vector will only have unique elements as
neighbours and hence no repitition of elements.

Now what i want is to cleverly with less computational burden,
consider every element in the vector one by one and replicate the
element as many times as it takes to pass a comparison test against a
randomly drawn variable.

For example, for every unique element 1, 2 and 3 I have a number
between 0 and 1 i.e 0.2, 0.3 and 0.5 respectively.

So how this would work is

1) Consider Vector(1), the element is 1.
2) Draw a Random number. Compare it to 0.2. If less than 0.2, append a
1 after the first 1, else move to next unique element. Continue
appending 1's till random value generated is higher than 0.2
3) If in element 2, compare to 0.3 and if in element 3 compare to 0.5.

finally my output vector should look something like this:

outvector = [1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 1 1 1 1 3 3 3 3 3.......];


Trying this with for loops for large vectors seems to take a toll on
the speed of computation and I would prefer a quick vector based
solution.


I have been spending a lot of time on this to compute efficiently and
will be really grateful for a solution for this with example code.

Many thanks,

Adshak

On Oct 21, 2:10 pm, Adshak <adshaikh.hip...@googlemail.com> wrote:
> Dear All,
>
> I have a tricky little issue I need to deal with:
>
> I have a vector which goes something like this
>
> vector = [1 2 3 1 2 3 2 3 1 3 2 1 2 3 1 3 2 1 2 3 1 1 3 1 2 1 3 1 2 3
> 1...];
>
> Please note that the above vector will only have unique elements as
> neighbours and hence no repitition of elements.
>
> Now what i want is to cleverly with less computational burden,
> consider every element in the vector one by one and replicate the
> element as many times as it takes to pass a comparison test against a
> randomly drawn variable.
>
> For example, for every unique element 1, 2 and 3 I have a number
> between 0 and 1 i.e 0.2, 0.3 and 0.5 respectively.
>
> So how this would work is
>
> 1) Consider Vector(1), the element is 1.
> 2) Draw a Random number. Compare it to 0.2. If less than 0.2, append a
> 1 after the first 1, else move to next unique element. Continue
> appending 1's till random value generated is higher than 0.2
> 3) If in element 2, compare to 0.3 and if in element 3 compare to 0.5.
>
> finally my output vector should look something like this:
>
> outvector = [1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 1 1 1 1 1 1 1 1
> 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 1 1 1 1 3 3 3 3 3.......];
>
> Trying this with for loops for large vectors seems to take a toll on
> the speed of computation and I would prefer a quick vector based
> solution.
>
> I have been spending a lot of time on this to compute efficiently and
> will be really grateful for a solution for this with example code.
>
> Many thanks,
>
> Adshak

See Luc Devroye, Non-Uniform Random Variate Generation, p 87, example
2.2, The geometric distribution: Let the length of a run that begins
with i be ceiling(log(u)/log(1-p_i)), where u is a Uniform(0,1)
random number and p_i is the theoretical marginal probability of
observing i (e.g. in your example, p_1 = .2 , p_2 = .3, p_3 = .5).

On Oct 21, 2:10 pm, Adshak <adshaikh.hip...@googlemail.com> wrote:
> Dear All,
>
> I have a tricky little issue I need to deal with:
>
> I have a vector which goes something like this
>
> vector = [1 2 3 1 2 3 2 3 1 3 2 1 2 3 1 3 2 1 2 3 1 1 3 1 2 1 3 1 2 3
> 1...];
>
> Please note that the above vector will only have unique elements as
> neighbours and hence no repitition of elements.
>
> Now what i want is to cleverly with less computational burden,
> consider every element in the vector one by one and replicate the
> element as many times as it takes to pass a comparison test against a
> randomly drawn variable.
>
> For example, for every unique element 1, 2 and 3 I have a number
> between 0 and 1 i.e 0.2, 0.3 and 0.5 respectively.
>
> So how this would work is
>
> 1) Consider Vector(1), the element is 1.
> 2) Draw a Random number. Compare it to 0.2. If less than 0.2, append a
> 1 after the first 1, else move to next unique element. Continue
> appending 1's till random value generated is higher than 0.2
> 3) If in element 2, compare to 0.3 and if in element 3 compare to 0.5.
>
> finally my output vector should look something like this:
>
> outvector = [1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 1 1 1 1 1 1 1 1
> 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 1 1 1 1 3 3 3 3 3.......];
>
> Trying this with for loops for large vectors seems to take a toll on
> the speed of computation and I would prefer a quick vector based
> solution.
>
> I have been spending a lot of time on this to compute efficiently and
> will be really grateful for a solution for this with example code.
>
> Many thanks,
>
> Adshak

Correction: Your p is Devroye's 1-p, so the length of a run that
begins with i should be ceiling(log(u)/log(p_i)).

Adshak <adshaikh.hipnet@googlemail.com> wrote in message <6fbe2615-a1f9-46ad-93d4-60500f097e38@q35g2000hsg.googlegroups.com>...
> Dear All,
>
> I have a tricky little issue I need to deal with:
>
> I have a vector which goes something like this
>
> vector = [1 2 3 1 2 3 2 3 1 3 2 1 2 3 1 3 2 1 2 3 1 1 3 1 2 1 3 1 2 3
> 1...];
>
> Please note that the above vector will only have unique elements as
> neighbours and hence no repitition of elements.
>
> Now what i want is to cleverly with less computational burden,
> consider every element in the vector one by one and replicate the
> element as many times as it takes to pass a comparison test against a
> randomly drawn variable.
>
> For example, for every unique element 1, 2 and 3 I have a number
> between 0 and 1 i.e 0.2, 0.3 and 0.5 respectively.
>
> So how this would work is
>
> 1) Consider Vector(1), the element is 1.
> 2) Draw a Random number. Compare it to 0.2. If less than 0.2, append a
> 1 after the first 1, else move to next unique element. Continue
> appending 1's till random value generated is higher than 0.2
> 3) If in element 2, compare to 0.3 and if in element 3 compare to 0.5.
>
> finally my output vector should look something like this:
>
> outvector = [1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 1 1 1 1 1 1 1 1
> 1 2 2 2 2 2 2 3 3 3 3 3 3 3 3 1 1 1 1 3 3 3 3 3.......];
>
>
> Trying this with for loops for large vectors seems to take a toll on
> the speed of computation and I would prefer a quick vector based
> solution.
>
>
> I have been spending a lot of time on this to compute efficiently and
> will be really grateful for a solution for this with example code.
>
> Many thanks,
>
> Adshak
>
>

I am not sure if I understand your problem correctly. Let me try to rephrase. You have a vector:

V = [2 3 1 2]

with associated changes for the values 1, 2 and 3:

p = [.2 .3 .5] ;

and you want to expand each value in V an individual number of times, based on p. In code, it might look like this:

W = [] ;
for i=1:numel(V),
   while rand < p(V(i))
       W = [W V(i)] ;
   end
end

so you might end up with

W = [], W = 1, W = [2 2 3 3 1], or W = [2 2 2 2 3 3 1 1 1 1 2]

Am I correct?

Indeed, for long vectors V this might indeed take some time, but if I am correct, improvements can be made.

Jos

On Oct 22, 7:50=A0am, "Jos " <DEL...@jasenDEL.nl> wrote:
> Adshak <adshaikh.hip...@googlemail.com> wrote in message <6fbe2615-a1f9-4=
6ad-93d4-60500f097...@q35g2000hsg.googlegroups.com>...
> > Dear All,
>
> > I have a tricky little issue I need to deal with:
>
> > I have a vector which goes something like this
>
> > vector =3D [1 2 3 1 2 3 2 3 1 3 2 1 2 3 1 3 2 1 2 3 1 1 3 1 2 1 3 1 2 3
> > 1...];
>
> > Please note that the above vector will only have unique elements as
> > neighbours and hence no repitition of elements.
>
> > Now what i want is to cleverly with less computational burden,
> > consider every element in the vector one by one and replicate the
> > element as many times as it takes to pass a comparison test against a
> > randomly drawn variable.
>
> > For example, for every unique element 1, 2 and 3 I have a number
> > between 0 and 1 i.e 0.2, 0.3 and 0.5 respectively.
>
> > So how this would work is
>
> > 1) Consider Vector(1), the element is 1.
> > 2) Draw a Random number. Compare it to 0.2. If less than 0.2, append a
> > 1 after the first 1, else move to next unique element. Continue
> > appending 1's till random value generated is higher than 0.2
> > 3) If in element 2, compare to 0.3 and if in element 3 compare to 0.5.
>
> > finally my output vector should look something like this:
>
> > outvector =3D [1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 1 1 1 1 1 1 1 1
> > 1 =A02 2 2 2 2 2 3 3 3 3 3 3 3 3 1 1 1 1 3 3 3 3 3.......];
>
> > Trying this with for loops for large vectors seems to take a toll on
> > the speed of computation and I would prefer a quick vector based
> > solution.
>
> > I have been spending a lot of time on this to compute efficiently and
> > will be really grateful for a solution for this with example code.
>
> > Many thanks,
>
> > Adshak
>
> I am not sure if I understand your problem correctly. Let me try to rephr=
ase. You have a vector:
>
> V =3D [2 3 1 2]
>
> with associated changes for the values 1, 2 and 3:
>
> p =3D [.2 .3 .5] ;
>
> and you want to expand each value in V an individual number of times, bas=
ed on p. In code, it might look like this:
>
> W =3D [] ;
> for i=3D1:numel(V),
> =A0 =A0while rand < p(V(i))
> =A0 =A0 =A0 =A0W =3D [W V(i)] ;
> =A0 =A0end
> end
>
> so you might end up with
>
> W =3D [], W =3D 1, W =3D [2 2 3 3 1], or W =3D [2 2 2 2 3 3 1 1 1 1 2]
>
> Am I correct?
>
> Indeed, for long vectors V this might indeed take some time, but if I am =
correct, improvements can be made.
>
> Jos- Hide quoted text -
>
> - Show quoted text -

Dear Ray,

I am sorry I do not have access to the book you just mentioned, so it
is difficult to understand your solution.

Dear Jos,

No, the only solution possible is the last possibility of W as in, if
W were the output vector, the elements in V need to exist as it is but
need to be replicated by the side of the existence of the original
element. The least possibility is that the output vector should be the
original input vector itself.

I am thinking that repmat might be a part of the solution to this,
where you decide the repeating number by the criteria mentioned above
and accordingly repeat the number of elements. any suggestions?



I was also thinking there might be a way I may want to avoid the
appending of arrays, by running time indices parallel to the original
vector.

Say my vector is as above in my original post i.e:


 vector =3D [1 2 3 1 2 3 2 3 1 3 2 1 2 3 1 3 2 1 2 3 1 1 3 1 2 1 3 1 2 3
1];

I can then have:

dt =3D 0:0.001:((length(vector)-1)/1000);


So now the number of times it takes for element 1 to satisfy the
random element criteria mentioned in my original post is multiplied
with the relevant time index in dt and so on for the remaining
elements. But I am still left with the problem of calculating the
number of times it loops for each element before it moves to the next
unique element of the vector.

Please kindly help me!!!! :(

adshak

Adshak <adshaikh.hipnet@googlemail.com> wrote in message ...
> In code, it might look like this:
> >
> > W =3D [] ;
> > for i=3D1:numel(V),
> > =A0 =A0while rand < p(V(i))
> > =A0 =A0 =A0 =A0W =3D [W V(i)] ;
> > =A0 =A0end
> > end
> >
> > so you might end up with
> >
> > W =3D [], W =3D 1, W =3D [2 2 3 3 1], or W =3D [2 2 2 2 3 3 1 1 1 1 2]
> >
> > Am I correct?
...
> No, the only solution possible is the last possibility of W as in, if
> W were the output vector, the elements in V need to exist as it is but
> need to be replicated by the side of the existence of the original
> element. The least possibility is that the output vector should be the
> original input vector itself.

So this would do then:

V = [2 3 1 2] ;
p = [0.2 0.3 0.5] ;
W = [] ;
for i=1:numel(V),
  W = [W V(i)] ;
  while rand < p(V(i))
    W = [W V(i)] ;
  end
end
W

So at least all elements of V are present in W.

Jos

Adshak <adshaikh.hipnet@googlemail.com> wrote in message <fb411cc8-4e3e-4940-8e3f-

...
translating your problem:

you have vector V with N elements, taken from 1:J. The element in position k "V(k)"is to be replicated M(k) times. M(k) depends on the value p(V(k)). So the problem becomes: How to find M?

Once you have M, the result can be obtained quite easily.

V = [3 2 1 2]
% ...
% find M
% ...
M = [3 4 2 1]
c = cumsum(M)
ind = zeros(1,c(end))
ind([1 c(1:end-1)+1]) = 1
W = V(cumsum(ind))

Jos

Adshak <adshaikh.hipnet@googlemail.com> wrote in message
> Dear Ray,
> I am sorry I do not have access to the book you just mentioned,
> so it is difficult to understand your solution.
> .......
> adshak
------------
  Adshak, a vectorized and undoubtedly much faster method of generating the number of repetitions for each element in your original vector (which Jos has called M) is implicit in the formula given in Ray Coopman's second article in this thread. You don't need to access the reference he has given there.

  Instead of generating an indefinitely long series of random numbers for each element of the vector, just use a single call on the 'rand' function. Let p be the "comparison test" number (e.g. .2, .3, & .5) and let u be the value of a 'rand' call: u = rand. Then Ray is telling you to find

 m = ceil(log(u)/log(p))

and use this as the number of repetitions for the corresponding vector element (1, 2, 3, etc.) all in a single step.

  The reasoning behind this is that if

 m = ceil(log(u)/log(p))

then

 m-1 < log(u)/log(p) <= m

and multiplying by the negative log(p) gives

 (m-1)*log(p) > log(u) >= m*log(p)

which by taking the exponential of all three quantities yields

 p^(m-1) > u >= p^m

The probability of this is thus

 p^(m-1)-p^m = p^(m-1)*(1-p)

which is the same as the probability of obtaining m-1 comparisons which are less than p followed by a final comparison that is greater or equal to p, and thus gives the desired number of repetitions for the corresponding vector element.

  You can of course make a vector equation out of the above 'ceil' expression which would give the vector M all in one vectorized line:

 M = ceil(log(rand(n,1)./log(P));

where P is the vector of comparison values and n is its length.

Roger Stafford