SERVING THE QUANTITATIVE FINANCE COMMUNITY

  • 1
  • 2
  • 3
  • 4
  • 5
  • 7
 
User avatar
maratikus
Topic Author
Posts: 58
Joined: January 2nd, 2008, 7:38 pm

random allocation

October 7th, 2009, 5:54 pm

I would like to generate a random allocation vector x_1, ..., x_n: x_1+...+x_n=1 and 0<=x_i<=c for each i, c is a parameter. does anyone have an idea of how that can be done?
 
User avatar
crmorcom
Posts: 452
Joined: April 9th, 2008, 4:09 pm

random allocation

October 7th, 2009, 6:05 pm

Yes: draw x_1, ...x_{n-1} from U[0,c] and keep drawing until you get x_n = 1-\sum_1^{n-1} x_i <=c.I have no idea if this is going to give you the probability measure that you want, but it will work.
 
User avatar
maratikus
Topic Author
Posts: 58
Joined: January 2nd, 2008, 7:38 pm

random allocation

October 7th, 2009, 7:26 pm

I would like random allocations to be uniformly distributed.
 
User avatar
MatthewM
Posts: 416
Joined: December 17th, 2007, 12:49 pm

random allocation

October 7th, 2009, 8:18 pm

You have to be a little more specific than that.
Last edited by MatthewM on October 6th, 2009, 10:00 pm, edited 1 time in total.
 
User avatar
MikeLo
Posts: 19
Joined: August 8th, 2006, 3:08 pm

random allocation

October 7th, 2009, 9:43 pm

How about n uniform U(0,c) ... add them up ... rescale so total is 1 and redo process if any of them is now greater than c.
 
User avatar
MatthewM
Posts: 416
Joined: December 17th, 2007, 12:49 pm

random allocation

October 7th, 2009, 10:55 pm

The resulting distribution would be highly non-uniform in any of the important senses I can think of.
 
User avatar
alexrem
Posts: 12
Joined: April 3rd, 2009, 4:57 pm

random allocation

October 7th, 2009, 11:01 pm

Maybe use recursion? Randomly generate x_n in [0, c], subtract it from 1, (if c is bigger than 1 you just take c=1), and then you need x_1+x_2+...+x_n-1 = (1-x_n) = a which is fixed. So now you scale down 1 to a so now you are generating randomly x_1+x_2+...+x_(n-1) = a with x_i in [0, c] which is same as generating y_1+y_2+...+y_(n-1)= 1 with y_i in [0, c*(1/a)], so generate those n-1 values and multiply each by a (i.e. x_i = y_i * a) to get the values for x_1, x_2,...,x_(n-1).I hope this works.
 
User avatar
wileysw
Posts: 593
Joined: December 9th, 2006, 6:13 pm

random allocation

October 7th, 2009, 11:27 pm

sorry i'm slow at understanding the exact question.is "n" a fixed a number? and is "c" given or something one could play with? and what does it mean by "random allocations to be uniformly distributed"? thanks.
 
User avatar
maratikus
Topic Author
Posts: 58
Joined: January 2nd, 2008, 7:38 pm

random allocation

October 8th, 2009, 11:41 am

QuoteOriginally posted by: alexremMaybe use recursion? Randomly generate x_n in [0, c], subtract it from 1, (if c is bigger than 1 you just take c=1), and then you need x_1+x_2+...+x_n-1 = (1-x_n) = a which is fixed. So now you scale down 1 to a so now you are generating randomly x_1+x_2+...+x_(n-1) = a with x_i in [0, c] which is same as generating y_1+y_2+...+y_(n-1)= 1 with y_i in [0, c*(1/a)], so generate those n-1 values and multiply each by a (i.e. x_i = y_i * a) to get the values for x_1, x_2,...,x_(n-1).I hope this works.That would be biased. On average x1 will get more weight than x_n.
 
User avatar
maratikus
Topic Author
Posts: 58
Joined: January 2nd, 2008, 7:38 pm

random allocation

October 8th, 2009, 11:43 am

QuoteOriginally posted by: wileyswsorry i'm slow at understanding the exact question.is "n" a fixed a number? and is "c" given or something one could play with? and what does it mean by "random allocations to be uniformly distributed"? thanks.let's fix n = 20, c =10%. Generate uniform (x_1, ..., x_20): x_1+...+x_20=1 and each x_i is between 0 and 10%.
 
User avatar
maratikus
Topic Author
Posts: 58
Joined: January 2nd, 2008, 7:38 pm

random allocation

October 8th, 2009, 11:46 am

QuoteOriginally posted by: MikeLoHow about n uniform U(0,c) ... add them up ... rescale so total is 1 and redo process if any of them is now greater than c.if n is high enough, the highest achievable allocation will be below c. on average x1+..+xn = c*n/2. then c/(c*n/2))=2/n , if n = 20, your algorithm won't generate x_i that is higher than 4% (roughly). If I choose c = 10%, the algorithm wouldn't accomplish my goal.
 
User avatar
crmorcom
Posts: 452
Joined: April 9th, 2008, 4:09 pm

random allocation

October 8th, 2009, 1:02 pm

You can sample uniformly from a unit simplex (which is what you have without the c restriction): this from Wikipedia.- Sample y_i from unit exponential- S = \sum y_i- x_i = y_i/S{x_i} is now uniform on {x_i : \sum x_i =1}If you keep sampling until you satisfy the x_i<=c restriction, I think this will be what you want.
 
User avatar
zerdna
Posts: 3856
Joined: July 14th, 2002, 3:00 am

random allocation

October 8th, 2009, 3:16 pm

uniform distribution is characterized by two parameters, its mean and its range. You can achieve what you want if you are allowed to choose both parameters. Generate n numbers x(i) from U(0,1), divide them by the r=max(X)/c , then subtract from each of new numbers the difference a=(1-sum(x(i))/r))/n, or something like that. The random numbers are now from U(-a, 1/r) and they satisfy your conditions. Assuming that you are doing some exercise related to portfolio weights, this is doable if both short and longs are allowed. If you cannot modify the mid of your distribution, i doubt that what you are asking is possible to do.
Last edited by zerdna on October 7th, 2009, 10:00 pm, edited 1 time in total.
 
User avatar
wileysw
Posts: 593
Joined: December 9th, 2006, 6:13 pm

random allocation

October 8th, 2009, 11:02 pm

QuoteOriginally posted by: maratikuslet's fix n = 20, c =10%. Generate uniform (x_1, ..., x_20): x_1+...+x_20=1 and each x_i is between 0 and 10%.thx. but one more question, if i think (x1, ..., xn) as coordinates, could you further clarify whether the p.d.f. of each coordinate is U(0,c) (when marginalized over other x's), or the point determined by the vector (x1, ..., xn) is uniform within the polytope, which is determined by the intersection of the hyperplane x1+...+xn=1 and the hypercube with side length of c?if the latter case, as crmorcom said, you can use independent exponential variables plus the rejection method to satisfy the [0,c] bound;(if c=1, then the polytope is just unit simplex, and no need for rejection)----- ----- this part is WRONG----- -----another more efficient way (w/o rejection but requires sorting) is to use order statistics. for example, if n=3, the polytope in general is a hexagon (except when c=0.5 or 1, and no solution for c<0.5). denote its vertices as v1,...,v6 (see them as vectors) with coordinates: (0,c,1-c) and the permutations. now generate five U(0,1) and sort them as 0<y1<...<y5<1, get the six spacings between them: z1=y1-0, z2=y2-y1, ..., y6=1-y5. then the vector (x1,x2,x3)=y1*v1+...+y6*v6 is what you want.----- ----- ----- ----- -----the former case is much more complicated. back to the simple n=3 case, the question basically asks a way to generate a density distribution on a hexagon so that the projected density to each direction is uniform. seems to me it's possible - will post more if i got any progress.QuoteOriginally posted by: zerdnaGenerate n numbers x(i) from U(0,1), divide them by the r=max(X)/c , then subtract from each of new numbers the difference a=(1-sum(x(i))/r))/n, or something like that. The random numbers are now from U(-a, 1/r)...zerdna, would you mind explaining why the above process would generate uniform r.v.s? it's not clear to me why it would.
Last edited by wileysw on October 11th, 2009, 10:00 pm, edited 1 time in total.
 
User avatar
MatthewM
Posts: 416
Joined: December 17th, 2007, 12:49 pm

random allocation

October 9th, 2009, 2:15 am

Quotewhether the p.d.f. of each coordinate is U(0,c) (when marginalized over other x's)As far as I can see, this would be impossible unless we had the relationship n*c = 2
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On