Mathematics - 2021-04-28 (page 2 of 3)

Euler 2

07:03

벼蛮๖媖

noobs will be tricked into thinking that this is chinese

Edward Evans

Do you just go from weird obsession to weird obsession and then spam it here?

Euler 2

well yes but actually no

maybe i should stop posting encrypted messages

Edward Evans

it's irrelevant if you do or don't since nobody can read them

Euler 2

yes that's true

robjohn

>(R5QB{U-#U.m9 [:0`9;zS7 HtO)oe8"

so there. I can do it too. That is an actual encrypted message.

Edward Evans

07:18

swhocare

here is a shifted message

decrypt

sinclair

is it true that if V is a subset of a vector space W, then the span of V is a subspace of W?

robjohn

@EdwardEvans indeed. just wanted to show how useless it is to try to decrypt a message

Edward Evans

@sinclair yes, take e.g. the subset consisting of all basis vectors of your vector space

@robjohn right lol

sinclair

thanks

Edward Evans

@sinclair this is a silly example but yeah, the span is the subspace consisting of all linear combinations. You're just taking all the vectors in your subset and smashing them all together in such a way that all of the subspace axioms are fulfilled

sinclair

07:21

i guess that makes sense, I'm just conscious of stating this fact

Euler 2

okay so i should stop posting encrypted messages

Edward Evans

That's fine, it's good to ask questions that you think are "silly" because we've all asked questions we thought were silly at some point :P

3

Euler 2

but but but

188 214 18 70 206 54 76 198 230 170 182 198 22 66 194 70 206 98 226 146 140 156 234 166

Eminem

07:53

Given two programs $P_1$ and $P_2$ executing the same two functions $f_1$ and $f_2$ but with different algorithms.

Say $P_1$ execute $f_1$ faster by a factor of $x$ but execute $f_2$ slower by a factor of $y$.

How do I know which program is faster and how much?

robjohn

it depends on how often you run the two functions.

Eminem

the same amount of times

Lets say 1 time

robjohn

I meant how much time is spent on each function, which may include number of times used.

Marcel

Quick question for which there is presumably a quick answer: under the DLog assumption, is it hard to determine whether two discrete logarithms are coprime? IOW, given $(g^x, g^y)$, is it hard to tell if $x$ and $y$ have a common prime factor?

Eminem

Yea so each function is executed once per program.

robjohn

08:06

If $P_1$ spends $s_1$ seconds on $f_1$ and $s_2$ seconds on $f_2$ then $P_2$ would spend $xs_1+s_2/y$

@Eminem that doesn't matter if we don't know the amount of time spent in each function

Eminem

I just want to know the relation between them, not the actual amount of time.

robjohn

well, if $f_1$ takes and hour on $P_1$ and $f_2$ takes a second, the factor $y$ is of little importance.

Eminem

Ok let me rephrase

robjohn

which is faster depends on how long the programs spend in the various functions.

Eminem

The problem i'm facing is whether or not to implement an AVL tree for a certain problem I have. Currently it is implemented in a linked list, but obviously insertion to a list is faster but searching is much slower.

robjohn

08:13

usually the trees are built once and searched many times. If that is the case, go with the faster search.

Eminem

You are right, but I wanted a mathmatical estimation on how much faster will it run

robjohn

again, that depends on how much time is spent building the tree and how much time is spent searching

If we don't know these, there is no way to compare

Eminem

What kind of data is missing here?

robjohn

how much time is spent building the tree and how much time is spent searching

I am guessing the time searching is the major one and so the ratio of speeds would be the ratio of the searching time

Eminem

hmmm... So if the average size of the tree is $a$, and i perform $m$ searches

robjohn

08:17

If you are building a tree to do one search, then don't build the tree, just scan the data

Eminem

No no. Im performing huge amounts of searches

robjohn

so go with the program with the faster search

Marcel

Ignore the question above, the answer is obvious (at least given DDH, which is enough for me)

robjohn

the tree building will be a small fraction, unless it is so slow that it takes longer than the enormous number of searches done in the other program

@Marcel great, because I had no idea :-)

Eminem

Total list search = $c$

Average list search = $d$

Total insertion = $a$

Average data base size = $b$

tree avg search = $\log_2e=f$

tree avg insertion = $\log_2b=g$

Improvment = $\frac{fd}{c}-g$

Is this analysis correct?

robjohn

08:25

it's hard to tell, since the terms are not defined well. are they total time in execution or what?

Eminem

hmmm... So $c$ will be the amount of times the program actually moves from a node to another node in the list.

Its hard to explain :)

robjohn

This is like telling me that there are 12 trucks, how many chickens are in them?

Eminem

lol

robjohn

the data is not of the proper type to draw the conclusions you want

Marcel

@robjohn: At least, I think so (admittedly this turned out to be a bit of an X-Y question, since I initially specified a weaker assumption):

Assume $G$ is a group for which DDH is hard, with generator $g$ and order $q$. Consider $(g^a, g^b, g^c)$ with $a,b$ randomly and independently selected from $\mathbb{Z}_q$ where $c$ is either $ab$ or randomly and independently chosen from the same set.

Assume that the decision problem specified above is solvable (in PPT). Take $g^a$ and $g^c$, and check if the exponents are coprime, and do the same for $g^b$ and $g^c$. If neither pair has coprime e…

robjohn

08:34

@Marcel This is about the difficulty of breaking certain types of encryption?

(in the end)

Marcel

Not really, I wondered about this when reading about Schnorr signatures, but it has no direct relation to any cryptosystem I know of

robjohn

Ah, okay. Usually when I hear "time to compute discrete logs", it has to do with the difficulty of breaking a cryptosystem

In any case, I am not up on the current state of computing discrete logs. I know there has been a lot of work done on that problem, though

so I don't know what DDH or the decision problem refers to.

Marcel

08:54

Ah, I should have explained more clearly. The DDH assumption states that for certain groups, it is hard to determine if $c$ in the above example is equal to $ab$ or if it is randomly chosen from $\mathbb{Z}_q$

geocalc33

can metrics add to 0?

$g_1+g_2=0$?

robjohn

09:16

Not on a Riemannian manifold since the tensors have to be positive definite

geocalc33

oh

@robjohn what about $g_1=dx^2+dy^2$ and $g_2=-dx^2-dy^2$

robjohn

@geocalc33 $g_2$ is not positive definite. You can define any $2\times2$ matrix and call it a metric, but the geometry may not be what you might expect. For example, complex distances.

geocalc33

@robjohn I was under the impression that $g_2$ was the same as $g_1$ just

reflected or something

robjohn

I don't think so, but ask Ted, he's the expert. (If he dares to enter the zombie room again.)

geocalc33

09:37

@robjohn okay thanks. oh yeah if you reflect the euclidean plane the distance still has to be positive. duh. just measured from a different orientation

Monty

11:05

When people say compactness theorems (w.r.t proving convergence of sequences) what are they generally referring to?

(convergence of sub-sequences of functions that is)

s.harp

13:07

stuff like azerla ascoli

leslie townes

13:37

they're generally referring to compactness in a function space :) more specifically arzela ascoli is an example of the kind of result people look for. often they only look for sufficient conditions (not necessarily necessary ones) because the application of interest is not in complete generality.

anakhro

Good morning leslie

leslie townes

hello

there are good compactness results for families of analytic functions on nice domains, which mean that a lot of suprema or infima over sets of functions are actually attained. that is a common application of compactness, solving an extremal problem in a function space.

problems in PDE or the calculus of variations can often (not always) leverage compactness theorems in appropriate function spaces. it is not usually clear a priori that solutions to such things exist. if compactness is around it helps you get there.

anakhro

Also compactness theorems are a popular topic in complex analysis, as a specific example of that for analytic functions.

Though they use the horrible name "normal" families instead of "precompact"

leslie townes

14:03

i like that.

a lot of those results predate point-set topology.

my daughter just said that our cat had ears, a chin, and a butt. all true.

s.harp

"normal" and "regular" are synonyms and their universal mathematical meaning is along the lines of "you have to look this up every time"

leslie townes

we need as many definitions of 'normal' as possible. so normal families can stay.

en.wikipedia.org/wiki/Normal let's all do our part and grow this entry as much as possible.

my daughter just learned that if you run up to a cat and swat at it, the cat is likely to swat at you right back. and now she's eating breakfast with the cat sitting next to her plate. friends again.

geocalc33

I'm moving on

leslie townes

where's the party bus headed next?

geocalc33

I'm moving on in math relationships music career

I'm turning the whole leaf

leslie townes

14:16

flipping the script

i've done that before. it is liberating but one shouldn't do it too often.

once every 5-10 years.

geocalc33

just kidding im not doing that

robjohn

@geocalc33 only turning part of the leaf?

or just peeking under to see what might be lurking?

geocalc33

yeah I'm evaluating the leaf

robjohn

Heading off soon to get my wife her second vaccination.

she is more nervous about this one than the first one. I think she's psyched herself out. Too much time to think about it.

Thorgott

14:32

well, stuff like normal subgroup, normal field extension, normal cover at least share the same adjective for a reason

leslie townes

my wife was thrilled when i said, instead of doing more math, i'll go back to school for three years and go into six-figure debt.

Thorgott

not at all like simple group vs simple field extension

leslie townes

but that was the leaf i turned over.

'normal families' is just someone being lazy about the use of the word normal.

no connection to anything.

paul montel, apparently.

whose students included dieudonne, who formed a group with other 'normaliens' that became bourbaki and tried to eradicate the careless use of language.

small world.

Rover

14:57

Can anyone please suggest a good geometry book that covers all why? And how? Questions I.e it also tells few things about how it evolved..

leslie townes

i like robin hartshorne's geometry: euclid and beyond.

it's partially a tour of euclid and also more than that. maybe a little too axiomatic for some tastes. does get into the how and why.

Edward Evans

15:16

@leslietownes I saw Hartshorne's geometry without reading Euclid and beyond and thought that you might be overshooting the reference request slightly

leslie townes

hartshorne does have other slightly more advanced geometry books.

syllabus of the first AG class at berkeley was like, "we will do the first thirty pages of hartshorne." count me out of that.

it's rare to see a book engage with euclid from a modern point of view. a lot of high school level books do a mishmash of euclid and analytic geometry and don't really distinguish between the two, and regard euclid as a kind of supernatural being. and more modern treatments of geometry don't have time to engage with euclid.

Thorgott

why is leslie talking about geometry

this isn't how things should be

leslie townes

i'm ted

we switched accounts

KeithMadison

I was recently given the following problem: determine the triple integral of f(x,y,z) dV given that f(x,y,-z) = -f(x,y,z). This seems much to trivial for a post, yet I can't quite wrap my head around it. Wouldn't this simply be 0?

Oops, I misread the problem. It should be: *f(x,y,-z) = f(x,y,z)

leslie townes

i would like to know about the region over which this integral is taken.

the function enjoys a kind of symmetry but if the region doesn't you wouldn't expect the integral to be evaluable from only the given information.

KeithMadison

15:26

Sadly, it isn't given, nor is f(x,y,z). I was supposed to use only that information to solve the problem.

leslie townes

that's just goofy.

it seems underdetermined to me. maybe sharper minds than mine can weigh in.

M. Çağlar TUFAN

Hey everybody. I have a question.

leslie townes

seems like something to do with orthogonality. my turkish is rusty.

M. Çağlar TUFAN

I couldn't understand how my teacher calculated $\int_0^L(\sin(k_3x)\sin(k_mx)dx)=\frac{L}{2}\delta_{3m}$

leslie townes

math.stackexchange.com/questions/638308/… may be of use.

M. Çağlar TUFAN

15:32

@leslietownes Yes, my teacher told a little about orhogonality of triginometric functions and kronecker delta but I'm confused right now

leslie townes

one way to see it is via a trigonometric identity. sin(a) sin(b) being something relating to a difference of cosines, and if things aren't zero you have cancellation.

if you're integrating over a full period, anyway.

i remember when i first learned of the orthogonality of these functions. a student in my class asked the professor "what does that mean?" and the professor responded "it means that those integrals are equal to zero."

very good day of professoring from that guy.

M. Çağlar TUFAN

Yes, I also think that it doesn't explain much that way :P

I actually tried to find the solution of integral just by solving it but I ended up like this:

leslie townes

i think my first linear algebra course was the worst course i took in college.

followed closely by the first course in real analysis, from someone who had no idea about analysis and should not have been put in that position. i liked her personally, one time she bought me lunch.

Edward Evans

Mine was by far ordinary differential equations

M. Çağlar TUFAN

$b_m=\frac{1}{L}\left(\frac{\sin(k_3L-k_mL)}{k_3-k_m}-\frac{\sin(k3_L+k_mL)}{k_3+k_m}\right)$

Edward Evans

15:37

The prof who taught it was relieved of teaching duties the year after I graduated because he was so awful

probably what he wanted

played it well

leslie townes

when i was at iowa, multivar was fully occupied by a guy who was personally pleasant but beyond incompetent as an instructor. the students would go on and take real analysis and not know anything from multivar.

Rover

@leslietownes does that contain conic section?

leslie townes

i can't think of where i learned the classification of conic sections. it may have been in multivariable calculus.

which frankly is a weird place to put it, but what do i know.

Rover

Conic section in calculus? Ok

leslie townes

i certainly didn't learn it in high school, so it must have been some kind of calculus.

Rover

15:42

Coordinate geometry is what only we have and conic are major part of them..

Any other books ?

leslie townes

regarding those trigonometric integrals. i'm assuming that k_3 and k_m are integers. i wonder if you plugged in the bounds of integration after finding an antiderivative.

euclid's three dimensional geometry is almost entirely ignored by everybody. they stop at 2d. i think hartshorne's review of euclid also similarly stops there. i don't know why.

M. Çağlar TUFAN

@leslietownes yes, I plugged in the bounds of integration this was the last result I got. I also found something about orthogonality

$\int_0^L(\sin(k_nx)\sin(k_mx)dx)=\frac{L}{2}\delta_{nm}$

and this results in $m\ne n \Rightarrow 0$ and $m=n \Rightarrow \frac{L}{2}$

That is how my teacher simplified that integral.

leslie townes

L seems like it ought to be an integral multiple of 2pi. is that included somewhere?

M. Çağlar TUFAN

I think I found the "how" part of my question but I still dont know "why" these 2 equations are equal.

Umm, actually this is a problem about vibration of string that is attached at both ends

L is the length of the string

but $k_m=\frac{m\pi}{L}, m=1,2,3...$

leslie townes

oh, OK.

as long as the period of the sine function matches the length of the interval, that is OK.

Koro

15:55

@M.ÇağlarTUFAN: For the integral, just read about orthogonality. It will also help you when you study Fourier series

Hi @leslietownes

M. Çağlar TUFAN

@leslietownes I see. Thanks for the help, I kinda understand the simplification. Even tho I have no idea about orthogonality :P

Koro

@M.ÇağlarTUFAN: In this context, I meant that if $f, g$ are two orthogonal functions on interval $(a,b)$ then $\int_a^b f(t) g(t) dt =0$

M. Çağlar TUFAN

@Koro Yes, I should to learn about orthogonality. My teacher told the class that we will be learning about Fourier series in greater detail in the next semester. But she introduced Fourier series briefly in this course, because we needed to use it.

Koro

@M.ÇağlarTUFAN: For example: $\sin x $ and $1$ are orthogonal on $(0,2\pi)$

@M.ÇağlarTUFAN: If you know that, you can understand Fourier series right now :)

M. Çağlar TUFAN

How do I test if $f(t)$ and $g(t)$ are orthogonal?

copper.hat

16:01

you need an inner product

Koro

@M.ÇağlarTUFAN: Refer what I mentioned above about it :) and comment from copper hat also.

M. Çağlar TUFAN

@copper.hat I know how to calculate inner product of 2 vectors but, 2 functions is something I'm not familiar :/

@Koro @copper.hat I can see what I should to learn with your help. Thanks a lot!

Koro

There are theorems which can be proven true or false. There are methods to prove a statement true or false. For example: One case use direct method, contradiction, contrapositive etc. But how to prove that a theorem can neither be proven nor disproven? Is there any example of that?

I know Continuum hypothesis is one such statement.

copper.hat

@M.ÇağlarTUFAN I don't know your particular situation, but I imagine is it something like $\langle f , g \rangle = \int_0^L \overline{f}(t) g(t) dt$. Possibly with different scaling.

leslie townes

euclidean geometry offers instances of something akin to this. without the parallel postulate, certain propositions are true or false depending on the model you choose for the assumed axioms. so you can't prove or disprove those propositions without adding more data.

offering models satisfying whatever you assume, in which the thing you want to prove alternately holds and does not hold, is one way of showing that something cannot be proved or disproved from a set of assumptions.

if we had logicians here they could be better at this than i am.

Koro

16:11

@leslietownes: Ahh, I understand your point. Basically the set of axioms kind of falls short is what you probably mean. But how does one go about to show it?

M. Çağlar TUFAN

@copper.hat Yes, it is something like it but the left hand side is a series from n=1 to infinity. But I got the answers I was seeking, thank you.

leslie townes

it depends on the axioms. i don't think there's a generic proof machine that you can run on this kind of stuff.

Koro

I see @leslietownes. Many thanks.

leslie townes

it's hard! they spent the entire 19th century arguing about this stuff.

smarter people than us, too.

Thorgott

the very rough outline is that one proves that we can add different axioms to our standard axioms in a manner that is consistent (if our standard axioms are consistent to begin with) and that we can do as such both in a way that makes a given claim false and in a way that makes a given claim true

Koro

16:14

I wonder if a 6 year old kid asks this question what answer should one give?

One can't say continuum hypothesis

unless the kid knows continuum hypothesis.

leslie townes

that's an interesting question. i'm an attorney and often, the legality of an act depends on the legal system where the act takes place. and sometimes the laws don't fully address the extent of what 'the man on the street' would regard as illegal behavior.

but it's very rare to be able to say X is legal or X is illegal. it really depends on the list of 'axioms' where you do X.

when my 2.5 year old daughter asks why she can't do something i just say it's because she can't do it.

leslie townes

16:26

some of you will find amusing the fact that today i am giving an internal presentation to new hires about how to deal with opposing counsel. i am an authority on this issue.

copper.hat

are we surprised?

Clarinetist

Laws are a lot more vague than most people would think, purely by design

I've had to read federal statutes, interpret them, and apply them for two jobs now. I wish that others could have that experience.

copper.hat

i'm still trying to find a definition of "right of way"

in the context of car vs pedestrian competition.

leslie townes

yeah that's never defined.

and god help you if you live in albany.

Clarinetist

@copper.hat I'm learning that the hardest thing about using a QP solver is actually rephrasing my problem in the QP form

copper.hat

16:41

i've forgotten what we were doing, sry.

the reality is that there is a huge leap from a few lines of an idea on a page to the work required to express, test, debug.

this is true in maths as it is in software development.

Clarinetist

Oh, I have numbers $x_1, \dots, x_n$ that are percentages rounded to the nearest tenth of a percentage with identical denominator and differing numerators (both denom and numerators unknown). I'd like to find values $y_1, \dots, y_n$ so that $\sum_{i}(y_i - x_i)^2$ is minimized, $0 \leq y_i \leq 100$, $\sum_{i}y_i = 100$, and another condition that I just thought of today: $x_i - 0.05 \leq y_i \leq x_i + 0.05$.

leslie townes

i'm an ideas man, michael. i think i proved that with [bleep] mountain.

copper.hat

@Clarinetist surely it is just the identity for the 'A' and $-2x$ for the 'b' part of $y^TAy+b^Ty$?

Clarinetist

@copper.hat Yeah, I figured out the objective function just this morning. Now I'm trying to figure out the constraints.

It would be an absolute miracle if the solution is unique, but I highly doubt it is

copper.hat

sure it is.

Clarinetist

16:47

Soon I will get myself to learn some optimization theory... that has been poking at me over the last few years. I despise that statisticians seem to intentionally avoid it.

copper.hat

closest point to a closed convex set is unique

Clarinetist

I took a machine learning course in the stats department in my MS... the professor put out a claim with a proof consisting of a single smiley face, to which he commented "let's leave that to the OR people"

copper.hat

i like luenberger's "optimization by vector space methods" as a nice high level approach. maybe a little too abstract at times.

focus on the underlying ideas & geometry. it is easy to get lost in the analysis, duals, etc.

i have yet to find a satisfactory presentation of duals in an optimisation context other than using non differentiable analysis, but that is a mountain of analysis itself.

Clarinetist

Noted. Thanks. I'm hopefully going to start serious study into optimization within the next month or two.

Friday is my very last lecture for a very long time at the very least, and Monday is my very last exam I'll be administering

copper.hat

i would be driven by need & interest rather than duty. i think i understand where you are coming from

(motivationally, i mean)

Clarinetist

16:54

I'm glad to finally spend time studying what I'd like to study... as opposed to dealing with formal classes

Ted Shifrin

@leslietownes yes, you are an authority on opposing!

Jade Vanadium

17:16

Hey Ted. Did you find your square yet?

If you have a functional approach to the problem I'd really be interested in seeing the details.

Kumar Shuvam

17:42

Let $z$ be a complex number such that $ \left|z+\frac{1}{z}\right| = 1$ and arg(z)= $\theta$, then the minimum value of $8sin^{2}\theta$ is?

hello

Clarinetist

@copper.hat How do you express the constraint $y_k \leq 1$ for all $k$ in the form $\mathbf{A}^T\mathbf{y} \geq \mathbf{b}$ for some matrix $\mathbf{A}$ and column vector $\mathbf{b}$?

Kumar Shuvam

@Clarinetist can u help me?

Clarinetist

@KumarShuvam I don't know complex numbers at all very well, otherwise would

Kumar Shuvam

@robjohn @copper.hat help me?

@Clarinetist oh! no problem ..thank u

copper.hat

@Clarinetist $-I^T y \ge e$, where $e$ is a vector of ones.

Kumar Shuvam

17:48

@copper.hat guess what I learned LateX

Clarinetist

@copper.hat Maybe I'm looking at this completely incorrectly, but wouldn't that be equivalent to saying that $y_k \leq -1$ for each $k$?

copper.hat

what is the difference?

Clarinetist

... I have $y_k \leq 1$, the one you have says $y_k \leq -1$?

Kumar Shuvam

@LeakyNun U there?

copper.hat

sry, replace $e$ by $-e$

Clarinetist

17:53

Ah, I see. Thanks @copper.hat

Kumar Shuvam

18:04

@copper.hat u saw my question?

Rover

@KumarShuvam arg(z)=y/x ? If z=x+iy ?

Then, try putting z=x+iy ..

Kumar Shuvam

Well argument in complex number is basically the angle of rotation from +ve real axis i.e arg(z) = tan^-1(y/x)

I did tried to put z=x+iy but all in vain...I'm not getting anywhere..

Koro

@KumarShuvam put $z=r e^{i\theta}$

Then your $\frac 1z$ becomes $ \frac 1r e^{-i\theta}$

Then simplify.

Kumar Shuvam

Ok I need to solve $ \left|z+\frac{1}{z}\right| = 1$ ?

Koro

You didn’t have first equation in your original question.

Kumar Shuvam

18:14

yes..yes sorry

Koro

Simplify this equation and you’ll get your answer.

Black Jack 21

Hi everyone. I am stuck at a problem for 2 months now and if I can show the following then I would be able to solve it. I am unable to do so, it would be great if someone can help!

https://math.stackexchange.com/questions/4118465/a-question-on-limits-for-tuples?noredirect=1#comment8519477_4118465

Kumar Shuvam

Umm! can I square both sides? @koro

Koro

You should get: $(r+\frac 1r)^2 \cos^2\theta +(r-\frac 1r)^2\sin^2\theta =1$ @KumarShuvam

Semiclassical

no. the cross-terms don't simplify like that

(also, if that were true then the LHS wouldn't depend on r. but theta=0 and theta=pi/2 clearly give different functions of r)

Koro

18:25

@Semiclassical ? theta=0 won’t satisfy the given condition.

Semiclassical

oh

i misunderstood the context

ignore entirely

copper.hat

surely you get $r^2+{1 \over r^2} + 2 \cos (2 \theta)=1$?

Semiclassical

yes.the point was to solve that equation, that's what i missed

Koro

The most important key in a laptop is the key that has stopped functioning. For me it’s right curly bracket.

Semiclassical

yes

copper.hat

18:28

carefully clean the key

Clarinetist

Oh good grief. Apparently the constraints are inconsistent.

copper.hat

better to fail fast :-)

Semiclassical

What's the inconsistency?

Clarinetist

I wish I knew enough optimization theory to know why this would fail

No idea

Oh, I'm an idiot

I should've had them sum up to 100, not 1

... still inconsistent

Back to the drawing board

Semiclassical

how're you concluding that they're inconsistent?

Clarinetist

18:35

R is telling me they are, per the quadratic programming solver I'm using

Semiclassical

huh

Clarinetist

Here is the program I am trying to execute in R, for your context:

copper.hat

i dont see how $\sum_k y_k =1 $ and $y_k \ge 0$ can be inconsistent?

Clarinetist

$x_1, \dots, x_n$ are percentages rounded to the nearest tenth of a percentage with identical denominator and differing numerators (both denom and numerators unknown). I'd like to find values $y_1, \dots, y_n$ so that $\sum_{i}(y_i - x_i)^2$ is minimized, $0 \leq y_i \leq 100$, $\sum_{i}y_i = 100$, and another condition that I just thought of today: $x_i - 0.05 \leq y_i \leq x_i + 0.05$.

Semiclassical

only thing i can see is that xi could conceivably be negative under these conditions, but that seems unlikely

leslie townes

18:36

"another condition that I just thought of today" makes me nervous, but applaud the spirit. always improving.

copper.hat

without knowing $x_k$ it is hard to say, i would drop the last condition first and then add it back in much more relaxed and then tighten it up

no magic here.

Clarinetist

Yeah, I'm going to have to execute this procedure... what, 18 times?

I have 18 different $\mathbf{x}$ vectors

copper.hat

use the computer :-)

Semiclassical

maybe start with a simple test case

like n=3

Clarinetist

All nonnegative values that are supposed to be percentages that this website decided to round to the nearest tenth of a percent. THIS IS WHY WE DON'T ROUND PERCENTAGES without providing the numerators and denominators

Semiclassical

18:39

lol

copper.hat

this is how real world data comes...

Clarinetist

I swear this website tries to make it as difficult as possible to get their data. They don't even have them stored in Excel docs. All PDFs that even if you tried to copy and paste the values into Excel would not come out as a table.

But I digress. Lol.

Semiclassical

so is this something to the effect of: the true fractions are 1/7, 2/7, and 4/7, but you're only given 0.143, 0.286, and 0.571

and you want to discover the true fractions by optimization?

Clarinetist

Correct, @Semiclassical, and I need these to represent a probability distribution to proceed with running more sophisticated stats on them.

Ideally, it would be nice if I could discover the true fractions, but honestly, I'm just at the point where I just want to stick with a probability distribution that is "close enough"

copper.hat

wait, that's a different problem...

do you know all the values are rounded versions of ${n_k \over d}$ for some $d$?

Clarinetist

18:43

Yes, but $d$ is unknown

Semiclassical

i take the simplifcation to be that Clarinetist is willing to settle for writing these as a/1000, b/1000, c/1000 for integer a,b,c

Clarinetist

@Semiclassical Nah, I don't even need the integer values

Semiclassical

(or something like that)

hmm

copper.hat

i think i am missing part of the puzzle.

Clarinetist

So here's what I've got

This organization hosts an exam

Semiclassical

18:45

oh. i guess part of the problem is that the rounded percents need not add to 1

Clarinetist

@Semiclassical Yes, precisely

Semiclassical

so you're really trying to figure out how to normalize the percentages

copper.hat

that is just projection onto the simplex.

Clarinetist

They have this exam every year, for which they've reported in PDFs one column with whole-number scores, and a percentage of people who obtained said scores, rounded to the nearest tenth

Semiclassical

one solution would be to rescale each value by the sum

and thereby force the sum to be 1

Clarinetist

18:47

@Semiclassical That was suggested yesterday in a stats question I posed, and I may resort to that. The method I was more comfortable doing was described by the optimization problem I posed above, solving for the $y_k$

copper.hat

just project.

Semiclassical

well, the main advantage of the projection method is that it's really cheap :P

copper.hat

why don't you solve the projection problem first and see what you get.

i mean solve the qp.

Clarinetist

@copper.hat Will that guarantee that the $y_k$ stay within the 0-1/0-100 range? I guess that's the only reason I'm worried about that.

Semiclassical

yes

copper.hat

18:48

i don not understand

if there is a solution, the constraints must be satisfied

Semiclassical

all you're doing is rescaling, i.e., dividing all of your percentages by a common value. that can't make any of the values negative, and therefore none of them can exceed 100% either

Clarinetist

Sorry, when I hear "project", I think "Lagrange multipliers", so sum to $1$, but ignore the inequality constraints

Semiclassical

ah.

copper.hat

and there must be a solution to the projection problem.

$\min \|x-y\|^2 $ subject to $y$ being the the simplex.

just try it. its all of 5 mins coding.

Clarinetist

The only reason I've been frustrated today is I tried to translate this to the QP solver - with the $y_k \geq 0$ and the $x_k - 0.05 \leq y_k \leq x_k + 0.05$ constraints implemented - and the QP solver insists that the constraints are inconsistent

Semiclassical

18:51

oh. different kinds of projection

i'm thinking (x1,x2,x3)->(x1,x2,x3)/(x1+x2+x3)

which is not orthogonal projection

copper.hat

jeez guy. solve the simple problem first, then make it harder

Clarinetist

K lol

Let's see what happens if I remove those constraints...

leslie townes

you are getting advice from a good source.

Semiclassical

yeah, i could see orthogonal projection knocking you out of the positive orthant

leslie townes

copperhat may have done this before a time or two.

copper.hat

18:52

solving the qp will keep you in $y \ge 0$.

Clarinetist

Oh, I know he has. He's heard me complain about the Boyd and Vandenberghe text ad nauseam

leslie townes

i suggest LAPACK. not the new version, the one from the 1980s.

i'm being facetious.

copper.hat

generallly i compute first if we are talking about 5-15 mins work

the computer time is cheaper than your time

(well, unless you are running 100k+ jobs, but that's my day job)

Semiclassical

my version of that, i think, is that if i'm faced with a sufficiently hard probability problem

i just simulate it

copper.hat

yes. compute don't think

Clarinetist

18:54

Yeah, the problem is that my optimization background is very weak

leslie townes

it's very frequently easier to simulate. it keeps you from going down rabbit holes.

copper.hat

or at least, short cut the think part

Semiclassical

or at least don't think while you're computing :P

copper.hat

well, for me it is about bugs

i can find a software bug faster than an intellectual bug

Clarinetist

I could see, if this needed to be scaled up beyond what I'm doing, having to put this into something like C++

That sounds like an utter headache

copper.hat

18:55

a monte carlo requires no thinking.

leslie townes

be careful that you simulate the right distribution. i wasted a year doing that once.

Clarinetist

Agreed with the Monte Carlo thought

copper.hat

jeez lad, burn your bridges after you cross them

Semiclassical

@copper.hat correct, right up until you run into the numerical sign problem :3

copper.hat

you will always make mistakes. the goal is find them quickly :-)

Semiclassical

18:56

though tbf that's less "monte carlo requires thinking" and more "monte carlo is great, when you can apply it"

copper.hat

i am grossly simplifying life here

Clarinetist

So it looks like removing the constraints has given me a solution, but it doesn't look great... many of them appear to have been zeroed out

Semiclassical

a bunch of hard physics problems can be summed up as "we can't figure out how to get monte carlo to do it"

hence why QCD remains computationally hard

copper.hat

i am guessing you have some errors. when you sum the data $x_k$ is that reasonable?

Clarinetist

LOLLLLLL

You were right LOL

I used the wrong column

Semiclassical

18:58

blinding flash of the obvious?

Clarinetist

-_-

copper.hat

everything is obvious afterwards...

like resigning from my highpaying window office job in a nice town with lots of food.

Clarinetist

THIS IS ACTUALLY WORKING!!! Lol

Semiclassical

cool

Transcript for

$Mathematics$ Mathematics