Drawing Blanks

Premature Optimization is a Prerequisite for Success

Archive for March 2011

Guessing the cards: some answers

leave a comment »

https://bbzippo.wordpress.com/2011/03/17/guessing-the-color-of-the-card/

First of all, obviously, if you keep betting on red you will always guess exactly N/2 cards. But there are better strategies.

You can keep saying “red” and count cards. Once you know that reds are out, keep saying “black”. This strategy allows to guess about 26.9 cards out of 52 on average. (I calculated this analytically).

Or you can count cards and say “red” if there are more reds left and say “black” otherwise. With this strategy you will guess about 30 cards out of 52 on average. (I calculated this on a simulation).

Keep in mind, if you want to simulate card games, use a reliable shuffling algorithm.

Advertisements

Written by bbzippo

03/29/2011 at 3:08 am

Posted in Uncategorized

Guessing the color of the card

with one comment

Here’s a probability problem that I ran into while discussing some card game with my friends. It has a very natural formulation, but I have never encountered it before. And I still don’t have a solution.

There is a deck of N cards. N is even, N/2 cards are red and N/2 cards are black. The player turns the cards over one by one and tries to guess the color. All cards in the deck must be played.

What is the probability of at least K correct guesses?

Note that this is not equivalent to coin tosses (binomial distribution). The probabilities of guessing the color of the 1st card, 2nd card, etc. are not equal. The player is smart, the player has perfect memory, the player may have a strategy.

I am also interested in the expected number of correct guesses for the given distribution of cards that a player equipped with the best strategy can make. E.g. the last T cards are of the same color, but this fact is not known to the player. How many correct guesses should we expect?

Written by bbzippo

03/17/2011 at 3:32 am

Posted in math

Consistency and Soundness

leave a comment »

mean·ing·ful

–adjective

full of meaning, significance, purpose, or value; purposeful; significant

—Synonyms
See
expressive.

Let us deal with formal systems. Interesting formal systems. “Formal” means they consist of formulas. “Interesting” means the formulas are constructed from basic arithmetical relations connected by propositional relations and quantifiers. It can contain other relations too. It has rules of inference and a set of axioms that allow to define the set of provable formulas. And “define” means that the sets of rules and the axioms are decidable.

There are some important classes of formulas that are called Π1 and Σ1. Π1 are formulas of the form ∀n: P(n) where P is a decidable property. And Σ1 is the dual class: ∃n: P(n).

The system is called consistent if there is no provable formula f such that the system proves ~f. Note that consistency is a purely syntactical condition. Also note that inconsistent theories prove all formulas.

The system is called ω-consistent if there is no provable formula ∃n: f(n) such that the system proves ~f(n) for each natural number n. This condition is still syntactical because “natural number” means here “a finite string of a certain form”, e.g. 0, S(0), S(S(0)). If the system is ω-consistent just for decidable formulas f, it is called 1-consistent.

Obviously, ω-consistency implies 1-consistency which in turn implies consistency.

The system is called sound if it only proves formulas that when interpreted as statements about numbers  turn out true. The system is called complete if it proves any formula that represents a true statement. Soundness and completeness are semantic conditions: they require to interpret formulas and deal with truth values.

Interesting formal systems possess the following very neat properties that bridge syntax and semantics:

  • They are Σ1-complete. That is, if ∃n: P(n) is true then for some number k the system must indeed prove P(k).
  • 1-consistency is equivalent to Σ1-soundness. If we prove ∃n: f(n) then there must exist an n such that S(n) holds, since otherwise we could prove ~S(n) for each n.
  • consistency is equivalent to Π1-soundness. If we prove ∀n: f(n) then for each n, we prove f(n), so f(n) must be true, otherwise ~f(n) would be provable.

What’s curious, we normally consider Π formulas (universal statements) more strong and important than Σ formulas (existence statements). And apparently, if we don’t prove any existential falsehoods, we don’t prove any universal falsehoods either. But universal soundness is also implied by the simple, weak, purely syntactical condition of consistency. The latter fact was considered fundamentally important by Hilbert.

I haven’t said anything about Π1-completeness yet. Unfortunately, Π1-sound systems are Π1-incomplete. If we reformulate this as “consistent systems don’t prove all true Π1 statements” we immediately recognize that it’s a part of Gödel’s 1st incompleteness theorem. (Popular books often say that the above statement is Gödel’s theorem, but that’s not the case).

Related posts:

An unsound consistent theory

A ω-inconsistent extension of a complete theory

Systems that have enough knowledge about certain aquatic rodents are Π1-complete (no kidding).

Written by bbzippo

03/09/2011 at 5:36 am

Posted in math

From Compactness to non-standard models

leave a comment »

Alright, I have had enough reflection on Compactness and I want to smoothly transition to another topic. Nothing comes to mind but logic, so in this transitional post I’d like to quickly apply the Compactness Theorem to build a non-standard model of Arithmetic.

Let’s add a new constant symbol ω (omega) to Arithmetic. And let’s add an axiom schema: ω > 0, ω > 1, ω>2, … Any finite subset of this new theory has a model that interprets ω as some large enough natural number. Hence, by the Compactness Theorem, the whole thing has a model. That model is a model of Arithmetic and all arithmetic theorems are true in it. And in addition it contains a number ω that is greater than any standard integer. This is a non-standard model of Arithmetic.

Please note that the existence of this model has absolutely nothing to do with the Gödel’s incompleteness theorems or any other manifestation of incompleteness of Peano Arithmetic. I didn’t even say I was constructing my theory from Peano Arithmetic. We could take the complete True Arithmetic and achieve the same result. 

One curious thing about this new theory is that it proves all sentences of the form  ω > n, but it does not prove ∀n: ω > n. If it proved that, it would prove a contradiction, because ∀n ranges over all natural numbers defined by the theory, not just over the standard naturals. And the non-standard naturals must include S(ω) – the successor that is greater than ω. But if our theory proved a contradiction it would not have a model.

So this theory is ω-inconsistent. Per Wikipedia, “T is ω-consistent if it is not ω-inconsistent”. In the next post I’m planning to write about relationships between various consistency and soundness conditions. And Model Theory is an other melody.

Written by bbzippo

03/02/2011 at 7:45 am

Posted in math

Disappointed by MS

leave a comment »

Today MS pulled the plug on Live Mesh beta – the best remote access and file sync program for PC that also once upon a time promised to become a universal sync platform of the future. I used it mostly for remote access, to connect to work from home, to home from work, and to maintain computers located halfway around the globe. Well they gave us a warning way ahead of time. They told us Mesh beta would be replaced by the new Mesh which would be part of Windows Live Essentials 2011. And the new Mesh would be incompatible with the old Mesh. The Essentials also include updates to programs that I’m using: Live Mail, Live Writer, Photo Gallery. Those are all great and useful programs and I’ve been wanting to update them, but I could not. Because the Essentials is an all-in-one pack, and you don’t get to choose which programs you want to install. You must install the new Mesh if you want to use the new Mail. And did I mention that the new Mesh cannot update or automatically uninstall the old Mesh. You must uninstall the old Mesh manually, from each PC and from each user account. That is something that is very hard to do remotely especially while being connected to the remote PC via Live Mesh! So I waited until the last day.

Today I installed Windows Live Essentials 2011 on my home PC. Did I mention that the new Essentials were pushed as an “important Windows update”. I had to uninstall the old Mesh. The Essentials installer gave me two options: “Install all Windows Essentials” or “Update the currently installed components”. Of course I wanted to update the currently installed software because the Essentials include too many programs that I don’t use. Guess what. Since I uninstalled Mesh, it was not among the “currently installed components”. So the only remaining option was to install ALL components.

I realize that Microsoft wants to serve the mass consumer and streamline the experience for the majority. But to me, the mass consumer and the majority are the users of ipads, androids, and other linuxes. I am an elite consumer – a loyal user of Windows – and I deserve treatment and experience of luxurious quality. Because, as a Windows user, I am used to luxury. Hot smile

BTW, the new Mail is good, the new Gallery is good, the new Writer is good, and Bing Toolbar sucks.

Written by bbzippo

03/02/2011 at 6:51 am

Posted in Uncategorized