An investment puzzle and speculation as to why some think its hard

 This is a Guest Post by David Marcus. He gives a puzzle and its solution, which is interesting, and then speculates as to why some people get it wrong. 

---------------------------------------------------------------------------

THE PROBLEM:

Investing Puzzle or Arithmetic Can Be Useful

The following is an example of investment results that I saw in an

investment newsletter. There are two portfolios that use different

strategies. Both portfolios start with $1 million twenty years ago and

withdraw 5% each year. The idea is that you are retired and withdrawing

money to spend. Not all years are shown in the tables.

Portfolio A

Year   Return  Withdrawal    Balance

2000   15.31%      57,655  1,095,445

2005    1.81%      59,962  1,139,273

2008  -12.65%      51,000    969,004

2009   34.26%      65,049  1,235,936

2010   11.94%      69,175  1,314,331

2015   -2.48%      64,935  1,233,764

2020   10.27%      66,935  1,271,765

Total Withdrawal: 1,685,190

Change in Balance: 27.18%

======

Portfolio B

Year   Return  Withdrawal    Balance

2000   -0.95%      49,524    940,956

2005    3.80%      44,534    846,154

2008  -20.11%      35,922    682,523

2009   18.27%      40,360    766,833

2010   11.57%      42,777    812,764

2015    0.99%      50,767    964,567

2020   13.35%      65,602  1,246,433

Total Withdrawal: 1,425,573

Change in Balance: 24.64%

Portfolio A has a final balance that is 25,000 more than Portfolio B's and

had about 260,000 more in withdrawals. Does the example lend credence to

the Portfolio A strategy being better than the Portfolio B strategy?

---------------------------------------------------------------------------

THE ANSWER:

Investing Puzzle or Arithmetic Can Be Useful: Analysis

Summary: The two portfolios have about the same performance over the 20

years. The difference is mainly due to Portfolio A having a good year or

years near the beginning before much money was withdrawn. The example

merely shows that it is better to withdraw money after a gain rather than

before.

Detailed Analysis:

The scenario is: Start with X = $1 million. Withdraw 5% a year.

Define "gain factor" to be 1 plus the percentage return. For example, if a

portfolio returns 5%, then the gain factor is 1.05.

Let A_j, j = 1, ..., 20, be the gain factors each year for portfolio A.

Let B_j, j = 1, ..., 20 be the gain factors each year for portfolio B.

The final amount in portfolio A is

   F = X * A_1 * 0.95 * A_2 * 0.95 * ... * A_20 * 0.95 .

The final amount in portfolio B is

   G = X * B_1 * 0.95 * B_2 * 0.95 * ... * B_20 * 0.95 .

From the "Change in Balance" values or the balances for year 2020, we see

that F and G are almost the same:

   F = 1.271865 * X,

   G = 1.246433 * X.

But, as we learned in elementary school, multiplication is commutative, so

   F = X * 0.95^20 * \prod_{j=1}^20 A_j,

   G = X * 0.95^20 * \prod_{j=1}^20 B_j.

Since F and G are almost the same, the total gains (product of the gain

factors) for the two portfolios are almost the same, i.e.,

   \prod_{j=1}^20 A_j \approx \prod_{j=1}^20 B_j.

Then what accounts for the big difference in the amounts withdrawn?

Portfolio A must have had some good years near the beginning. (We see in

the tables that Portfolio A did better in 2000 than Portfolio B.) So, all

the example shows is that it is better to withdraw your money after your

gains rather than before.

To take an extreme example, suppose an investment is going to go up 100%

this year. It is better to take your money out at the end of the year

(after the gain) than at the beginning of the year (before the gain). This

is a triviality.

The example tells us nothing useful about the two strategies.

Note: The total gains aren't exactly the same, but the timing of the yearly

gains is what is driving the results. We have (rounding off)

   ( F - G ) / 0.95^20 = 70942.81 .

So, if there had been no withdrawals, the difference in the portfolio

balances would have been about $71,000, much less than the $260,000 +

$25,000 difference with the withdrawals.

---------------------------------------------------------

WHY IS THIS HARD FOR PEOPLE?

Many people have trouble with this puzzle. The difficulty may be that such

people don't make a mental model (or a written model) of the process that

is producing the balance. If you write down (or have in your head) a

formula for the balance, then you see that the gain factors are independent

of the withdrawal factors. That is, we could withdraw more or less money,

or even deposit money, without affecting the gain factors we would use in

the model. This then leads us to consider the gain factors on their own,

and to recognize that the gain factors are the true measures of how the

strategies perform.

Ordering Beauty

First, congratulations to fellow complexity theorist and blogger Scott Aaronson for receiving the 2020 ACM Prize in Computing for "groundbreaking contributions to quantum computing". The prize is ACM's highest honor for mid-career researchers. Well deserved! 

Now back to our regularly scheduled post...

Every freshman at Cornell back in 1981 had to take two seminar courses, basically one-shot courses in an usually humanities area which required no prerequisites but lots of writing. I took my first course in philosophy. The instructor, a PhD student, at one point described his research, a philosophical argument that there is an intrinsic total ordering of beauty, say that Beethoven would always sit above the Beatles, no matter the beholder. I didn't believe him then and still don't today. A few months ago the Washington Post ran a story with the same theme entitled Maradona was great, and maybe the greatest. Can we make similar claims about artists?

Somehow we have this belief when it comes to conference submissions, that there is some perfect ordering of the submissions and a good PC can suss it out. That's not really how it works. Let's say a conference has an accept rate of 30%. Typically 10% of the submissions are strong and will be accepted by any committee. About half the submissions are just okay or worse and would be rejected. The other 40% of the submissions will be chosen seemingly randomly based on the tastes of the specific members of the program committee. Experiments in the NeurIPS and ESA conferences have bourn this out. 

Why not make the randomness explicit instead of implicit? Have the PC divide the papers into three piles, definite accepts, definite rejects and the middle. Take the third group and randomly choose which ones to accept. It will create a more interesting program. Also randomness removes biases, randomness doesn't care about gender, race and nationality or whether the authors are at senior professors at MIT or first year grad students at Southern North Dakota. 

We put far too much weight on getting accepted into a conference given the implicit randomness of a PC. If we make the randomness explicit that would devalue that weight. We would have to judge researchers on the quality of their research instead of their luck in conferences.

Given that conferences, especially the virtual ones, have no real limits on the number of papers and talks, you might say why not just accept all the papers in the middle. Works for me.

Is the following reaction to getting the first COVID shot logical?

 Alice works at a charity that puts together bag and box lunches for children.

They all wear masks and they are 12 feet apart and very careful, and nobody there has gotten COVID.

Then Alice gets here first COVID shot and says:

I am not going to work for that charity until I have had my second shot and waited  4 weeks so I am immune. 

She is really scared of getting COVID NOW that  she is on the verge of being immune. 

Is that logical? She was not scared before. So does it make sense to be scared now? I see where she is coming from emotionally, but is there a logical argument for her viewpoint? I ask nonrhetorically.

bill g. 

Quantum Stories

Scott Aaronson wrote last month about the hype over quantum computing. I'd thought I'd drop a few stories.

I was once asked to review a grant proposal (outside the US) that claimed it would find a quantum algorithm for NP-hard problems. I wrote a scathing review but the grant was funded because I failed to prove that it was impossible. I replied that they should fund my research to teleport people from Chicago to Paris because they couldn't prove I couldn't do it. I never got a response.

I was at an NSF sponsored meeting on quantum computing. I suggested, as a complexity theorist, that we need to explore the limits of quantum computing. A senior researcher said we shouldn't mention that in the report or it might hurt our chances of funding the field if they think quantum computing might not be a complete success.

I went to a Microsoft Faculty Research Summit which had a big focus on quantum computing. I complained of the quantum computing hype. My friends in the field denied the hype. Later at the summit a research head said that Microsoft will solve world hunger with quantum computing.

I was meeting with a congressional staffer who had worked on the National Quantum Initiative which coincidentally was being announced that day. I said something about high risk, high reward. He looked shocked--nobody had told him before that quantum computing is a speculative technology.

Quantum computing has generated a large number of beautiful and challenging scientific questions. Thinking about quantum has helped generate classical complexity and algorithmic results. But quantum computing having a real-world impact in the near or mid-term is unlikely. Most scientists I know working directly in quantum research are honest about the limitations and challenges in quantum computing. But somehow that message is not often getting to the next layers up, the policy makers, the research managers, the university administrators, the media and the venture capitalists. 

But who knows, maybe some quantum heuristic that doesn't need much entanglement will change the world tomorrow. I can't prove it's impossible.

Do any NP-reductions use deep mathematics? Non-rhetically

BILL: Lets say we didn't know that FACTORING NPC --> NP=coNP.

then what direction would we think Factoring in P or NPC? 

STUDENT: In P. After all, Number Theory is a deep subject and I can imagine some deep Theorem in it leading to FACTORING in P. 

BILL: That cuts both ways. I can imagine some deep theorem in NT being the key to showing 

FACTORING poly-reduces to  SAT

STUDENT: 

Deep mathematics HAS been used for algorithms. Factoring algs is one example, The graph minor theorem yielding MANY problems in P is another. Can you give me an example where deep mathematics has been used for an NPC reduction?

BILL: Oh. Gee. I do not know of any. 

STUDENT: If only you had some mechanism to ask the theory community. Maybe you could call it a web log, or weblog.

BILL: If only...

QUESTIONS

1) Are there any NPC reductions that use deep math? (I realize that the phrase `deep math' is not well defined,)

2) Are there other reductions that use deep math?

3) If P NE NP then: 

For all epsilon there is no approx-alg for MAX3SAT which yields  \ge  (7/8 + epsilon)OPT

For all delta  there is no approx-alg for CLIQ which yields > n^{-delta} OPT

No approx-alg for SET COVER which yields \ge (ln n + o(1))OPT. 

All of these proofs use  the PCP machinery or something similar. My impression is that the original PCP theorem, while long, hard, and impressive, did not use deep math. I have a vague memory of some paper or PhD thesis stating that the ONLY theorem needed was that a poly of degree d over a finite field has \le d roots. 

However to get the optimal lower bounds seemed to use some deep math. But I am more ASKING than telling. 

Want to Buy a Theorem?

This is embarrassing to admit but after a few badly timed trades on GameStop options I find myself a bit tight on money. To raise some cash, I reluctantly decided to sell one of my prized possessions, one of my theorems.

For Sale: Boolean formula satisfiability cannot be solved in both logarithmic space and quasilinear time. For a more formal and slightly more general statement and a proof, see this paper.

Bidding starts at 12 BTC (about $705,000). 

The winning bid, upon verified payment, will receive:

• The ability to give the theorem the name of your choice such as your own name, your best friend's mother's name or "Teddy McTheoremface".
• A non-fungible token (NFT) attesting ownership of the theorem and the name you have chosen for it.
• Anyone citing this result will be required to note that you own it and use the name you chose above. You cannot, however, limit the use of the theorem or receive compensation for its use. 
• By virtue of owning this theorem you will a Fortnow number of zero. This immediately gives you an Erdős number of 2. If you have previously written a paper with Paul Erdős then both of us will now have an Erdős number of 1.

Frequently Asked Questions

Q: Why this theorem?

A: The theorem is in one of my few solely authored papers and I can't afford to share the proceeds of the sale. 

Q: Doesn't Ryan Williams and others have stronger theorems?

A: The results are incomparable. Ryan gives bounds on a single algorithm with low time and space. My theorem allows different machines for the time and space bounds.

Also, to the best of my knowledge, Ryan's theorem is not for sale.

Q: Doesn't the proof of the theorem rely on other people's theorems such as Nepomnjascii? Shouldn't he get some of the value from this sale?

A: I'm not selling the proof of the theorem, just the theorem itself.

Q: If I purchase this theorem will I get to write next year's April Fools post?

A: No.

Slicing the Hypercube

Here's a neat result I heard about at virtual Dagstuhl last week, a new lower bound on the number of hyperplanes that cuts all the edges of a hypercube.

A n-dimensional hypercube has 2ⁿ vertices corresponding to the binary strings of length n. Edges are between two vertices that differ in exactly one bit, for a total of (n/2) 2ⁿ edges. Hypercubes played a large role in Hao Huang's recent proof of the sensitivity conjecture. 

A hyperplane is just a linear inequality in x₁,…,x_n the bits of the string corresponding to a vertex. An edge is cut if the inequality is true for one vertex and false for the other.

With n hyperplanes you can cut all the edges in two very different ways. 

• The hyperplanes x_i > 0 for each i. These are n orthogonal hyperplanes.
• The hyperplanes x₁+…+x_n > i for each i from 0 to n-1. These are n parallel hyperplanes.

Do you need n hyperplanes to cut all the edges? Mike Paterson found 5 explicit hyperplanes that cuts all the edges of a 6-dimensional hypercube (see survey by Mike Saks). Scaling that up means you need 5n/6 hyperplanes to cut an n-dimensional hypercube. That remains the best known upper bound.

For the lower bound, in 1971 Patrick O'Neil showed that any hyperplane can cut at most O(n^0.5) fraction of the edges (sharp by the hyperplane x₁+…+x_n > n/2). Thus you need at least O(n^0.5) hyperplanes which for 50 years was the best known bound.

Gil Yehuda and Amir Yehudayoff have given a new lower bound of O(n^0.57). The paper gives a O(n^0.51) bound but Yehudayoff said in a talk last week the bound has been improved.

Yehudayoff didn't go into much details in his 20 minute talk but the proofs uses geometry, probability and antichains. 

The result has some applications to complexity, namely you need at least n^1.57 wires in a depth-two threshold circuit for parity. But the main fun is the question itself, that we finally made progress and there is still a long way to go.

The key to my Taylor series problem: Buddy can you spare a penny, nickel, dime, or quarter

 In my last blog post I posed a question about finding the coeff of x^100 in a particular Taylor Series. The question and answer are given  here:

The key to the problem was to recognize that it was asking how many ways you can make change of a dollar using pennies, nickels, dimes, and quarters. This can be done by hand (its 242). 

1) Someone who I gave the problem to solved it by available software, but when he saw the answer was 242 he realized how to do it via making change.

2) How hard would this problem me to do completely by hand- say as a Putnam Problem? Its hard for me to say since I started with the trick and then found the problem. 

3) Is this a well known trick?