由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Quant版 - 来一道题 (转载)
相关主题
Ordering a sequence (2) (转载)对EURODOLLAR futures 的convexity不理解。。。
[合集] brainteaser弱问一道面试题
CTC interview 2nd round phone interview如何hedge negative convexity
面经:Why this trading strategy doesnot workGS interview question
问大家一道数学题(probability)【Brainteaser】Interview Questions
请教一个老题implied vol和strikeMurex interview questions
请教一个简单问题: call optionCTC interview 1st round phone interview
如何证明euro. call opotion是convex的?我想找人一起写code
相关话题的讨论汇总
话题: so话题: problem话题: let话题: distinct话题: mapping
进入Quant版参与讨论
1 (共1页)
D**u
发帖数: 204
1
【 以下文字转载自 Mathematics 讨论区 】
发信人: DuGu (火工头陀), 信区: Mathematics
标 题: 来一道题
发信站: BBS 未名空间站 (Thu Oct 22 11:18:45 2009, 美东)
Let {x_1,...,x_n} be n distinct positive real numbers;
{y_1,...,y_n} be n distinct positive real numbers;
and x_i*x_j is not equal to y_k*y_l for any i,j,k,l.
Question:
(1) you can reorder x_i to z_1,...,z_n, such that
(z_i*_z_j - y_i*y_j)(z_i-z_j)(y_i-y_j) > 0 for any distinct i and j.
(2) Is the reordering in (1) unique
a**m
发帖数: 102
2
Don't I understand your problem correctly? I think there is an easy counter
example when n=2...

【在 D**u 的大作中提到】
: 【 以下文字转载自 Mathematics 讨论区 】
: 发信人: DuGu (火工头陀), 信区: Mathematics
: 标 题: 来一道题
: 发信站: BBS 未名空间站 (Thu Oct 22 11:18:45 2009, 美东)
: Let {x_1,...,x_n} be n distinct positive real numbers;
: {y_1,...,y_n} be n distinct positive real numbers;
: and x_i*x_j is not equal to y_k*y_l for any i,j,k,l.
: Question:
: (1) you can reorder x_i to z_1,...,z_n, such that
: (z_i*_z_j - y_i*y_j)(z_i-z_j)(y_i-y_j) > 0 for any distinct i and j.

p*****k
发帖数: 318
3
attm, it's (z_i-z_j), not (z_i-y_i). i don't see a counter example for n=2.
D**u
发帖数: 204
4
z_1,...z_n is a reordering of x_1,...x_n.
Namely there is a permutation f, such that
z_i = x_f(i).

counter

【在 a**m 的大作中提到】
: Don't I understand your problem correctly? I think there is an easy counter
: example when n=2...

b***e
发帖数: 1419
5
1. By a divide and conquer construction:
* Without losing generality, assume X is sorted ascendingly and Y is sorted
descendingly.
* Find i, such that x_{i-1} * x_n < y_i * y_{i-1} < x_i * x_n
* let z_i = x_n
* Solve the following two sub-problems:
- X = {x_1, ..., x_{i-1}}, Y = {y_1, ..., y_{i-1}}
- X = {x_{i+1}, ..., x_n}, Y = {y_{i+1}, ..., y_n}
2. I didn't prove it in details, but my impression is the division is
unique, as a result, the construction is unique.
D**u
发帖数: 204
6
I think in the 2nd sub_problem, you mean
"-X = {x_{i}, ..., x_{n-1}}, Y = {y_{i+1}, ..., y_n}"
It is not obvious to me that this construction will guaranty
that for any ki,
z_k*z_m < y_k*y_m.

sorted

【在 b***e 的大作中提到】
: 1. By a divide and conquer construction:
: * Without losing generality, assume X is sorted ascendingly and Y is sorted
: descendingly.
: * Find i, such that x_{i-1} * x_n < y_i * y_{i-1} < x_i * x_n
: * let z_i = x_n
: * Solve the following two sub-problems:
: - X = {x_1, ..., x_{i-1}}, Y = {y_1, ..., y_{i-1}}
: - X = {x_{i+1}, ..., x_n}, Y = {y_{i+1}, ..., y_n}
: 2. I didn't prove it in details, but my impression is the division is
: unique, as a result, the construction is unique.

p*****k
发帖数: 318
7
i guess it's induction then, instead of "divide and conquer". you throw away x_n and y_i, and end up with the same problem but n-1 numbers in each set.
b***e
发帖数: 1419
8
Essentially, I am applying the process recursively like psacnik
suggested, for the smaller problem of size n-1 . But it occurs that after
the division by putting x_n to z_i, nothing to the left of z_i could ever
cross the ith position (to z_i's right) anymore. So doing {z_1, ...,
z_{i-1}} is equivalent to doing {z_1, ..., z_{i-1}, z_{i+1}, ..., z_n}.

【在 D**u 的大作中提到】
: I think in the 2nd sub_problem, you mean
: "-X = {x_{i}, ..., x_{n-1}}, Y = {y_{i+1}, ..., y_n}"
: It is not obvious to me that this construction will guaranty
: that for any ki,
: z_k*z_m < y_k*y_m.
:
: sorted

D**u
发帖数: 204
9
If you do {x_1, ... x_{i-1}} for {z_1, ..., z_{i-1}}, then
(z_k - z_m)<0 for any k (z_k*z_m - y_k*z_m)<0 for k (z_k*z_m - y_k*z_m)*((z_k - z_m)*(y_k -y_m) > 0.

【在 b***e 的大作中提到】
: Essentially, I am applying the process recursively like psacnik
: suggested, for the smaller problem of size n-1 . But it occurs that after
: the division by putting x_n to z_i, nothing to the left of z_i could ever
: cross the ith position (to z_i's right) anymore. So doing {z_1, ...,
: z_{i-1}} is equivalent to doing {z_1, ..., z_{i-1}, z_{i+1}, ..., z_n}.

b***e
发帖数: 1419
10
Here is what I mean:
* First I find the mapping for the largest x_n and map it to z_i. So
my new sequence Z is:
- z_k = x_k for k in [0..i-1]
- z_i = x_n
- z_k = x_{k-1} for k in [i+1..n]
* Now I can ignore x_n and y_i and reapply the algorithm on:
- Z' = {z_k where k != i}. Note that Z' is sorted in ascending
order.
- Y' = {y_k where y != i}
where the problem size is 1 shorter than the original problem.
Semantically, in this second pass, I am trying to locate the second
相关主题
请教一个老题implied vol和strike对EURODOLLAR futures 的convexity不理解。。。
请教一个简单问题: call option弱问一道面试题
如何证明euro. call opotion是convex的?如何hedge negative convexity
进入Quant版参与讨论
p*****k
发帖数: 318
11
blaze, sorry about backpedaling, but let's consider:
x={5.1, 7.1, 8} and y={7, 6, 5},
if i understand your approach correctly, one should start by putting "8" at position 2, because 5.1*8 < 7*6 < 7.1*8. but then easy to verify that either {5.1, 8, 7.1} or {7.1, 8, 5.1} does not work... maybe you had something else in mind?
i also found that the ordering is not unique. consider:
{7.1, 6.1, 5.1} with {7, 6, 5},
which is good. but another ordering:
{5.1, 7.1, 6.1} with {7, 6, 5}
also works...
D**u
发帖数: 204
12
right, the ordering is not unique. So only the existense part is left.

at position 2, because 5.1*8 < 7*6 < 7.1*8. but then easy to verify that
either {5.1, 8, 7.1} or {7.1, 8, 5.1} does not work... maybe you had
something else in mind?

【在 p*****k 的大作中提到】
: blaze, sorry about backpedaling, but let's consider:
: x={5.1, 7.1, 8} and y={7, 6, 5},
: if i understand your approach correctly, one should start by putting "8" at position 2, because 5.1*8 < 7*6 < 7.1*8. but then easy to verify that either {5.1, 8, 7.1} or {7.1, 8, 5.1} does not work... maybe you had something else in mind?
: i also found that the ordering is not unique. consider:
: {7.1, 6.1, 5.1} with {7, 6, 5},
: which is good. but another ordering:
: {5.1, 7.1, 6.1} with {7, 6, 5}
: also works...

b***e
发帖数: 1419
13
Sharp! Thanks.
I see where my reasoning was flawed: using your example, after
locating 8, I got:
... 5.1, 8, 7.1, ...
... 7, 6, 5, ...
I was thinking, if 8 needs to travel to 6 to beat the corresponding
position in Y, 7.1 will certainly travel more (to cross 6) simply due
to the fact that 7.1 is smaller than 8. But the problem is that on
the border case, 8 is beating 6*7, while 7.1 is beating 5*7 (because 6
is ignored in the sub-problem). So yes, in this case, 7.1 does travel
across 8 to t
D**u
发帖数: 204
14
答案:
Let Z = (z_1,...z_n) and
f(Z) = \sum (z_k-y_k)/(z_k+y_k).
If for some k < m that
(z_k*z_m - y_k*y_m)(z_k-z_m)(y_k-y_m) < 0,
then we swap z_i and z_j in Z to define
Z' = (z1,... z_m,...z_k,...z_n).
We have
f(Z') - f(Z) = (z_m-y_k)/(z_m+y_k)+(z_k-y_m)/(z_k+y_m)
- (z_k-y_k)/(z_k+y_k) - (z_m-y_m)/(z_m+y_m)
= -1/2*(z_k*z_m - y_k*y_m)(z_k-z_m)(y_k-y_m)/(zk+yk)(zm+ym)(zk+ym)(zm+yk)
> 0.
So f(Z') is bigger than f(Z). Notice that f(Z) can only take finite number
of different values (since only finite

【在 D**u 的大作中提到】
: right, the ordering is not unique. So only the existense part is left.
:
: at position 2, because 5.1*8 < 7*6 < 7.1*8. but then easy to verify that
: either {5.1, 8, 7.1} or {7.1, 8, 5.1} does not work... maybe you had
: something else in mind?

b***e
发帖数: 1419
15
I see. I was going the algorithmic approach by trying to find an
effective way to compute the mapping, which is not necessary for the
proof.

【在 D**u 的大作中提到】
: 答案:
: Let Z = (z_1,...z_n) and
: f(Z) = \sum (z_k-y_k)/(z_k+y_k).
: If for some k < m that
: (z_k*z_m - y_k*y_m)(z_k-z_m)(y_k-y_m) < 0,
: then we swap z_i and z_j in Z to define
: Z' = (z1,... z_m,...z_k,...z_n).
: We have
: f(Z') - f(Z) = (z_m-y_k)/(z_m+y_k)+(z_k-y_m)/(z_k+y_m)
: - (z_k-y_k)/(z_k+y_k) - (z_m-y_m)/(z_m+y_m)

D**u
发帖数: 204
16
The proof I gave is not a good construction proof. We only know the swapping
process will eventually stop, but don't know when it will stop.
The problem is designed when I tried to solve
\max(\sum(zk-yk)/(zk+yk)), so the problem is proved by "cheating".

【在 b***e 的大作中提到】
: I see. I was going the algorithmic approach by trying to find an
: effective way to compute the mapping, which is not necessary for the
: proof.

b***e
发帖数: 1419
17
This is interesting. Do you have an instance of practical use which needs
such a mapping to be constructed?
D**u
发帖数: 204
18
Here is an interpretation.
Suppose you have n chess players (x1,...xn) to play n 1-1 matches with
another n players (y1,...yn). Assume if player x_i matches up with y_j,
he has x_i/(x_i+y_j) chance to win.
The question is: In order to maximize the expected number of wins of your
players, how do you want to order your players to match the other team.
This is equivalent to maximize \sum(z_i/(z_i+y_i)),
or \sum((z_i-y_i)/(z_i+y_i))

【在 b***e 的大作中提到】
: This is interesting. Do you have an instance of practical use which needs
: such a mapping to be constructed?

b***e
发帖数: 1419
19
This's cool, so there is an application.
In that case, you do need an effective algorithm to computer the mapping,
right? How are you currently doing it? The naive brute-force is n!. It
is hard to estimate the algorithm directly derived from your proof,
because the converge rate is hard to understand...

your

【在 D**u 的大作中提到】
: Here is an interpretation.
: Suppose you have n chess players (x1,...xn) to play n 1-1 matches with
: another n players (y1,...yn). Assume if player x_i matches up with y_j,
: he has x_i/(x_i+y_j) chance to win.
: The question is: In order to maximize the expected number of wins of your
: players, how do you want to order your players to match the other team.
: This is equivalent to maximize \sum(z_i/(z_i+y_i)),
: or \sum((z_i-y_i)/(z_i+y_i))

p*****k
发帖数: 318
20
DuGu, nice problem. my little grumble however is that the problem was inspired by the "solution" and you could have given us some hint...
btw, blaze, i am not sure from your later post whether your approach is fixable?
相关主题
GS interview questionCTC interview 1st round phone interview
【Brainteaser】Interview Questions我想找人一起写code
Murex interview questionshow to price Quarter pay Libor6M
进入Quant版参与讨论
b***e
发帖数: 1419
21
这个就是田忌赛马的推广。
It would be very interesting to have a generic solution/effective
algorithm for it.

mapping,
It

【在 b***e 的大作中提到】
: This's cool, so there is an application.
: In that case, you do need an effective algorithm to computer the mapping,
: right? How are you currently doing it? The naive brute-force is n!. It
: is hard to estimate the algorithm directly derived from your proof,
: because the converge rate is hard to understand...
:
: your

D**u
发帖数: 204
22
For the max problem, it will be good (but not always a must) to find a way
to compute the mapping. If the mapping is hard to construct, a necessary/
sufficient characterization of max(f(Z)) is also good.
Currently I haven't made more progress beyond
(z_k*z_m-y_k*y_m)(z_k-z_m)(y_k-y_m) > 0.
My "proof" only converge to a "local" maximum of f(Z), not the global
maximum. So I guess we need a new way to construct max(f(Z)).

【在 b***e 的大作中提到】
: This's cool, so there is an application.
: In that case, you do need an effective algorithm to computer the mapping,
: right? How are you currently doing it? The naive brute-force is n!. It
: is hard to estimate the algorithm directly derived from your proof,
: because the converge rate is hard to understand...
:
: your

D**u
发帖数: 204
23
the expected # of wins.
The problem was to maximize "the expected number of wins of individual games
", which is different from "the expected chance of TEAM wins (like a NBA
playoff 7-game series)". Under this interpretation, you have z_k/(z_k+y_k)
chance to win
the k-th game, so your expected number of wins for the k-th game is also
z_k/(z_k+y_k). Add them up over k, it is the expected number of wins of
individual games.
+y2)]
btw, the above formula for n=2 is the same as x_i/(x_i+y_1) + x_j/(x
p*****k
发帖数: 318
24
ah, of course, you are right. silly me.
here is another thought regarding the new maximum problem:
consider function: f(t)=1/(1+t), set t(i)=y(i)/z(i), so one has
t(1)*...*t(n)=[y(1)*...*y(n)]/[x(1)*...*x(n)] which is fixed. i wonder whether the continuous case: to maximize the sum of f[t(i)] s.t. the product of t(i)=const. might help. (so instead of pairwise swap, i am thinking of adjusting all n elements with some constraints)
unfortunately f is neither log-concave or log-convex, so the conv
D**u
发帖数: 204
25
Let's think about the case of n=2.
To maximize \sum(f(t(i))
(1) if t(1)*t(2) > 1, you want t(1) and t(2) to be as apart as possible.
(2) if t(1)*t(2) < 1, you want t(1)=t(2) (or as close as possible when there
are constraints)
(3) if t(1)*t(2) = 1, then it doesn't matter because f(t)+f(1/t)=1.
This is mainly due to the convexity of function g(x)=1/(1+e^x), which is
convex when x>1, but concave when x<1. This inconsistancy in convexity makes it hard even to conjecture
what the final t(i) might be

【在 p*****k 的大作中提到】
: ah, of course, you are right. silly me.
: here is another thought regarding the new maximum problem:
: consider function: f(t)=1/(1+t), set t(i)=y(i)/z(i), so one has
: t(1)*...*t(n)=[y(1)*...*y(n)]/[x(1)*...*x(n)] which is fixed. i wonder whether the continuous case: to maximize the sum of f[t(i)] s.t. the product of t(i)=const. might help. (so instead of pairwise swap, i am thinking of adjusting all n elements with some constraints)
: unfortunately f is neither log-concave or log-convex, so the conv

b***e
发帖数: 1419
26
独孤,I am wondering whether this problem, if solved, would generate
real-world value. It is very intriguing.
p*****k
发帖数: 318
27

one possible application is for the chess team championship (not necessarily round-robin tournament), with 4 members in each team. ignore the fact that games might end up with draw and the difference between white & black, team indeed cares about the points to gain in each round, rather than beating the other team.
(but 4 is a small number so presumably it's ok to enumerate)
back to the inequality, here are some special cases:
if t(1)*...*t(n) = 1, then sum of 1/[1+t(i)] < n-1
(with one -> inf

【在 b***e 的大作中提到】
: 独孤,I am wondering whether this problem, if solved, would generate
: real-world value. It is very intriguing.

D**u
发帖数: 204
28
Here is another intepretation of the problem.
n bulbs has expected life x_i, each bulb's breaking time follows a
expernential distribution. There are another n bulbs y_i. If you turn on x_i
and y_j, then bulb x_i has x_i/(x_i+y_j) to outlast y_j.
So the question becomes: how to order x_i to max the expected number of
bulbs that outlast the opponent's.

【在 b***e 的大作中提到】
: 独孤,I am wondering whether this problem, if solved, would generate
: real-world value. It is very intriguing.

1 (共1页)
进入Quant版参与讨论
相关主题
我想找人一起写code问大家一道数学题(probability)
how to price Quarter pay Libor6M请教一个老题implied vol和strike
请教两个作业题(Stochastic Calculus)请教一个简单问题: call option
我research中的问题详细描述(优化)如何证明euro. call opotion是convex的?
Ordering a sequence (2) (转载)对EURODOLLAR futures 的convexity不理解。。。
[合集] brainteaser弱问一道面试题
CTC interview 2nd round phone interview如何hedge negative convexity
面经:Why this trading strategy doesnot workGS interview question
相关话题的讨论汇总
话题: so话题: problem话题: let话题: distinct话题: mapping