Mark Gritter's Journal|
[Most Recent Entries]
Below are 20 journal entries, after skipping by the 20 most recent ones recorded in
Mark Gritter's LiveJournal:
[ << Previous 20 -- Next 20 >> ]
[ << Previous 20 -- Next 20 >> ]
|Monday, July 22nd, 2013|
|Capital Raising Through Arm Twisting
Today's "On Business" column by Neal St. Anthony discusses a plan to create a local fund-of-funds for early stage venture capital
Local venture capitalists and fund managers have been quietly urging Gov. Mark Dayton’s administration to embrace a privately financed and operated equity fund....
The idea would be for flagship Minnesota institutions, such as U.S. Bancorp, Thrivent Financial and Ameriprise, to perhaps pledge several million dollars each, followed by foundations and perhaps affluent individuals. A fund-of-fund manager, operating under agreed-upon guidelines, would disburse the money to Minnesota and other private equity and venture capital managers.
There's nothing wrong with a little cheerleading for local investment. That sort of boosterism is certainly the governor's job. But showing up at U.S Bancorp's door and asking them to invest more money with local VCs? That goes a bit far too me. Are the VC's going to give up their 2-and-20 on the deal, too? The article doesn't say, and hints at some desire for public-sector involvement.
It would be one thing if Minnesota didn't have venture capitalists to provide early-stage funding--- but we do. Capital crosses borders (especially state borders!) easily, and if local VCs can't raise enough money for their investment funds, they're failing at their job. Why bail them out with cash from Minnesota's successful large companies?
Now, don't get me wrong--- I'd much rather have had a $348m state venture capital fund than a new Vikings stadium. But it's not clear to me that this sort of deal is on the correct side of the line between "the governor provides a little bit of social lubricant for a good cause" and back-room cronyism. Maybe I'm hypocritical, but I'd rather have the state pony up some money if this is a social good, than have VCs propped up by private investments that otherwise wouldn't get made.
|Sunday, July 21st, 2013|
|How Not to Build a Large-Scale Marketplace
Steam rolled out a collectible cards, and a "community marketplace"
for real-money trades. As expected, the value of all the cards rapidly trends towards zero after their introduction. But I've earned a significant fraction of a dollar selling on it. :)
Unfortunately, for heavily-traded items the marketplace is nearly unusable, because there is no way to specify a market-price or limit purchase. Instead, each item has a list of offers to sell from specific users (and I think each offer is for a single item, even if they have multiple they want to sell--- I certainly didn't find any way to make a bulk offer.) So attempting to purchase at a low price is an exercise in frustration, because anything on the first page is already sold by the time it pops up on your web browser.
The "feature" of "I want to buy from my friend" thus interferes with the main goal of a marketplace, which is to match up buyers and sellers. I dunno, perhaps they anticipated this and it's a mechanism to encourage trades at above-market prices (so that their transaction fee is higher.) Or are they copying somebody else's RMT market design which is equally bad?
Note also that the marketplace is saved from being a money-laundering tool only by the inability to cash out Steam credit. Transactions with named counter-parties rather than anonymous ones are just the wrong model here.
A set of cards can be turned in for a "badge" which gives "experience points" and other collectibles. The other collectibles trade at a significant discount to the cost of the badge itself in cards--- for the summer promotion badge, the 10 cards trade at about $0.15 each, while the two items (profile background graphic and special chat emoticon) I got with the badge trade at $0.03 each. (They seem to suggest some badges will provide DLC or coupons in the future.) An interesting experiment--- obviously the badge in the abstract is worth more to people than the specific rewards, and I don't think it's the XP. Though more XP gets you more "friend" slots, I guess that might be worth something. But I wonder if people think the badge rewards are better than they actually are.
(Yes, I did make a RMT trade to get the badge, but only as a way of trading my duplicates for the one in the set I didn't have. So I guess the badge--- or at least curiousity--- was worth at least $0.15 to me.)
|Tuesday, July 9th, 2013|
|Random Matrix Algebra
I've been getting familiar with the Sage environment. Here's a nontrivial result (but I dunno how interesting it is) about eigenvalues.
Take the finite field GF(3), and look at all its 3x3 matrices. How many of these 39
= 19683 matrices' characteristic functions have all three roots? Or no roots? Brute force search reveals:
No cubic in GF(3) has just two roots for the same reason as cubics in the reals don't have just two real roots, I think. The element of a field extension in which those two extra roots exist must cancel out. But in GF(3) you've got degree-three extensions too, so zero-root polynomials exist as well.
What's potentially interesting here is the symmetry breaking for (0, 0, 1) and (0, 0, 2). Those cases have +1 and -1 count, respectively, than you would "expect" by comparison with (0, 0, 1), (1, 1, 2), (0, 1, 1), and (1, 2, 2). The single-root cases are perfect symmetric, by contrast.
Anyway, since these roots are the eigenvalues it turns out that just slightly over 50% of the 3x3 matrices in GF(3) have the full set of eigenvalues (and thus might be diagonalizable, although probably a lot are defective.)
Expanding to 4x4 matrices (43 million of them) or GF(5) (about 2 million) would require a lot more processing time, so I'd like to make the computation smarter in some way.
|Sunday, July 7th, 2013|
I played through "Puzzle Agent" last night which was amusing enough, although few of the puzzles were truly hard. I think what seemed "cheapest" to me is that the "fit N items into this space" puzzles gave you extra help by sticking pieces together that belonged together.
Anyway, I thought this puzzle had a nice algebraic solution, but the puzzle itself seems overspecified.
Is it really necessary to know the number of fish, or just that the number of fish making it to the river is fixed?( solutionCollapse )
|Sunday, June 30th, 2013|
|Some stuff from the Eagan Art Fair
From Dale's Woodcraft (daleswoodcraft.com), a Seega board
. Had you heard of this game before? I had not; it is claimed to be an ancient Egyptian board game. Conceptually a little similar to Nine Men's Morris. (You can also buy a board for that.)Thomas Siciliano, papermaker
has some very nice garden art. His booth included some 3-D peppers I don't see in the Etsy shop.
I bought a new tea mug from Adama Sow
, but his website features mainly his more serious pottery.
|Monday, June 24th, 2013|
|Tintri's first patent
Gritter family patent totals:
David Gritter: 30
Daniel Gritter: 6
Mark Gritter: 1 as of this month!
Tintri's first patent was approved June 11th: number 8463825
has said, "now I'm part of the problem." :)
|Sunday, June 16th, 2013|
|Mathy thing I learned today
V. K. Leont’ev, Roots of random polynomials over a finite field, 2006
(payment required but you can see the first couple pages.)
As the size q
of a finite field Fq
grows larger, the number of roots of a random polynomial from Fq
[x] asymptotically becomes a Poisson distribution with mean value 1. That is, for large finite fields, a random polynomial can be expected to have just one root within the finite field.
random matrices give rise to uniformly distributed characteristic polynomials (which I'm not at all sure is the case) then we can expect random matrices over finite fields to have just one eigenvalue, on average.
|Friday, June 14th, 2013|
|Eigenvector decomposition on finite fields
I thought this question on Quora about eigenvalue decomposition of matrices over finite fields
was interesting, and I answered it (in the affirmative, the eigenvalue decomposition is possible but sometimes the eigenvalues require an extension to the field.) Unfortunately "polynomial time" does not mean "feasible" when your matrix becomes large.
For real-valued matrices there are a variety of algorithms that do clever things I don't understand to compute the eigenvalues quickly as limiting sequences.
To experiment: what happens if you run these algorithms with finite fields instead? Seems like you either ought to get convergence or cycles, but it's not clear that either would tell you anything about the eigenvalues.
All this reminds me that I should post my Tubulo solver
on Combinatorium, as long as I've got the domain registered... and I still have some work I'd like to do on sliding and match-3 games.
|Thursday, June 13th, 2013|
|Sunday, May 26th, 2013|
|Paying Influencers with Influence
I blogged about Wahooly when it launched
as a company to reward "influencers" with equity in the companies they promoted. The company has pivoted, renamed itself Chasm.io
, and now is trying to tell a story about reciprocal sharing
. Sharing links ("content") earns points, which can be cashed in to get others to promote your content.
In theory this attempt to make influence a fungible commodity seems like a novel effort. If you're a well-respected expert on, say, VMware, but want to promote your sister-in-law's new novel, a "whuffie" marketplace allows you to make that trade. Or you may just want to expand your blog readership beyond the circles you can already reach.
But, I remain dubious. It seems like the desire to do any sort of cross-domain "credibility swap" would be rare. It's hard to see how a Duncan Epping
would be motivated to earn points by making tweets he wouldn't otherwise send. But there's no economy of influence without those additional tweets, so there has to be a critical mass of influencers who think they could be bigger influencers--- or, enough people who wouldn't otherwise see each others' content but do have Chasm.io in common.
|Sunday, May 19th, 2013|
|Classic Math Geek Sunday
...will not become a regular feature, unlike timprov
's classic photos.
But I did get a question from a high school student about a calculation I'd done about the game Tonk, five years ago on 2+2: http://forumserver.twoplustwo.com/21/draw-other-poker/profitably-dropping-tonk-315444/
I didn't mention the technique in the forum post, but I used a generating function to count the possibilities. If you multiply (1+yxk
) together for each value of "k" in the deck (as a multiset, not a set), you get a polynomial whose coefficient on yi
is the number of ways to make a "j"-point hand with "i" cards.
Back in 2008 there wasn't a readily available symbolic manipulation tool available on the web, so I hacked some python together to do the math. Today there's Wolfram Alpha, whose limited-duration (free) computation is powerful enough to give:
simplify | Coefficient[(1+y x)^4 (1+y x^2)^4 (1+y x^3)^4 (1+y x^4)^4 (1+y x^5)^4 (1+y x^6)^4 (1+y x^7)^4 (1+y x^8)^4 (1+y x^9)^4 (1+y x^10)^16, y, 5] as
4368 x^50+7280 x^49+10640 x^48+16720 x^47+22496 x^46+31216 x^45+40436 x^44+52556 x^43+65532 x^42+82176 x^41+92548 x^40+105176 x^39+116832 x^38+127484 x^37+136344 x^36+143676 x^35+147784 x^34+149268 x^33+146936 x^32+140224 x^31+134052 x^30+125188 x^29+115520 x^28+103808 x^27+92416 x^26+79416 x^25+67600 x^24+55712 x^23+45584 x^22+36708 x^21+28948 x^20+22144 x^19+16520 x^18+11988 x^17+8344 x^16+5724 x^15+3784 x^14+2492 x^13+1552 x^12+920 x^11+484 x^10+240 x^9+92 x^8+28 x^7+4 x^6
which (fortunately) seem to be the numbers I came up with in October 2008.
I wonder how well Wolfram Alpha's freemium model is working for them. :)
|Monday, May 13th, 2013|
|Late-night group theory
Nearly every undergrad who takes abstract algebra learns the proof that the 15-puzzle
cannot be solved if two of the tiles are reversed. That's because the permutations generated by the sliding motions are a subset of the entire permutation group (Sn), called the alternating group (An). The alternating group contains permutations that can be expressed as an even number of transpositions (called, unsurprisingly, "even permutations"), and a single-tile swap is an odd permutation.
So what if the motions are instead wraparound "slides"? That is, take an entire row or column and move it as many squares as you want, with tiles wrapping around from left to right or top to bottom. Does that set of moves produce the entire permutation group? Or is it the alternating group, or some other subgroup?
For odd-sized grids, the slide moves produce just even permutations. For example, sliding the top row on a 3x3 puzzle like this:
3 1 2
4 5 6
7 8 9
is the cycle (1 2 3) = (1 3)(1 2), which is even.
For even-sized grids it seems possible to generate a single-transposition--- say, (1 2)--- since the slides are odd permutations, but how to prove it?
Well, one way is brute force. For a 4x4 grid it might be just feasible to find the shortest "word" (combination of generating moves) which generates a particular transposition, although the search space is of size 16! =~ 2*10^13. I thought for a bit and bounded depth-first-search seemed better than BFS or heuristic search, because the queue size could become very large. But the size grows very quickly, even with two pruning heuristics at work.
The 8 basic moves on a 4x4 grid are H1, H2, H3, H4, V1, V2, V3, V4, where Hy slides the y'th row right by one, and Vx slides the x'th column down by one. The reverse moves can be generated by cycling around, i.e., H1^-1 = H1.H1.H1. So there are two easy ways to prune the DFS tree. The first is that we should never use the same move more than three times in a row. The second is that all the H's commute with each other (and so do all the V's), so we shouldn't explore both H3.H2.H1 and H1.H2.H3 since they are the same.
Depth # of words (w/o pruning commutative pairs)
4 2443 4673
6 95883 298057
So much for brute force--- we didn't find (1 2) in this search, and going to 14 would take more than overnight.
But, that undergraduate algebra class probably talked about commutators as well, moves of the form y^-1.x^-1.y.x. In solving a Rubik's cube these moves tend to swap just a subset of the cubes, making it easier to find a move which fixes a portion of the cube while leaving the rest alone. The same is true here. (Note that composition of group operators is read from right to left.)
A useful commutator, X = V2^-1 . H1^-1 . V2 . H1 (first row right, second column down, first row left, second column up) introduces a 3-cycle among 1, 2, and 14:
*14 *1 3 4
5 6 7 8
9 10 11 12
13 *2 15 16
So V2.X.X produces the desired swap of 1 and 2, but has messed up the column:
[2 1] 3 4
5 *14 7 8
9 *6 11 12
13 *10 15 16
But, another three-cycle can be used to correct this. Let Z = V2^-1 . H3^-1 . V2 . H3, which looks like this:
1 2 3 4
5 *10 7 8
*6 *9 11 12
13 14 15 16
We just need to move the '10' into position, perform the cycle, and then back out again. That means something of the form Y^-1.Z.Y, where Y = V1^-1 . H4^-1. Here's Y alone:
5 2 3 4
9 6 7 8
14 10 11 12
1 15 16 13
which screws up a bunch of stuff, but here's Y^-1.Z.Y:
1 2 3 4
5 *10 7 8
9 *14 11 12
13 *6 15 16
which is a nice well-behaved three-cycle, exactly the one we want to patch up V2.X.X. Putting it all together, Y^-1.Z.Y.V2.X.X =
2 1 3 4
5 6 7 8
9 10 11 12
13 14 15 16
or in word form: H4.V1.V2.V2.V2.H3.H3.H3.V2.H3.V1.V1.V1.H
2.H1.H1.H1.V2.H1. There might be a shorter word for the same permutation, but at 33 moves we were not likely to find this one by brute force any time soon.
But, this is sufficient to show that the slide moves generate the whole symmetric group S_16, since we can generate any other desired transposition in the same way, and the transpositions are generators for S_16.
How could we encode the directed search I performed by hand, into a computer algorithm for finding efficient (but not necessarily minimal) sets of moves for a given permutation?
|Saturday, May 11th, 2013|
|Why is 50% the limit?
In today's Star Tribune, an orchestra board member makes the case that musician salaries must be cut
Deficits will continue to grow unless we are able to address cost savings in our musicians’ contract, since their direct compensation makes up nearly 50 percent of the orchestra’s total expenses.
Nearly 50 percent! Good heavens! I'll be generous and blame the Star Trib itself for the sub-head "The musicians are half the cost, and that can’t continue." But even so, why shouldn't
musicians--- you know, the ones that actually form the orchestra--- be more than 50% of the budget?
This is an awful way to try to make your case. (The board's web site trying to compare orchestra salaries to PhD-holders is almost as bad.) It would be better to state--- as the web site does--- that 80% of the budget is "musicians and concert-related costs." Even so, it would be refreshing to see an honest breakdown of what it really costs to have an orchestra--- not why the current cost structure of the orchestra doesn't work.
|Tuesday, May 7th, 2013|
|Towards a Taxonomy of Match-3 Games
Field: square lattice, hexagonal lattice, freeform, 1-d
Moves: slide (15-puzzle style), rotate around lattice "great circle", rotate around interior point, swap, drop (singles or groups, with restricted placement at edges), place (arbitrary free location)
Matching result: promote/build (objects are combined to a next-tier object), clear
Minimum match size: 3, 4, 5+
||Puzzle Pirates "Navigation" (cylindrical topology), PopCap Chuzzle
||Puzzle Pirates "Foraging", KadoKado "Binary" (match-4)
||PopCap Bejeweled, Puzzle Quest, Puzzle Pirates "Bilging"
||PopCap Zuma (1-d, single unit), KadoKado "Paradice" (multiple units in parallel, match-4), KadoKado "Drakhan" (single unit, freeform), Puzzle Pirates "Sailing" (two-unit), Dr. Mario (two-unit, match-4)
||PopCap Alchemy (match-6)
||Naturalchimie (2-unit drops)
||Spryfox Triple Town
I am sure I have seen a "clear"ing game with the slide-to-empty-space mechanic, but I cannot come up with it. "Alchemy" is something of a cheat.
I am less sure that the "promote" row can be filled in. So many games use the swap mechanic that I feel like there must be a "build+swap" game but I can't think of one.
One obvious variation is to perform rotations around the center on a square grid. I.e., the center rotation would move 4 squares, the one outside that would move 12 squares, the next ring has 22 squares.
|"30 Greatest Orchestral Works"?
The modern orchestra's not all that old. If you want to list greatest paintings you can go at least back to the 1500's. Greatest literature? Much further.
So I saw a "Great Courses" ad for their "30 Greatest Orchestral Works"
and was a bit discomfited to realize that there was nothing more recent than 1953 on the list. It starts in the 1720's with Vivaldi and Bach, but ends in the 1953 with Shostakovich's Symphony No. 10. (And a sad lack of Sibelius...) So, 230 years of orchestral works == about one "greatest" every eight years.
Is it plausible that we have gone 60 years without any great orchestral music?
Possible, certainly. A nearly equal span of time passed between the Bach and Mozart pieces Dr Greenberg chose. And the rise of all the strains of popular music has certainly diverted some energy and talent from the orchestral tradition.
But no movie composers? No postwar modernists? None of the Jazz musicians who have tried their hand? I would think it shocking for any great literature survey to cut off the last 60 years of work by ending with "Invisible Man" or "The Old Man and the Sea."
I can't decide whether this is a deliberate critical choice, a preference for honoring dead composers over live ones, or just a failure to engage.
|Sunday, May 5th, 2013|
Google searches for "Netflix X" where X is a movie title usually find the Netflix page for that movie, even though their robots.txt prevent it being searched. (Not too surprising--- if there are enough links, Google can find it even if it can't scan the page itself.)
So out of curiousity I took a look at robots.txt and not only is it commented but it also has a disabled portion listed:
# Uncomment this when we start generating sitemaps again.
has a ton of boilerplate text that obviously came with the web server or framework.
There are exceptions: http://cnn.com/robots.txt
doesn't have any comments. http://facebook.com/robots.txt
|Friday, May 3rd, 2013|
|Finding all the Pythagorean triples
My interest was sparked by this Quora question: How would you find all the Pythagorean triplets in an array of N numbers?
The first answer was the straightforward O(N^2) examination of all pairs of numbers. It seemed like there might be a better way. One of the comments initially suggested O(N^2) was probably the best possible, because of its similarity to 3SUM
, but I knew that Pythagorean triples were sparse (and had structure) so there might be a way to beat the "generic" algorithm.
In fact primitive Pythagorean triples have a quite lovely structure: they can be generated in a ternary tree
using a set of three matrices. (In two different ways, no less! The second set of matrices was only discovered in 2008.) There are several implementations of this idea on Rosetta Code
(often contrasted with the naive approach.) Primitive triples are those whose three elements have no common divisor.
We can use this structure to do better than O(N^2), under certain conditions.
Pick the largest element of N, call it L. Using depth-first search on the ternary tree, generate all primitive Pythagorean triples with hypotenuse length <= L. Note that this method of generation always produces larger hypotenuses in the children of each node, so we can effectively prune our search. There is a result from the turn of the century which says that the number of primitive Pythagorean triples <= L is, in the limit, a constant fraction of L (in fact 1/2*pi). So, the depth first search takes time O(L), because we generate a unique triple each step, and prune no more than 3x the number of valid triples.
How long does it take us to generate all triples from just the primitive ones? Well for (3,4,5) we create an additional L/5 triples. For (5,12,13) we create an additional L/13 triples. I claim that this is bounded by L*H(L), where H(k) = the k'th element in the harmonic series (i.e., 1 + 1/2 + 1/3 + 1/4 + ... + 1/k.) A little handwaving is required here because some hypotenuses appear in more than one Pythagorean triple. I was not able to find a reference online confirming my guess about this bound on the number of Pythagorean triples. (Mathworld cites only the limit result for the number of primitive triples.
) However, using OEIS's list of the number of triangles
I can verify that L*H(L) =~ L*log(L) is a good bound up to 10^12.
This process produces all the Pythagorean triples with no repeated elements. So, for our algorithm we put all elements on N into a hash table. (Note that randomized algorithms can produce a perfect hash in O(N) time, if we're worried about that aspect.) Then iterate through all Pythagorean triples with hypotenuse <= L, and check whether all three elements are in the hash table, which is a constant-time operation. Thus the total run time is O(L log L).
If N is O(L) then this algorithm is much better than O(N^2). That is, as long as the number of elements in the set is proportional to the largest number--- or even somewhat worse--- we win. The naive algorithm is better if there are only a few, large numbers. I coded up both in Python (they are just a few lines each) and ran a handful of experiments (times are in seconds:)
L N quadratic tree
1000000 1000 0.21 2.18
1000000 2000 0.83 2.22
1000000 4000 3.37 2.20
2000000 4000 3.39 4.82
2000000 6000 7.73 4.95
A possibly interesting follow-up question is which algorithm parallelizes better. Both algorithms have pretty trivial partitionings (tree sub-branches vs. subsets of the pairings.) With an unbounded number of processors the "quadratic" algorithm can be made constant-time, but the tree algorithm is not.Code on pastebin
(because I'm not one of the cool kids on github.)
|Tuesday, April 16th, 2013|
|Python programming problem
Suppose you have a set A and you want all possible ordered triples of elements in A. In Python you can just do
for x in itertools.product( A, repeat = 3 )
Now, what if A has a special element X and you want only the ordered triples that include at least one X. What's the best way of doing so? (Assuming we want to pick only among the implementations which don't generate all triples and then filter.)
I was thinking of
A = complete set
X = mandatory element
Aprime = A - X
for i in xrange( 0, 3 ):
allowed = [ Aprime ] * i + [ [ X ] ] + [ A ] * ( 3 - i - 1 )
for x in itertools.product( *allowed ):
but this seems a bit indirect (of course, I'm allowing for the general case here.) The idea is to iterate over (X, any, any), then (not X, X, any) then (not X, not X, X) which should cover all possibilities exactly once.
|Monday, April 15th, 2013|
One branch of theoretical computer science looks at "circuit complexity", studying the size and depth of boolean logic circuits necessary to produce a particular function. A puzzle in this area is whether we can invert three binary digits using just two inverters
(but as many AND and OR gates as we want.)
The answer (in the affirmative) actually shows that all 88
3-bit to 3-bit functions can be represented using at most two inverters. Given A, B, C, and not-A, not-B, not-C, we can construct any arbitrary 1-bit function as an OR of ANDs, enumerating the cases where the output should be 1. Do this three times in parallel and you have all the 3-to-3 functions.
So, of those 16 million functions, how many can be represented with 0 or 1 NOT gates? This seems like it should be feasible to explore via brute search. The 4-bit case, with 2*1019
possible functions, would require some cleverness. (That is probably why many results focus on one-bit outputs such as decision problems. :)
Circuits with no inverters are referred to as "monotone"--- one circuit complexity result is that the "k-clique" problem (detection of a clique of size k in a graph) can be solved with a monotone circuit, but requires a superpolynomial number of gates.