Wikipedia:Reference desk/Archives/Mathematics/2013 January 3

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 3

Low-probability high-payoff events

XKCD What-If #19 calculates that the typical acre of Florida land produces an average revenue of $0.03 per year from bales of cocaine falling out of aircraft. Based on the numbers given, this statement is true, but not exactly useful. Is there a better way of expressing the expected value of such high-value, low-probability events? --Carnildo (talk) 01:55, 3 January 2013 (UTC)

Note that you'd have to also add in the probability you will find the coke and be able to sell it before the drug dealers or cops stop you. StuRat (talk) 02:03, 3 January 2013 (UTC)

I believe Black_swan_theory has what you are looking for.OldTimeNESter (talk) 20:32, 3 January 2013 (UTC)

I don't see how that applies. Sure, having a bale of cocaine fall out of a smugglers' plane and land in your back yard could be described as a "black swan event", but I don't see anything in the article that lets me compute numbers more meaningful than "three cents per acre per year". --Carnildo (talk) 02:42, 4 January 2013 (UTC)

I'm not sure what's wrong with the $0.03 per year per acre figure, provided you account for the additional factors I listed above. This tells you the payout is absurdly low, so, even if you have no moral compulsion about selling cocaine, it would still be a bad investment to buy Florida land in the hopes of finding "white gold" on it. You could add up all the potential low payoffs like this, finding oil on your property, etc., but then you really need to include all the potential negatives, too, like that somebody will injure themselves on your property and sue you. StuRat (talk) 03:30, 4 January 2013 (UTC)

The approach is to talk about expected utility rather than expected money. Generally the utility of money is concave, which means that for low-prob high-pay, the expected utility is less than indicated by the expected money.

So if $0.03 per year per acre is bad even if it's guaranteed, having it is a low-prob high-pay event makes it even worse. -- Meni Rosenfeld (talk) 22:12, 5 January 2013 (UTC)

What the typical acre of Florida land has produced is not the same thing as what the typical acre of Florida land produces in the future. The one is deduction and the other is prediction. See here. Bo Jacoby (talk) 15:17, 8 January 2013 (UTC).

optimization and regularization!

I am trying to use total variation minimization for an image reconstruction problem. Essentially, I am trying to penalize different in the intensity of the two pixels in the reconstructed image. I minimize |Ax-b|+ \lambda |F(X)| where F(x)= (x_i - x_i+1)^2 is a quadratic function that penalizes the difference intensity of two nearest pixels.

I am however unable to decide how to fix the value of \lambda (strength of regularization). Bootstrapping is turning out to be computationally very expensive. In literature I found ways to find \lambda for the case of norm regularization using Lagrange multipliers. However, I am unable to find/formulate a method to find optimal \lambda for this case. Anyone has any idea about how to deal with it? Does anyone know if there exists a analytical form for optimal \lambda? — Preceding unsigned comment added by 210.212.187.69 (talk) 06:57, 3 January 2013 (UTC)

I don't understand what you mean by "penalize the pixels". StuRat (talk) 08:12, 3 January 2013 (UTC)

What I mean is the following :This is a regularization problem. The goal here is to find an x such that it minimizes |Ax-b|+ \lambda |F(X)|. |F(x)| ensures that image reconstruction is smooth (gradient of the image is minimum). Say x_i is the intensity of pixel i. By penalizing a pixel I mean, |F(x)| would choose the a solution such that x_i+1 should be as close to x_i as possible. — Preceding unsigned comment added by 210.212.187.69 (talk) 13:53, 3 January 2013 (UTC)

Decomposing hermitian matrix into rank-one matrices

Hello,

perhaps this is a well-known problem, but I could not find it anywhere on the net. Let us assume we work over the complex numbers. Let $A$ be a Hermitian matrix of rank $k$ . How can one describe the solutions of the matrix equation: $u_{1}u_{1}^{H}+\cdots +u_{k}u_{k}^{H}=A$,

where $H$ denotes the Hermitian transpose, and where all $u_{i}$ are column vectors.

I am in fact equally interested in the solution for finite fields.

Kind regards,Evilbu (talk) 11:10, 3 January 2013 (UTC)

You can rewrite this as $BB^{\dagger }=A$ where $B=(\,u_{1}\,\cdots \,u_{n}\,)$ (and I'm using † for the Hermitian conjugate). The elements of A are the pairwise inner products of the row vectors of B. Let U be a unitary matrix that diagonalizes A (i.e., $U^{-1}AU$ is diagonal). Then the row vectors of $U^{-1}B$ are mutually orthogonal and their squared norms are the eigenvalues of A (in order). You could stop there and say that the solutions are the columns of UC where U diagonalizes A and etc. Since different choices of U simply permute the solutions, you can just pick one U, and then you have a bijection between choices of C and solutions.

I can't remember when you can diagonalize symmetric matrices over finite fields, if I ever knew. -- BenRG (talk) 01:09, 4 January 2013 (UTC)

Thanks, I'm quite sure that any hermitian (not symmetric) matrix $A$ over a finite field is congruent to a diagonal matrix $D$ with only ones and zeroes on the diagonal, where I mean by congruence: there is an invertible $U$ such that $U^{\dagger }AU=D$. If I am not missing something, this should mean that the number of solutions is given by the size of the unitary group $GU(r,q)$. Evilbu (talk) 07:20, 4 January 2013 (UTC)

Singular value decomposition is relevant (and applicable for matrices which are not Hermititan). -- Meni Rosenfeld (talk) 22:15, 5 January 2013 (UTC)

Eigenvalue decomposition is the decomposition described in the question. — Preceding unsigned comment added by 123.136.64.14 (talk) 03:06, 7 January 2013 (UTC)

The decomposition described in the question is SVD, which happens to be equivalent to eigen since the matrix is Hermitian. -- Meni Rosenfeld (talk) 10:04, 7 January 2013 (UTC)

Actually, since there's some freedom in choosing the decomposition, it would be more accurate to say the decomposition in the OP is orthogonal diagonalization, which exists only for Hermitian matrices and is a special case of both SVD and diagonalization. Though SVD should be the first thing to come to mind when speaking about decomposition to a sum of rank-1 matrices since it gives the best approximation for any given number of summands. -- Meni Rosenfeld (talk) 14:48, 7 January 2013 (UTC)

Appreciated, SVD is more general, and ED is a special case, but since it is a special case there are useful properties of ED which may be useful to the OP which are not elucidated by the SVD article. Sorry for the acronyms.

Orthogonal ED is a special case of SVD. ED in general isn't, an asymmetric matrix will have very different SVD and ED. -- Meni Rosenfeld (talk) 15:35, 8 January 2013 (UTC)

I don't think this is a special case of either SVD or ED. For example ${\begin{pmatrix}1\\2\end{pmatrix}}{\begin{pmatrix}1&2\end{pmatrix}}+{\begin{pmatrix}1\\-2\end{pmatrix}}{\begin{pmatrix}1&-2\end{pmatrix}}={\begin{pmatrix}2&0\\0&8\end{pmatrix}}$ but the vectors are not orthogonal and are not eigenvectors of the matrix. -- BenRG (talk) 00:33, 9 January 2013 (UTC)

You're right. I'll rephrase again: In the OP's terms it is possible to choose the decomposition so that the vectors are orthonormal, in which case this is orthogonal ED etc.

Not sure this all applies to finite fields, but I think it does. -- Meni Rosenfeld (talk) 13:15, 9 January 2013 (UTC)

Cell phone pre-paid card optimization

I've tried very hard to determine which prepaid cellular cards are best for me (I'm on TracFone), but the math of it leaves me a bit stymied. The various cards offer some combo of "days" and "minutes". All the TracFone cards roll over. My current method is to figure out which I'm likely to run out of first, then solely optimize for that. So, if I expect to run out of minutes first, I will select whichever plan costs the least per minute, completely ignoring the days included. If I expect to run out of days first, then I'd optimize for which card costs the least per day, completely ignoring the number of minutes included. This is a bit of a simplification, though, and I will sometimes pick a card which costs slightly more per minute or per day, if it includes massively more of the other attribute. However, what tends to happen is I alternate between a purchase which is optimal for minutes, but leaves me short on days, then a purchase which is optimal for days, but leaves me short on minutes.

I'd like to find a more scientific way to do this. I can calculate my average number of minutes used per day, but what would that tell me ? I can find a card that most closely resembles that ratio, but there's no guarantee that it will save me in the long run.

The best solution I can come up with is as follows:

1) Determine the ratio. For this example, let's say I average 10 minutes per day.

2) Pick some arbitrarily large quantity, say a million days. That would mean I'd need 10 million minutes to go with it.

3) Write a computer simulation to try every combination of cards to get me to a million days and 10 million minutes, then select the combo which costs the least.

However, in addition to being complex, this also wouldn't be guaranteed to be correct, as the cards are always changing costs and terms, my usage patterns might change over time, and I wouldn't necessarily know which card to buy first from the "optimal suite".

So, any advice on better ways to determine the optimal card for me ? StuRat (talk) 20:27, 3 January 2013 (UTC)

Oh boy I sound like a salesman. How about just going with something like virgin mobile? It is prepaid. And their pricing structure is much simpler. One plan even gives you unlimited minutes with unlimited texts and data (I've never had issues with throttling). And if you keep track of your past usage, it is useful up to a point. Sometimes you just grow into a plan. For example if you rarely text right now, and if you get something which happens to have unlimited texts or something I guarantee you, you will start texting more. - Looking for Wisdom and Insight! (talk) 06:16, 5 January 2013 (UTC)

My main goal is to keep the costs low. I currently pay about US$7 a month and as low as 5 cents a minute, and I doubt if Virgin Mobile can beat that. StuRat (talk) 06:25, 5 January 2013 (UTC)

The most obvious moderately simple yet fairly rigorous approach that occurs to me is to characterize your typical usage pattern and describe it as a probability distribution. Then capture each candidate package's constraints and costs, and define a function of the cost to you (including throttling, payments and annoyances). Then run a Monte Carlo simulation to determine the expected cost of each package. If you like, you can model uncertainties in future package terms as well.

That said, the cost in time of actually making such a study is likely to overshadow the savings compared to a choice between packages made on gut feel or even simply trialing different options, unless you turn a profit selling your program in the internet. So you're stuck with making an executive decision on what approach to use. Mobile providers seem to deliberately make comparison difficult by providing a plethora of complicated packages. I would not be surprised if they are deliberately doing so to force the market away from the optimum decision model, to their profit. — Quondum 08:50, 6 January 2013 (UTC)

Yes, so far I go for whichever one "seems" like the best deal, but I would like a more scientific approach. I wonder if any apps exist out there for this. StuRat (talk) 22:26, 6 January 2013 (UTC)

If you attack that kind of problems with an "I wonder if any apps exist out there for this" attitude, you'd be well advised to try the MPU strategy. - ¡Ouch! (^{hurt me} / _{more pain}) 13:12, 8 January 2013 (UTC)

Minimum phone usage. :p

I don't quite follow. Are you saying that using the app would cost more than it would benefit me ? StuRat (talk) 01:16, 9 January 2013 (UTC)

Yup;)

Esp. since I know you can code. And you won't run into the bias of whoever coded the damn app. The money needed to "convince" an app author to bias their app towards a certain provider is pocket change to them. 61453 for thought. - ¡Ouch! (^{hurt me} / _{more pain}) 07:52, 11 January 2013 (UTC)

61453 ? StuRat (talk) 09:44, 11 January 2013 (UTC)