You throw a die until you get 6. What is the expected number of throws (including the throw giving 6) conditioned on the event that all throws gave even numbers?

The “obvious” answer is incorrect.

The correct answer can be brute-forced by computing probabilities of this sort:
If \(s\) is a sequence of length \(n\), then
\(P_n\triangleq\) = P(\(s\) ends in 6 and \(s\) all even) = \((2/6)^{n-1} (1/6)\)
(The total probability over all \(n\) is therefore \(Z=(1/6)/(4/6)=1/4\).)
The expected length of \(s\) is \(\sum_{n=1}^\infty n (P_n / Z)\)
\(= \sum_{n=1}^\infty n (2/6)^{n-1} (1/6) / (1/4) = \sum_{n=1}^\infty n (2/6)^{n-1} (2/3) = 3/2\)

This is interesting since premature conditioning on the 3 even sides of a die in every roll produces an (incorrect) expected length of 3.

There is already an elegant and convincing derivation of the correct answer attributed to Paul Cuff if you follow the links from the original article, but here’s an intuitive explanation for why the incorrect answer overestimates the expected length in such a way –

Notice that in \(P_n\) the probability \((1/6)\) of obtaining the final 6 has no effect on the expected length. The expected length depends entirely on the shape of \(P_n\) over \(n\). The calculation for the “incorrect” reasoning would have made the sum \(\sum_{n=1}^\infty n (2/3)^{n-1} (1/3) = 3\), and the difference is in the \((2/3)^{n-1}\) vs. \((2/6)^{n-1}\) term. So the existence of 1, 3, and 5 matter; they make longer prefixes of 2 and 4 even less likely, as more of the longer sequences that would have been valid ends up containing a 1, 3, or 5 instead and getting thrown away.

Note: There is also a good discussion on Quora.

Then there are those who expect not only to have a non-negative real return, but at least a market return. This is the expectation that during the consumption period, we will get at least as much value as we “stored” proportionally to the fraction of output we produced in the economy at the time of “storage.” For example, if technology improved, we would expect that our “stored” widget version 1, would be returned to us as the much improved widget version 10. This seems greedy yet fair. In contrast, the expectation for non-negative real return seems rather tame now, doesn’t it? Until you consider that the economy might actually contract. What if, due to whatever circumstances, the excess producers during the consumption period do not produce enough value to proportionally divide among those who “stored” value an amount that is more than what they stored? This could be by will or by necessity. What if all we had were widget version 0.5? Would it still be plausible to insist on non-negative returns? It would not.

In fact, following a period of great excess in production, especially one that prematurely fulfilled useful work for some time into the future (until new technology and demand develop), the right view is that the nominal amount of stored value is irrelevant — it is not exchangeable.

Now the second assumption. Capital markets are a great invention. They solve the centralized allocation problem in a distributed way. We assume that rational actors freely acting in their own self interests will produce a solution that allocates capital in the “optimal” way. Perhaps it isn’t a global optimal (requires cooperative strategies), but a more basic question is what planning problem do they solve in the first place? Let us give individual actors the benefit of the doubt that they can do planning and are perfectly rational. Nevertheless, it seems difficult to imagine that any would do planning much beyond their own lifespans. That would not be rational. Thus, capital markets are essentially solving an allocation problem based on each individual’s preferences for maximizing their own utilities during their lifespans. This has great implications. First, it puts an upper bound on the planning period for the allocation problem at the longest remaining lifespan among individuals. This is like 80 years or so. That is pretty myopic. It seems like a long time, but for many decisions, especially concerning resources, it is very myopic.

It gets worse. That was just an upper bound. Inputs into capital markets are weighted by the amount of money committed to a trade. It is a given that older (working) people have greater wealth, and as a consequence their inputs as expressed by capital commitment are weighted more in the allocation decisions. That is exactly what you don’t want, because a shorter remaining lifespan is now correlated with larger weight in decisions. The net result is that the capital allocation decisions are being carried out for optimality over very short planning periods, possibly only on the order of 10 or 20 years at most. It isn’t even optimal for most people alive any more.

So this is a fundamental problem in capital markets. Under the law of one price for open markets, only one view can be ultimately carried out, and it is one that is too myopic, and even myopic for most people. The only way to correct for this is to weight the inputs properly, and that would require external intervention to enforce a political planning decision.

1. The ‘System’ process uses a low level of CPU (~6%) when nothing is going on.
2. Chinese characters in the system (e.g. file names) suddenly become boxes.

The first problem caused excessive battery drain along with the CPU fan going on and off all the time. Because Task Manager doesn’t tell you what is under the ‘System’ process, I had to use Process Explorer, which promptly identified the culprit: a revolving series of threads labeled ‘ntoskrnl.exe!KeReleaseInStackQueuedSpinLock+0x1e0′. This would appear to be some issue with a driver stuck on something and aimlessly retrying. It turns out turning off Wifi cured it. An updated driver for the Broadcom 4313 802.11n card fixed the problem permanently. The old version was 5.100.82.82 from 5/2011. The new version that does not have the problem is 5.100.82.112 from 10/2011.

The second problem is caused by a little-known new setting in Windows 7. Under Control Panel -> Fonts -> Font settings, there is an option “Hide fonts based on language settings.” It’s simply broken, so I just turned it off.

Microsoft has for years tried to get into mobile devices. Here you see Bill Gates really uncomfortable with the notion that Apple has succeeded more than Microsoft in this space. He is not wrong, since for a time Windows phones and tablets were the only ones out there, while Apple’s Newton was forgotten memory. Those devices either used a slightly modified Windows OS or one that copied all of its metaphors. The latest Windows phones are an exception, but with Windows 8, it will no longer be. It cannot be disputed that there are important applications that do not exist on mobile devices (currently), and therefore mobile devices are not complete (currently). So people argue that mobile devices will be full-fledged computers or desktops will not die. The idea of a dual interface seems to be aimed in this direction. However, a third possibility exists. Applications, after all, merely solve real life problems. They are not themselves holy. If there were a different way of accomplishing the same things, the applications could be replaced. One could argue that data is the rather more holy object. Back to this later.

While devices are converging, it becomes a question of what the hardware distribution of the future will look like, and how functions will be partitioned among them. In this video, Steve Jobs posits a rather linear, functional view of computing history, where things moved from desktops to more mobile devices as usage functions evolved from scientific and office work to entertainment and socializing. Bill Gates posits a more encompassing and parasitic view, seeing computing power spreading to colonize all niches, a niche for each device, none really going away. To him, the kind of space or niche makes a difference, like whether a device fits in a pocket or not.

What they are both getting at is that there are constraints — some hardware, some social convention — that limit what functions can be used where. Because if it were at all possible, why wouldn’t one want all functions on all devices? But there are power, weight, screen-size, and input device constraints that are fundamental. Given that, you can’t possibly have all applications run in all devices.

To address this, one way is to have all devices become one device — a hardware solution along with its companion software like Windows 8. This “classic” solution has existed quite a while now, e.g. convertible laptops, some better than others. The problem is in both hardware and software. The equivalent tethered power and heavy-case computing power cannot be had with mobility at any given time, even though mobile devices are more powerful than computers of even a few years ago. And the software interface is also different — requiring a stylus for mouse-like precision (although I like the stylus, it’s one more thing to hold). With Windows 8, the interface problem maybe is solved, but the hardware problem remains. There is talk of some dual-part computer where you can remove a light (both weight and CPU power) piece of it. The non-mobile base of such a computer would have additional processing capabilities as well as keyboard and mouse like a standard docking station. The hardware design for this though, would be enormously complicated if it were to be efficient. For example, two processors separated a great physical distance, does not make for good communication speed. Either that, or when the light piece is docked, its own capabilities are totally disabled for its trivial contribution to total computing power. This would be a waste of hardware and the cost would be even greater than a tablet and a separate non-mobile computer combined.

So what about another way. Forget combining all devices into one device — in hardware. Why not have all these devices, and even let them run all their vastly different applications and interfaces at vastly different processing capabilities, but combine them at the level of data? Given the constraints of the devices, people will write any and all applications that support functions natural to them — we need not worry about that. We only care that these applications can access a common set of data and have seamless sync’ing between them. This also has a buzzword already, it’s called cloud computing. Yet I don’t think it’s about migrating applications to the cloud — not so, although some of that will take place, for “light” applications (light on bandwidth and computation). The full power of each device though, is going to harnessed, I am sure of that. So the best gains from the cloud is data sync’ing. This is a problem not merely of sync’ing, but of a method to record data in a way that is universally available regardless of software or hardware platform. It’s not just document data, but things like preferences, and program states. And I’m not talking about applications that are simple and entertainment-like or applications already on the web for which devices are only terminals. Furthermore, this “cloud” doesn’t even need to be an internet company, it can be managed among the devices themselves or by any mostly-on device that is at a common locus of interaction, like a “cloud server” or some such in the home. I think this is the more likely future, because it makes more sense.

Two problems arise with Scheme B. One, winning players whose dollar-per-chip exchange rate happens to be “higher” than average can’t be paid back fully from that game alone, or ever if he keeps winning. Two, the players may not declare truthfully. Is there a clean way out of this?

The second problem is complicated, so ignore it now. The first problem occurs because the group of players does not, in aggregate, support the payoff profile demanded by the players with above-average dollar-per-chip exchange rates, if they also win more than average. In this context, we see that Scheme A (a group playing with agreed-upon equal-dollar stakes) gets around this problem by essentially setting a common exchange rate for everybody at the minimum of the group (that which enticed the last person to join). This works, but can we combine Scheme A’s payoff fairness with Scheme B’s utility matching fairness?

To some extent, yes. A marginal improvement can be made by noting that, as long as the players do not win 100% of the games, some exchange rate flexibility can be allowed. This is an interesting fundamental trade-off: the less spread out the winning percentages of players, the more spread out they can bid their exchange rates, and vice versa. In the one extreme, players set the same exchange rates (Scheme A) and any game outcome can be supported. At the other extreme, if the players are equally likely to win, then on average no chips change hands, so it wouldn’t matter what exchange rates were set (Scheme B). I should probably quantify what happens in the middle but can’t be bothered to do it today.

This is an interesting question because at first thought, one would think that in a large enough network, a sufficient number of independent reads on the truth will occur in the aggregate to allow at least the later-deciding nodes to get a really good estimate of the truth. This is the basis of the folk belief in “wisdom of the crowd.” However, this is not what happens all the time.

The problem really lies in the fact that a social network is (inadvertently) running a rather constrained version of belief-propagation, not the full-fledged belief-propagation that we would like, in which the nodes are more sharing. For example, in belief-propagation, full distributional beliefs are passed instead of these binary decisions, where estimation information is abridged and suppressed locally. If the observed decisions embody estimates so compressed as to be heavily distorted and not very indicative of the truth, then given certain network topologies, error propagation may not decay away. Then there is also something about single-pass decision-making that makes it impossible for nodes with the wrong answers to correct themselves and for the network overall to always converge on the right answer. Of course, some cooperative protocol could solve the problem, but we can’t really assume all nodes in a social network are cooperative, or even not adversarial.

So the crowd is not always right. In fact, it can be manipulated by “excessively influential” nodes in bad network topologies, as some other results in the talk indicated. Learning occurs a little more robustly in network topologies where some small (but non-negligible) fraction of nodes are “independently observing” ones that don’t listen to other nodes, but are listened to.

Here is a different kind of problem: if there are limited copies of each of the \(k\) coupon types (say, \(d\) copies), how many samples does it take to collect \(t\) coupon types?

By the pigeonhole principle, we have two extremes: from \(n=0\) to \(n=t-1\) samples, it is impossible to collect \(t\) coupon types; and for \(n>(t-1)d\) samples, it is impossible not to. For number of samples in between, there is some monotonically decreasing probability that \(t\) or more types are not collected. Let’s call the latter probability \(P(n)\). The expected number of samples it takes to collect \(t\) types is then

Finding \(P(n)\) for \(n\ge t\) doesn’t appear easy, though the combinatorics could be written down (in theory), maybe involving partition functions, Stirling numbers, or whatever. But the question is reduced to the following, which somebody must have solved: given a \(d \times k\) 0-1 matrix, in which \(n\) 1′s are placed randomly, what is the probability that exactly \(z\) columns are 0-weight (have 0 column sums)?

These papers give some approximations:

http://arxiv.org/PS_cache/arxiv/pdf/0806/0806.1480v3.pdf

http://cs.anu.edu.au/~bdm/papers/irregular.pdf

Does anybody know the actual answer?

* As an aside, TeX4PPT inside PowerPoint is probably the fastest way to make scalable figures and math. There is just no way that any other drawing tool even comes close to the speed with which simple diagrams can be made using PowerPoint. Since the LaTeX people seem completely uninterested in the end user, there is basically no choice in the matter. My work flow these days involves LyX initial drafts with LaTeX final drafts for papers and PowerPoint with TeX4PPT for presentations, using pen input for the initial drawings. Not ideal, but getting there.

But I ran into a problem where every time I saved any LaTeX expression with the symbol \(\gamma\), it turns into a degree symbol, that little circle °. It turns out \(\gamma\) is codepoint U+00B0 in the font cmmi10. But PowerPoint’s default master template has gone stupid, and never wants to change the font type of just that one codepoint, so it goes with the Arial glyph there, which is the degree symbol. It doesn’t help that LaTeX is stuck in the stone age and doesn’t know about Unicode, instead using about 20 different fonts with overlapping codepoints to make the expressions.

So in the end I had to carefully recreate a clean master template in PowerPoint. For future use, it is saved here.

I think there are two options here. Either structure needs to be explicitly enforced or presentation needs to be refined.

In the former, perhaps it is better to only allow replies in certain places. Perhaps it is better to only allow edits in certain places. Perhaps it is better to separate the two and keep the distinction between edit mode, thread mode, and conversation mode, and only allow mixing in very restricted settings (or require some extra steps to discourage its use). After all, in preparing a shared endeavor, the purpose should be defined and known ahead of time.

In the latter, perhaps a lot of hiding and collapsing should be used. Perhaps hyperlinks should be used for in-place edits that often hijack a topic. And now that subthreads can sprout like a tree, it makes little sense to retain the linear structure of conversations. Perhaps a topic based graph, or a conversation stack would be the more appropriate presentation metaphor.

Wave is a good idea, but not well thought out. In its attempt to differentiate, it has forsaken useability for chaotic flexibility, which would have had redeeming value, were it matched by equally ambitious presentation/visualization.