Showing posts with label Wissenschaft und Hausverstand. Show all posts
Showing posts with label Wissenschaft und Hausverstand. Show all posts

Tuesday, October 5, 2010

Telephone surveys simply explained



Of course, this simplifies the issue, so let's honor it with a bit more detail.

(Note: I'm neither a specialist on statistics nor on telephone surveys. I'm only applying some common sense here.)

Sources of errors and biases


By and large there are two kinds of errors that can distort survey results:
  • Errors due to parts of the population not being reachable by phone ("selection bias").
  • Errors due to people not answering honestly ("measurement error").


Selection bias

There are various reasons why people can't be reached. Some don't have phones. This includes relatively isolated parts of the population, such as indigenous tribes and Amish people, but also homeless people, children, and people with alternative life styles who don't use phones by choice. Others just don't pick up when they see unknown or suppressed numbers.

Most telephone surveys deal with this by just extrapolating -- that is, hoping that those who could not be reached would have answered similar to those who did pick up. How well this approach works depends largely on how strongly the question is correlated to the reachability. Ideally, there is no correlation at all.

For example, if the question is "Do you prefer strawberry or vanilla ice cream?", then it's quite likely that this is not strongly linked to the possession of a phone. Probably the percentage of homeless who like vanilla better is similar to the percentage amongst millionaires.

Asking "Do you own a phone?", on the other hand, is akin to asking "Are you asleep?". You will not get a [credible] "no" for an answer.

Most questions are somewhere in the grey area between these extremes. For example, "Did you book a holiday on the Internet this year?" has distorted results, because of those people who did, a certain percentage is probably on this very holiday when the survey is being made.

Similarly, political opinion polls are likely to be distorted, because preference for a particular party is strongly tied to the social group -- and so is reachability by phone. A party with a program that favors young educated people for example might underperform in such surveys, because young educated people have mobile phones with caller ID, and know how to put anonymous calls onto an ignore list.

Other kinds of surveys have similar issues with selection bias. For example, a survey that is conducted in a shopping mall by randomly approaching people might not exclude people without phones, but it preselects on "people who go to shopping malls", and additionally has some preselection against assertive people who are more likely to refuse to take part in the survey.

Finally, the real selection bias nightmare are surveys where people can sign up themselves to participate. This is something that many non-profit organizations suffer from. Not having the money for a professional survey, they often send out "Please take our latest survey" emails to friends and mailing list subscribers -- which is a group that's usually very far away from the average opinion on the topic at hand. It's a bit like asking your five best friends if they like you, and then extrapolating that all the world loves you: Good for your self-esteem, but not very realistic.

Measurement error

Measurement errors are simpler to explain: Some people just don't answer honestly or correctly. Again, how much of a problem this is depends on the question. For some questions, people don't have any incentive to lie. Take for example the already mentioned vanilla or strawberry ice cream preference.

There are other questions however where people are much more likely to lie. "Do you cheat on your wife/husband?" is a classical one. But also certain political parties are generally underrated in pre-election polls because people are too embarrassed to admit that they vote for them. For example, we all know that nobody would ever vote for the FPÖ (except for those 10-20% that regularly do so at the elections, but miraculously never show up in any polls).

Besides intentional lying there are also questions where people simply don't know the correct answer. Smokers for example tend to underrate how much money they really spend on cigarettes, and few people can really tell how many hours per day they spend on the Internet or watching TV.

And sometimes people just don't understand the question. Ask enough people whether they have ever seen a phishing attack, and you will find some who have never heard of "phishing" before, hear "fishing" instead, and answer "no" because no, they have never seen a fish attack anyone.

Handling errors and biases


In order to handle these errors and biases, surveys can for example do the following things:

Estimating known biases

In some cases, previous surveys compared to real data can indicate what biases are to expect. For example, by comparing pre-election polls with election results, it's possible to see patterns how real results differ from predictions. Once it is known that the aforementioned FPÖ generally is underestimated in surveys, it is possible to estimate how much the bias distorts the result and try to calculate it away.

Weighting sample to match demographics

As mentioned before, some groups of the population are underrepresented in those samples because they are less likely to be reachable by phone than others. Surveys that also ask for age, gender and similar attributes can weight the answers so that the overall result better matches the distribution in the population. For example, if it is known that 30% of the population are older than 50 years, but of the people who took part in the survey only 10% are, then those 10% get more weight.

Stratified random selection

When proper distribution amongst certain population groups is crucial, instead of randomly calling phone numbers, the survey participants can be selected randomly per group, and if necessary even be surveyed by different means. For example, when it's important to avoid that homeless people are underrepresented -- for example, for a discount store they might be an important group of the customers --, then a survey will randomly select 200 phone numbers, and in addition perform 100 random in-person surveys at a homeless shelter. It will have other selection biases, but can avoid those that are known to be important to a particular survey.

Estimating result confidence


Even if there were no sampling biases and no measurement errors, there would still stay the problem that only a small fraction of the population was asked. So how much can asking 10 people really tell us about the average person?

Let's look at the simple example from above in detail. We want to know whether Austrians prefer strawberry or vanilla ice cream. We randomly choose 10 phone numbers and call them. 1 person likes strawberry and 9 prefer vanilla. To certain news papers this would be enough evidence for saying that 90% of the Austrians prefer vanilla ice cream. But what do we really know? The only thing we know for sure at this point is that 9 of the 8000000 Austrians like vanilla ice cream. Or, more precisely, that 9 Austrians say that they like vanilla ice cream.

The simple truth is that after calling n people, all we know for sure is how these n people answered.

Calling another n could change the whole result. The next 10 people might all like strawberry, and suddenly the preference for vanilla plummets from 90% down to 45%. And this is where probability comes in.

It is, theoretically, possible, that we have accidentally called the only 9 Austrians who like vanilla ice cream. It is possible that all the other 7999991 Austrians hate it, and that the Austrian preference for vanilla ice cream is thus at 0.0001125%. But how likely is it that with only 10 phone calls we really managed to reach these 9? Right. It's about as likely as calling 10 random phone numbers and meeting 9 attractive, single lottery millionaires, which is less likely than winning in the lottery yourself, which is less likely than being struck by lightning.

I will spare you the mathematics, but the most likely explanation for the 9 out of 10 vanilla answers is that 90% of the Austrians prefer vanilla.

Since we only called 10 persons, the result is not very reliable, though. If we call 10000 people and 9000 of them say "vanilla", we would still guess that 90% of the Austrians prefer vanilla, but we would be more confident about our estimate.

Professional surveys will therefore indicate the margin of error, which indicates how reliable the results are, by giving the range within which the real result lies with a high probability, usually 95% or 99%. And here the problems start again, because it's not possible to calculate that range without making even more assumptions. For example, do you assume that any result between 0 and 8000000 Austrians preferring vanilla is equally likely, or do you assume that roughly half of the Austrians preferring vanilla and the other half strawberry is much more likely than nobody liking strawberry?

The truth is that even the estimate can only be estimated. It can be estimated relatively well, though, and it always holds that the larger the sample size, the higher the reliability of the result. So both with 9 out of 10 and with 9000 out of 10000 answers in favor of vanilla ice cream we estimate the real result to be "around" 90%, but with different confidence levels: With 9 out of 10 answers for vanilla, the real result is with a probability of roughly 99% between 50% and 100%. With 9000 out of 10000 answers, it's with a probability of roughly 99% between 88% and 92%.

Conclusion


Surveys can have their uses, but they aren't the absolute truth and should be taken with a grain of salt. At the end of the day, the only thing they tell us for sure is how the people who were called have answered.

-- Birgit

Monday, October 4, 2010

srorriM

Insight of the day: "Mirrors don't flip left and right, you know. They flip up and down, but most mirrors are turned sideways because otherwise it looks weird."

kR Birgit

Wednesday, April 14, 2010

Heppi Miel

Nur ein paar kleine Anmerkungen zu der bunten Box, in der bei McDonalds vor ein paar Tagen mein Happy Meal daherkam:
* Es gibt je nach Zählweise zwischen 5 und 7 Kontinente. Wenn man schon die Zählweise mit 5 Kontinenten als einzige Wahrheit anpreist, dann sind Europa und Asien bitte zusammen ein Kontinent namens Eurasien, und als Ausgleich vergessen wir bitte nicht auf die Antarktis.
* Übrigens gibt es diese 5 (bis 7) Kontinente nicht auf der Welt, sondern auf der Erde.
* Die Erde besteht mitnichten zu 70.7% aus Wasser; dies trifft lediglich auf die Erdoberfläche zu.
* "Eskimo" gilt im Allgemeinen nicht als Bezeichnung, sondern als Schimpfwort.
* Insgesamt sind in den Texten vier Rufzeichen zu viel, die durch Punkte ersetzt werden sollten.
* Der Text beim Rätsel sollte nicht heißen "Ordne jeweils das Lieblingsessen auf der linken Seite dem richtigen Landsmann auf der rechten Seite zu! Wer mag was am liebsten?", sondern "Ordne die im Allgemeinen als landestypisch angesehenen Speisen auf der linken Seite den klischeehaften Darstellungen von Einwohnern dieser Länder auf der rechten Seite zu."
* Ob das dann wirklich deren Lieblingsspeisen sind, sei dahingestellt.
* Übrigens ist Mais nicht afrikanischer, als Reis europäisch ist.
* Und über die Landkarte im Hintergrund schweige ich besser. (Dass Italien und Ägypten zusammengewachsen seien, wäre mir jedenfalls neu. Aber Moskau ist ja auch im Allgemeinen nicht östlich von Indien.)


Und noch zwei kleine Rechenübungen (unter Verwendung der unverbindlichen, nicht kartellierten Richtpreise, wie vorgefunden am 30.03.2010 im McDonalds Rankweil, Vorarlberg):

Rechenübung 1:
Variante 1:
Happy Meal (Hamburger, Kl. Portion Pommes, Kl. Getränk, Spielzeug): 3.49€
Variante 2:
Hamburger (1€), Kl. Portion Pommes (1€), Kl. Getränk (1€): 3€
Frage:
Was ist der effektive Preis des Spielzeugs?

Rechenübung 2:
0.25l Cola: 1€
0.4l Cola: 1.79€
0.5l Cola: 1.99€
Was ist an dieser Preistabelle seltsam?

lG Birgit

P.S.: Gut, zugegeben, Moskau ist östlich von Indien, um ungefähr 320 Längengrade.

Monday, March 8, 2010

Weltfrauentag / Frauen in der Informatik

Eigentlich hätte ich mir zum Weltfrauentag ja die Abschaffung des Weltfrauentags gewünscht. Aber nachdem es inzwischen auch den Männertag, den Hermaphroditen-Tag, den Transgender-Tag und sogar den Gender Awareness Tag gibt, kann ich wohl kaum meckern.

Also muss ich stattdessen meine übliche Predigt ablassen über die angebliche Benachteiligung von Frauen in der Informatik. Meine Zahlen sind ein paar Jahre alt und gerundet, aber viel dürfte sich nicht geändert haben.

Machen wir ein Schätzspiel:

Wie hoch ist der Frauenanteil unter den ProgrammiererInnen in der Industrie?
Etwa 10% bis 15%.

Wie hoch ist der Frauenanteil beim Lehrpersonal für Informatik (an der TU Graz)?
Etwa 10% bis 15%.

Wie hoch ist der Frauenanteil unter den TutorInnen und StudienassistentInnen für Informatik (an der TU Graz)?
Etwa 10% bis 15%.

Wie hoch ist der Frauenanteil bei den Informatik-Doktoratsstudienabschlüssen (an der TU Graz)?
Etwa 10% bis 15%.

Wie hoch ist der Frauenanteil bei den Informatik-Diplom- bzw. Master-Studienabschlüssen (an der TU Graz)?
Etwa 10% bis 15%.

Wie hoch ist der Frauenanteil bei den Informatik-StudentInnen (an der TU Graz)?
Etwa 10% bis 15%.

Wie hoch ist der Frauenanteil bei den Informatik-StudienanfängerInnen (an der TU Graz)?
Etwa 10% bis 15%.

Ich sehe einfach nicht, wo auf diesem Weg angeblich Diskriminierung stattfinden soll. Der einzige Punkt, an dem tatsächlich Diskriminierung passiert, ist da, wo nur 15% der StudienanfängerInnen weiblich sind -- aber das ist nun wohl wirklich deren freie Entscheidung.

Die vielleicht beeinflusst wird durch die gebetsmühlenartige Wiederholung der Behauptung, Frauen würden in der Informatik diskriminiert werden.

lG Birgit

Thursday, February 18, 2010

Magie

Martin: "Ich weiß noch einen Zaubertrick. Denk an eine transzendente Zahl zwischen 1 und 10!"
Birgit: "Okay..."
Martin: "Jetzt bilde die Ziffernsumme!"
Birgit: "Okay..."
Martin: "Aleph-Null!"

lG Birgit

Monday, February 8, 2010

Du willst es doch auch!

Auszug aus einem Angebot im Internet:
"Deswegen haben wir beschlossen, Dir eine kostenlose Testversion zur Verfügung zu stellen.

* Du kannst Dir mit dieser einfachen 21-Tage-Testversion (...) das komplette Programm sofort herunterladen.

* Heute musst Du nichts zahlen, bis auf die kleine 3,97 EURO Bearbeitungsgebühr. Das sind weniger als 4 EURO... (...)

* (...)

* Die heutige Bearbeitungsgebühr von läppischen 3,97 EURO wird Dir auf das Deluxe Paket (29,97 EURO) angerechnet, für die Du Dich bereits auf der letzten Seite entschieden hast... die verbleibenden 26 EURO (...) werden heute in 21 Tagen von Deiner Kreditkarte abgezogen."

Kleingedrucktes ist immer lustig, aber das hier hätte sich einen besonderen Award verdient.

Detail am Rande: Die 3,97 EURO beinhalten keine Mehrwertsteuer, sind genaugenommen also mehr als 4 EURO.

lG Birgit

Wusstet ihr schon...

Wusstet ihr schon...

..., dass teure Placebos besser wirken als billige?

lG Birgit

Saturday, February 6, 2010

Lotto

Lotto: Wer mitspielt, kann gewinnen; Wer nicht mitspielt, hat schon gewonnen.

lG Birgit

Thursday, February 4, 2010

Millionenfrage

Auf einer Freilandstraße sind 500m zwischen dem Ende einer 70km/h-Zone und dem Beginn der nächsten. Wenn man auf diesen 500m auf 100km/h beschleunigt und vor der nächsten Zone wieder abbremst, wieviel Zeit gewinnt man dann etwa gegenüber jemandem, der konstant mit 70km/h weiterfährt (unter Annahme idealer Beschleunigung, d.h. von 70km/h auf 100km/h in 0 Sekunden)?
A) 5 Sekunden
B) 6 Sekunden
C) 7 Sekunden
D) 8 Sekunden

Mit freundlichen Grüßen an alle, die auf besagtem Straßenstück schon einmal geglaubt haben, an meiner hinteren Stoßstange kleben zu müssen.

Birgit

Sunday, January 31, 2010

Gür... Gür... Gürkchen?

Vorschlag für eine Studie über das Suggerieren von Wörtern:

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

Versuchsanordnung:

Zuerst bekommt die Testperson folgende Wörter präsentiert und soll sich möglichst viele davon einprägen:
Pizza
Gürtel
Skelett
Möhre
Koffer
Nadel
Adresse
Fieber
Zukunft
sowie 10 weitere zufällig ausgewählte Wörter

Nach ca. 15 Minuten Pause bekommt die Testperson folgende Aufgabe:

Sie werden nun jeweils drei Anfangsbuchstaben präsentiert bekommen. Ergänzen Sie diese auf ein Hauptwort (Nomen), verwenden Sie aber bitte keine Eigennamen. Beispielsweise können Sie "Kat" ergänzen auf "Katze", "Katalog", "Kathete", aber nicht auf "katholisch" (kein Nomen) oder "Katharina" (Eigenname). Verwenden Sie bitte das erste Wort, das Ihnen einfällt.
Möh...
Gür...
Zuk...
Ske...
Piz...
Adr...
Nad...
Kof...
Fie...

Erwartetes Ergebnis:
Es ist zu erwarten, dass bis zu 90% der Probanden die Wörter auf die zuvor eingeprägten Wörter ergänzen werden. Natürlich nur auf Grund der vorherigen Suggestion.

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

Auch so kann man "Wissenschaft" betreiben.

lG Birgit

Thursday, January 21, 2010

Schmäääärz

Uuuuuund das Wort des Tages (aus einer Abgabe zu "Entwurf und Analyse von Algorithmen") lautet: Stäck.

lG Birgit

Tuesday, January 19, 2010

Kuhhandel-Probleme

Vorbemerkung: 0 ist in diesem Artikel keine natürliche Zahl, und alle Teilmengen sind nicht-leer.

Gewisse Aspekte von "Kuhhandel" lassen sich folgendermaßen vereinfacht darstellen:

Es gibt 10 Karten: A, B, C, D, E, F, G, H, I, K. Jede dieser Karten hat einen Wert. (Im Originalspiel: 10, 40, 90, 160, 250, 350, 500, 650, 800, 1000.) Am Ende des Spieles hat jeder Spieler einige dieser 10 Karten. Die Punkte für den Spieler ergeben sich nun aus (Summe der Kartenwerte) * (Anzahl der Karten).


Beispiel:

  • Birgit hat B (40) und F (350). Punkte: (40 + 350) * 2 = 780.
  • Martin hat A (10), C (90) und E (250) Punkte: (10 + 90 + 250) * 3 = 1050.


Ein weiteres Beispiel:

  • Birgit hat C (90) und D (160). Punkte: (90 + 160) * 2 = 500.
  • Martin hat G (500). Punkte: (500) * 1 = 500.

Wie wir im zweiten Beispiel sehen, kann es bei diesen Kartenwerten also ein Unentschieden geben.

Fragestellung

Man finde Werte für die 10 Karten, sodass kein Unentschieden möglich ist und der höchste Wert minimal ist.

Mathematisch formuliert: Man finde eine 10-elementige Menge natürlicher Zahlen mit möglichst kleinem maximalen Element, die folgende Bedingung erfüllt: Es existieren keine zwei disjunkten Teilmengen, sodass (Anzahl der Elemente in der Teilmenge) * (Summe der Elemente in der Teilmenge) für beide Teilmengen dasselbe Ergebnis liefert.


Oder: Man finde eine 10-elementige Menge natürlicher Zahlen mit möglichst kleinem maximalen Element, die folgende Bedingung erfüllt: Die Wertigkeiten ((Summe der Elemente) * (Anzahl der Elemente)) von 2 Teilmengen sind höchstens dann gleich, wenn mindestens 1 Element in beiden Teilmengen vorhanden ist.


Hinweis: Es gibt mindestens eine Lösung (1,10,100,1000,...,1000000000), daher muss es auch eine kleinste Lösung geben.

Bekannte [nicht optimale] Lösungen und Nichtlösungen

  • 1,10,100,1000,...,1000000000 ist eine Lösung
  • 1,2,4,8,...,512 ist keine Lösung: {2,4,16} = 66 = {1,32}
  • 1,2,3,5,11,17,31,112,171,326 ist die Greedy-Lösung
  • 1,4,6,7,8 ist eine optimale Lösung für n=5
  • 1,4,7,12,13,14 ist eine optimale Lösung für n=6
  • 1,2,3,13,19,22,25 ist eine optimale Lösung für n=7
  • 1,2,3,22,32,38,42,45 ist eine Lösung für n=8
  • 1,4,7,23,32,40,41,42 ist eine optimale Lösung für n=8
  • 1,2,3,20,43,70,76,79,82 ist eine Lösung für n=9
  • 1,2,3,43,61,70,76,79,82 ist eine Lösung für n=9

Verallgemeinerte Fragestellungen

  • Man finde Kartenwerte für 10 bzw. n Karten, sodass kein Unentschieden möglich ist und der höchste Kartenwert möglichst klein ist. Und/oder:
  • Man finde einen Algorithmus, der obiges Problem (für n=10) in < 24 Stunden berechnet.
  • Vermutung (Birgit): Die Fragestellungen (*) und (**) (siehe unten) sind beide NP-vollständig (und folglich die obige erst recht).


(*): Gegeben eine Menge von n Zahlen. Man bestimme, ob es zwei Teilmengen dieser Menge mit gleichem Ergebnis ((Summe der Elemente) * (Anzahl der Elemente)) gibt.


(**): Für eine Zahl n bestimme man die kleinste Zahl Z(n), für die eine Menge von n natürlichen Zahlen existiert mit Z(n) als größter Zahl, sodass in der Menge keine Teilmengen mit gleichem Ergebnis ((Summe der Elemente) * (Anzahl der Elemente)) existieren.


(Problem posed by: Martin Windischer)


lG Birgit

Thursday, January 14, 2010

Warum weniger Sicherheit manchmal mehr ist
Oder: Wie fälsche ich den Wohnungsschlüssel meines Nachbarn?

Hier ein Beitrag um zu beweisen, dass Informatik sich mit viel mehr beschäftigt als nur mit Computern. Beispielsweise auch mit ganz profanen Türschlössern.

Nehmen wir an, jemand besitzt eine Maschine zum Fräsen von Schlüsseln, und beliebig viele Rohlinge. Um nun einen Schlüssel für ein Schloss anzufertigen, dessen Code man nicht kennt, kann man natürlich einfach alle Möglichkeiten durchprobieren, bis man den korrekten Schlüssel erwischt hat. Bei einem klassischen österreichischen(*) Türschloss sind das etwa 100000 mögliche Kombinationen, nämlich 5 Stellen mit Werten zwischen 0 und 9. Die Schlüssel lassen sich entsprechend bezeichnen mit 00000 bis 99999.

Entsprechend wird man durchschnittlich 50000.5 Schlüssel anfertigen müssen, bis man den richtigen erwischt. Wenn man für einen Schlüssel und das Ausprobieren desselben eine Minute benötigt, dann dauert das (im Durchschnitt) etwa 35 Tage -- essen und schlafen noch nicht mitgerechnet. Für eine praktische Umsetzung ist das viel zu langwierig, daher "sicher". Außerdem fällt es auf, wenn jemand 35 Tage lang vor einer fremden Wohnungstür sitzt und Schlüssel ausprobiert.



Nehmen wir nun aber an, die Wohnung befindet sich in einem Mehrparteienwohnhaus mit einem Schließsystem und einer gemeinsam gesperrten Haupteingangstür. Das heißt, jeder Bewohner hat einen Schlüssel, der seine eigene Wohnung sperrt und die gemeinsame Tür.

Nun müssen wir uns ein wenig damit befassen, wie so eine Schließanlage funktioniert. Beginnen wir einmal mit der Funktionsweise eines normalen Zylinderschlosses. Dieses besteht aus Federn und Stiften. Der richtige Schlüssel drückt die Stifte genau so weit hinein, dass der Spalt zwischen Feder und Stift genau an der Kante zwischen Schloss und drehbarem Zylinder ist; Nur dann kann der Zylinder gedreht werden. Die nächsten Bilder verdeutlichen diese Beschreibung.

Skizze 1: Zylinderschloss

Skizze 2: Zylinderschloss mit richtigem Schlüssel

Skizze 3: Zylinderschloss mit falschem Schlüssel


Um zu erreichen, dass eine Tür von mehreren verschiedenen Schlüsseln gesperrt werden kann, werden statt der durchgehenden Stifte solche Stifte verwendet, die sich aus mehreren Teilen zusammensetzen. Der Zylinder kann dann gedreht werden, wenn sich an jeder der fünf Schlüsselpositionen eine der Spalten im Stift an der Kante zwischen Zylinder und Schloss befindet. Im Folgenden sind Skizzen von einem Schloss, das mit zwei Schlüsseln gesperrt werden kann.


Skizzen 4 und 4a: Zylinderschloss mit zwei sperrenden Schlüsseln

Die beiden Schlüssel in Skizzen 4 und 4a haben die Nummern 85173 und 85143 -- beschriftet von links nach rechts, größere Ziffern bedeuten längere Stifte / tiefere Kerben. Offensichtlich müssen vier der fünf Stellen gleich sein.

Bei dem Schloss aus Skizzen 4 und 4a gibt es zwei mögliche Schlüssel, folglich könnte man es als gemeinsam gesperrte Tür für zwei Wohnungen verwenden. Für mehr Wohnungen braucht man entsprechend mehr unterteilte Stifte. Beispielsweise könnte man den bereits geteilten vierten Stift ein weiteres Mal unterteilen, sodass die drei Kombinationen 85143, 85173 und 85193 möglich sind. Oder man könnte einen weiteren Stift teilen, zum Beispiel den ersten, um die Kombinationen 25143, 25173, 85143 und 85173 zu erhalten.



Kurz und gut, wie auch immer man es anstellt, die Schlüssel, die die gemeinsame Tür sperren, weisen ein Muster auf. Und genau das nutzen wir nun aus.

Nehmen wir an, ich besitze einen gültigen Schlüssel für die gemeinsam gesperrte Tür -- nämlich den meiner eigenen Wohnung. Habe dieser zum Beispiel die Nummer 12345. Um herauszufinden, wie das Schloss der gemeinsamen Eingangstür aufgebaut ist, brauche ich lediglich 45 Schlüssel, nämlich jene, die entstehen, wenn man jeweils nur genau eine Stelle verändert. Wenn 12345 ein gültiger Schlüssel ist, dann erfahre ich durch Durchprobieren der Schlüssel 22345, 32345, 42345, ..., 92345, 11345, 13345, ..., 19345, 12145, 12245, ..., 12945, ...... 12349 die Positionen aller Spalten in den Stiften des gemeinsamen Türschlosses. (Von den vier unveränderten Stellen weiß ich mit Sicherheit, dass ein Spalt an der richtigen Stelle ist. Falls der Schlüssel mit einer veränderten Position nicht sperrt, muss also diese eine veränderte Stelle diejenige sein, bei der der Stift nicht in einer richtigen Position ist. Sperrt der Schlüssel, so ist auch für die veränderte Stelle ein Spalt im Stift vorhanden.)

Aus den Positionen dieser Spalten in den Stiften lassen sich nun wiederum alle Schlüssel konstruieren, die das Schloss sperren, selbst wenn sich diese noch nicht unter den durchprobierten Schlüsseln befanden. Wenn 18345 und 12347 nämlich beide sperren, dann muss auch 18347 ein gültiger Schlüssel sein.


Jetzt bleibt zu hoffen, dass die gemeinsame Tür so gebaut ist, dass möglichst wenige Schlüssel sie sperren. Das ist auch üblicherweise der Fall. Bei 8 Wohnungen wird man zum Beispiel drei Stifte in je zwei Teile teilen, bei 24 Wohnungen einen vierten Stift in drei Teile zerlegen. Bei 37 Wohnungen wird man nicht umhin kommen, das Schloss so zu bauen, dass mindestens 40 Schlüssel sperren. (Man kann keinen Stift in mehr als 10 Teile teilen. 37 ist eine Primzahl, 38 = 2*19 enthält einen zu großen Primfaktor, 39 = 3*13 ebenso, und 40 = 2*2*2*5 ist möglich.)

Wie auch immer, im Normalfall wird es etwa gleich viele mögliche Schlüssel geben wie Wohnungen. Und Wohnblöcke mit mehr als 50 oder 100 Wohnungen sind nicht gerade häufig. Folglich fertigt man nun diese höchstens 100 möglichen Schlüssel an, und einer davon wird die Nachbarwohnung sperren.

Wenn man wie oben etwa 1 Minute für jeden gefertigten Schlüssel annimmt, kommt man mit den 45 + ca. 100 Schlüsseln auf etwas mehr als zwei Stunden Arbeit. Das ist etwas, wofür der Nachbar noch nicht einmal auf Urlaub sein muss. Soviel zum Untertitel.



Setzen wir den Gedanken noch ein wenig fort. Nehmen wir an, jemand, der nicht einmal einen Wohnungsschlüssel für eine andere Wohnung im gleichen Haus besitzt, will einen Schlüssel fälschen. Sobald wir einen gültigen Schlüssel für irgendeine Wohnung im Haus haben (oder auch nur für die gemeinsame Eingangstür), kann mit der oben beschriebenen Methode offensichtlich recht effizient auch ein Schlüssel gefunden werden für diejenige Wohnung, in die eingebrochen werden soll. (Entsprechend müssten eigentlich jedes Mal, wenn irgendwer seinen Schlüssel zu einer Wohnung verliert, die Schlösser bei allen Wohnungen ausgetauscht werden.)

Wie lange dauert es nun also, einen Schlüssel für die gemeinsame Eingangstür zu finden? Offensichtlich ist das leichter als bei einer einzelnen Wohnung, da es mehr gültige Schlüssel gibt. Nehmen wir an, es gibt k Wohnungen, und das gemeinsame Schloss lässt sich von genau k Schlüsseln sperren. Dann braucht man im Durchschnitt 100001/(k+1) Versuche, bis man einen dieser Schlüssel erraten hat.

Um in eine bestimmte Wohnung einzubrechen braucht man nun also im Durchschnitt 100001/(k+1) + 45 + (k+1)/2 Schlüssel. (Erraten eines Schlüssels für die gemeinsame Tür + Bestimmen des Aufbaus des gemeinsamen Schlosses + Erraten des richtigen der k gültigen Wohnungsschlüssel.) Im Gegensatz zu einer einzelnen Wohnung (für die man wie oben beschrieben im Durchschnitt 50000.5 Schlüssel braucht), benötigt man für eine Wohnung in einem Wohnblock mit 2 Wohnungen nur noch durchschnittlich 33380.17 Schlüssel, also um 33% weniger. Bei 10 Wohnungen benötigt man nur mehr 9141.5 Versuche, also 81% weniger als bei einer einzelnen Wohnung.

Einige weitere Zahlen:










Anzahl WohnungenDurchschnittliche VersucheSicherheitsverlust in Prozent
233380,1733,24
325047,2549,91
420047,759,91
516714,8366,57
109141,581,72
204817,4590,37
502031,395,94
1001085,6197,83
200643,0298,71


Bei 446 Wohnungen schließlich benötigt man durchschnittlich nur noch 492 Schlüssel, etwa 8 Stunden und somit um 99% weniger als wenn es keine gemeinsame Eingangstür gäbe.

Gibt es noch mehr Wohnungen im Wohnblock, so steigt die Schwierigkeit langsam wieder, da zwar die Eingangstür nun leichter zu erraten ist, danach aber umso mehr gültige Schlüssel existieren.

Daraus folgt, passend zum ersten Titel: Obwohl bei einer gemeinsamen Eingangstür zwei versperrte Türen zwischen dem Einbrecher und der Wohnung stehen statt nur einer, ist die Sicherheit geringer. So gesehen wäre es am sichersten, gar keine gemeinsame Eingangstür zu haben, oder zumindest eine, bei der jeder Schlüssel sperrt. (Natürlich nur aus informatisch-theoretischer Sicht. Praktisch braucht man bei zwei Türen trotzdem einmal öfter das Brecheisen als bei einer.)


Noch allgemeiner betrachtet kann man statt der 100000 Möglichkeiten ein Schlüsselsystem annehmen, in dem es n mögliche Schlüssel gibt (beispielsweise durch zusätzliche Stellen oder mehr Ziffern pro Stelle). Sei wie oben k die Anzahl der Wohnungen im Wohnblock. Dann beträgt die durchschnittliche Anzahl der Versuche (n+1)/(k+1) + (k+1)/2 + C, wobei C die Konstante für das Austesten des gemeinsamen Schlosses ist, im obigen Sonderfall also 45. Die geringste Sicherheit besteht dann genau dann, wenn die Anzahl der Wohnungen k gleich ((Wurzel[2*n+2])-1) ist, und beträgt dann ((Wurzel[2*n+2])+C). Größenordnungsmäßig reduziert sich die Schwierigkeit im schlimmsten Fall also von O(n) auf O(Wurzel[n]).



Übrigens besteht die Reaktion der Hersteller von Schließsystemen bislang nicht im Entwurf neuer Systeme, sondern schlicht und einfach in der Erhöhung der Anzahl der Möglichkeiten. Mit bis zu 8 seitlichen Einkerbungen produziert Winkhaus beispielsweise ein Schloss mit 256000000 Möglichkeiten. Andere Schließsysteme verwenden Magneten für zusätzliche Stellen.

Eine der wenigen Möglichkeiten, die tatsächlich das Grundproblem beheben, sind elektronische Schließsysteme, bei denen einfach jeder Schlüssel eine Nummer hat und jedes Schloss eine Liste derjenigen Nummern speichert, bei denen es sperren soll.



lG Birgit
... die übrigens keine Schlüsselfräse besitzt.

(*) Deshalb österreichisch, weil jedes Land etwas andere Schlüsselnormen verwendet. Die meisten Prinzipien dieses Artikels funktionieren aber auch dort.

P.S.: Als Zuckerl für alle, die bis hierher gelesen haben: http://www.xkcd.com/538/

Dritte Lager und Prozentrechnung

Apropos dritte Lager: Eine Musterübung in Sachen Prozentrechnung:

Eberau hat 500 Einwohner.
Es soll ein Asylheim mit 300 Plätzen gebaut werden.

Argumentationslinie des dritten Lagers: "Die Anzahl der Asylwerber wäre 60% der Bevölkerung!"

Zugegeben, man kann obige Aussage mit viel gutem Willen so lesen, dass sie nicht völlig falsch ist. Aber ich bin trotzdem für 37.5%.

lG Birgit

Wednesday, January 13, 2010

Radiosender

Nach dem Schreiben dieses Beitrags habe ich über das Thema noch ein wenig nachgegrübelt und bin zu dem Schluss gekommen: Eigentlich ist es dumm von den Radiosendern, sich alle auf dieselbe Zielgruppe zu stürzen.

Nicht nur, dass die Kosten eines Senders ziemlich konstant sind, unabhängig von der Hörerzahl, wogegen die Werbeeinnahmen (vermeitlich) mit der Anzahl der Hörer wachsen. Wenn nun drei Sender mehr oder weniger dieselbe Musik spielen, also dieselbe Zielgruppe haben, teilen sich die Hörer auf die drei Sender auf. In Summe über die drei Sender hat man nun also höhere Kosten bei gleichen Einnahmen. Aber gut, für den zusätzlichen Sender, der sich zu den schon vorhandenen in die Zielgruppe dazuhineindrängt, mag sich das trotzdem noch auszahlen.

Nein, darüber hinaus sinkt die Summe der Werbeeinnahmen der drei Sender dadurch, dass sie dieselbe Zielgruppe haben. Warum?

Nehmen wir ein Beispiel. Nehmen wir eine 23-jährige Studentin aus Graz, die beim Autofahren meist Radio hört. Früher meist Antenne Steiermark. Heute Antenne Steiermark, Ö3 und Kronehit, weil die drei eh fast die gleiche Musik spielen. Was also mache ich, wenn auf einem der drei plötzlich Werbung daherkommt? Richtig! Ich schalte weiter zum nächsten. Wenn dort fünf Minuten später auch Werbung kommt? Weiter zum dritten! Wenn dort zufällig gleichzeitig Werbung läuft? Dann eben wieder zum ersten, dort ist sie nämlich inzwischen vorbei.

Ich als Hörer finde das ja ganz wunderbar: Ich höre nur mehr Musik und keine Werbung mehr. Zugegeben, Ö3 hat schlechtere Verkehrsnachrichten (da für ganz Österreich statt nur Steiermark), und Kronehit ärgert mich damit, dass ich von den Moderatoren dauernd geduzt werde. Aber das sind vernachlässigbare Übel.

Problem: Wenn andere Hörer das genauso wunderbar finden wie ich, werden die Werbeeinnahmen für alle drei Sender recht rasch gegen Null gehen.

Leider leider hängen Werbeeinnahmen halt doch nicht nur von der Höreranzahl ab.

lG Birgit

Friday, January 1, 2010

Euklidscher Algorithmus -- Mathematiker vs. Informatiker

Ziegler, Mathematische Grundlagen der Kryptographie (für Mathematiker): "Und bei endlichen Körpern funktioniert der euklidsche Algorithmus ganz gleich wie gewohnt, das ist so einfach dass ich das jetzt glaub ich nicht noch einmal vorführen muss, oder?"

Rijmen, Angewandte Kryptographie (für Informatiker): "Und bei endlichen Körpern kann man den euklidschen Algorihmus auch anwenden, aber das ist ein bisschen zu kompliziert für uns, das werde ich jetzt nicht vorführen."

lG Birgit

Tuesday, December 29, 2009

Avatar -- Aufbruch nach Pandora

[Achtung Spoiler]

"Avatar -- Aufbruch nach Pandora" hätte sich redlich einen Platz in der Liste der deprimierendsten Happy Ends verdient. Warum? Erstens, auf beiden Seiten ist vermutlich gut die Hälfte der Bevölkerung draufgegangen, nebst weltlicher Dinge wie Heimat, Infrastruktur und Hab und Gut. Und viel schlimmer zweitens: Wenn dieses Mineral, das dort abgebaut wird, wirklich so wertvoll ist, dann kann man sich ausrechnen, wie lange es dauern wird, bis die Menschen zurückkommen -- mit größeren Atombomben. Auf der Seite der Na'vi dagegen sehe ich keine weiteren Ressourcen mehr, mit denen man sich noch einmal und effektiver verteidigen könnte.


Kommentare zum Film im Allgemeinen:

Die Geschichte ist im Wesentlichen schell zusammengefasst als 80% Dune, 10% Pocahontas und 5% "Der mit dem Wolf tanzt", erweitert um vielleicht 5% eigene Ideen. Im Großen und Ganzen hat man ein Dutzend Stereotypen genommen, ein wenig an die fremde Welt angepasst, und zusammen in einen Film geworfen. Die Charaktere sind, vielleicht mit Ausnahme des Protagonisten, um dessen persönliche Entwicklung es im Film ja geht, flach wie Fußmatten.

Nicht einmal ein anständiges Heldenepos mit erschütternden Selbstzweifeln, Trauer über den verlorenen Zwillingsbruder und Hin- und Hergerissenheit zwischen der Loyalität zu verfeindeten Seiten, gefolgt von mutigen Entschlüssen und heroischer Selbstaufopferung, ist gelungen. Die Trauer um den verstorbenen Zwilling wird abgehandelt als "Er sieht genauso aus wie mein Bruder." -- "Nein, er sieht aus wie du." -- "Hm.". Und über die Wandlung vom Verräter zum Volkshelden innerhalb von 10 Filmminuten brauchen wir auch nicht zu reden. Das war kein mutiger Entschluss, in der aussichtslosen Situation das Unmögliche zu wagen, das war "Übrigens, ich hatte da so eine seltsame Idee und bin mal eben von oben auf einen gefährlichen Raubvogel draufgesprungen.", gefolgt von einer peinlich absurden Rede, die selbst bei einem derart traumatisierten Volk nicht auf tosenden Applaus sondern auf schallendes Gelächter stoßen müsste.

Übrigens ließe sich der Film sehr einfach und effektiv in einen europäisch-sozialkritischen Film (mit ungewohnt vielen Special Effects) verwandeln, indem man ihn einfach direkt nach der Zerstörung des Heimatbaumes abschneidet, und das [deprimierende] Nachdenken dem Zuschauer überlässt. Über Geschmack lässt sich bekanntlich nicht streiten, aber mir persönlich gefallen Filme, die im Wesentlichen zwei Stunden lang Spannung aufbauen, um am Ende eine einzige Frage zu stellen -- und unbeantwortet zu lassen.


Von der etwas schwachen Geschichte abgesehen ist am Film und insbesondere den Special Effects nichts auszusetzen. Na gut, das ist untertrieben. Die Special Effects sind genial. Ebenso die Zukunftstechnologien, die auf der Bodenstation der Menschen zu sehen sind, von den futuristischen Bildschirm- und Eingabegeräten über die tragbaren Atemgeräte mit den großen Sichtfenstern bis hin zu den verschiedenen medizinischen und biologischen Apparaturen und den Hubschraubern und anderen Fluggeräten. Dazwischen immer wieder ganz unfuturistisch einfache Dinge, wie zum Beispiel gute alte Kaffeehäferl, Maschinengewehre und natürlich der Rollstuhl. Kurz und gut, eine der meiner Meinung nach realistischsten Zukunftsvisionen, die man in den letzten Jahren so gesehen hat.

Auch auf Seiten der Na'vi kommt der Realismus nicht zu kurz, der vor allem in den liebevoll und sorgfältig durchdachten Details beginnt. Beispielsweise haben die Na'vi, die an jeder Hand nur vier Finger haben, ein Zahlensystem zur Basis 8 (wie schlaue Menschen herausgefunden und hier in die Wikipedia geschrieben haben). Das gesamte Ökosystem des Planeten ist in sich stimmig, ebenso die gesellschaftliche Struktur und die Religion. Selbst der Flug mit vier Flügeln wirkt physisch sinnvoll, und der Kampf- und Jagdstil passt zum Körperbau. Einzig das scheinbar völlige Fehlen von Insekten ist ein wenig verwunderlich. Aber zugegeben, man kann es auch übertreiben.

Und natürlich ist verwunderlich -- aus biologischer Sicht, nicht aus cinematographischer --, dass die Na'vi so ungemein menschlich aussehen und sogar auf zwei Beinen gehen, in einer Welt, in der sonst alles auf sechs Beinen unterwegs sind. Wie groß ist schon die Wahrscheinlichkeit, dass die Evolution neben der Menschheit noch ein zweites Mal die ungemein dumme Idee hatte, irgendwelche Lebewesen auf zwei Beinen gehen zu lassen? Und selbst wenn, müssten die Na'vi dann nicht mindestens noch ein zweites Paar Arme haben, übriggeblieben vom Leben als Sechsbeiner? Selbst wenn man argumentieren wollte, dass Werkzeuggebrauch freie -- also nicht zur Fortbewegung verwendete -- Arme benötigt, selbst dann wäre ein Design mit vier Beinen und zwei Armen, ähnlich wie bei Zentauren, doch wesentlich sinnvoller. Aber wie gesagt, man kann es mit dem Realismus auch übertreiben.


Fazit: Die Geschichte ist ein bissl mau, aber die Computeranimationen und die davon erschaffene Welt muss man gesehen haben.

lG Birgit


P.S.: Bin ich wirklich die einzige, die sich fragt, warum Jake und Neytiri sich ganz profan abknutschen, anstatt wie sonst bei jeder passenden und unpassenden Gelegenheit mit ihren verlängerten Nervenfasergehirnverbindungsdingern "das Band" zu formen?

Friday, December 25, 2009

Understand

"You have not really understood a thing if you cannot explain it to your grandma."
-- A. Einstein

Tuesday, December 22, 2009

Cancer leads to the purchase of mobile phones!

There's an abundance of scientific studies that can be roughly summarized as: "People who own mobile phones more often have cancer than people without mobile phones, which means that mobile phones do cause cancer." Based on those studies I want to prove today that cancer leads to the purchase of mobile phones.

Let the rectangle below represent the population of the country/region where such a study was conducted, separated into owners of mobile phones (M) and people who don't own or use mobile phones (nM).


The abovementioned studies now say that among M, a higher percentage of the people has cancer than among nM. We draw two lines to represent this. The only important thing is that the line in the M-rectangle is higher than the line in the other one.


Let's now compare the percentage of people with cancer who own mobile phones to the same percentage among people without cancer. We label the distances as shown below.


Among cancer patients, the percentage of people who own mobile phones is:


Among peope without cancer, this percentage is:


Under the assumption that a > b, it can easily be shown that
holds true (for all positive values for x and y).

(This can also be easily shown with more words and less formulas: If a = b holds, it's obvious that the two compared percentages are equal. Let now the line for b "move downwards", then we see that the first percentage grows, whereas the second one shrinks.)

Thus it is shown that people who have cancer more often own mobile phones than people who don't have cancer.

With the same argumentation as in the beforementioned studies, we can therefore conclude that cancer leads to the purchase of mobile phones.

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

Wondering where's the catch? It's simply not legal to infer from "A and B often occur together" that "A leads to B". Sadly, many so-called "scientific" studies about cancer and mobile phones (and a dozen other popular topics) use exactly this train of thought.

Birgit Vera Schmidt

P.S.: I'll have another article about this topic some day.

Sunday, November 29, 2009

97%!

Aus dem Werbetonband in einem Schweizer Supermarkt:

"Heute um 14.99 Franken statt 29.99 Franken. Sie sparen über 97%!"

(Ursprünglich geposted am 13.07.2009 in meinem privaten Blog.)
lG Birgit