Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Туған күндердің ортақтығының ықтималдығы
Probability of shared birthdays
Ықтималдықтар теориясында, туған күн мәселесі n кездейсоқ таңдалған адамдар тобында кем дегенде екеуінің туған күнінің бірдей болу ықтималдығын анықтауға қатысты. Туған күн парадоксы – бұл тек 23 адамның болуымен аталған ықтималдық 50%-дан асып кететін, көңілге сыймайтын факт. Туған күн парадоксы – шындық парадокс: көзқарасыңда дұрыс емес сияқты көрінеді, бірақ шындығында дұрыс. Тек 23 адамның болуы туған күндердің 50% ықтималдығымен ортақтастырылуы таңқаларлық болғанымен, бұл нәтиже туған күндердің салыстырылуы әрбір мүмкін жұп арасында жасалатынын ескерсек, түсінікті болады. 23 адаммен = 253 жұпты қарастыру қажет, бұл жылдағы күндер санының жартысынан асып түседі. Туған күн мәселесінің нақты қолданылуына туған күн шабуылы деп аталатын криптографиялық шабуыл жатады, ол осы ықтималдық модельді хэш-функция үшін соқтығысуды табудың қиындығын азайту үшін, сондай-ақ белгілі бір популяцияның хэш-терінде хэш-соқтығысуының шамамен тәуекелін есептеу үшін пайдаланады. Бұл мәселе әдетте 1927 жыл шамасында Гарольд Давенпортқа жатқызылады, бірақ ол сол кезде оны жарияламады. Давенпорт оны ашқанмын деп мәлімдемеді, "өйткені одан бұрын айтылмағанына сенбеді". Туған күн мәселесінің алғашқы нұсқасы 1939 жылы Ричард фон Мизес тарапынан жарияланды.
In probability theory, the birthday problem asks for the probability that, in a set of n randomly chosen people, at least two will share a birthday. The birthday paradox refers to the counterintuitive fact that only 23 people are needed for that probability to exceed 50%. The birthday paradox is a veridical paradox: it seems wrong at first glance but is, in fact, true. While it may seem surprising that only 23 individuals are required to reach a 50% probability of a shared birthday, this result is made more intuitive by considering that the birthday comparisons will be made between every possible pair of individuals. With 23 individuals, there are = 253 pairs to consider, far more than half the number of days in a year. Real world applications for the birthday problem include a cryptographic attack called the birthday attack, which uses this probabilistic model to reduce the complexity of finding a collision for a hash function, as well as calculating the approximate risk of a hash collision existing within the hashes of a given size of population. The problem is generally attributed to Harold Davenport in about 1927, though he did not publish it at the time. Davenport did not claim to be its discoverer "because he could not believe that it had not been stated earlier". The first publication of a version of the birthday problem was by Richard von Mises in 1939.
Адамдардың бірнеше түріне жалпылау
Негізгі мәселе барлық тәжірибелерді бір "түр" деп қарастырады. Туған күн мәселесі кез келген санды түрлерді ескеру үшін жалпыландырылған. Ең қарапайым кеңейтуде екі түрлі адам бар, мысалы, m ер және n әйел, және мәселе кем дегенде бір ер және бір әйелдің ортақ туған күнінің ықтималдығын анықтауға айналады. (Екі ер немесе екі әйелдің ортақ туған күні есепке алынбайды.) Мұнда ортақ туған күні жоқ ықтималдығы мынадай:
The basic problem considers all trials to be of one "type". The birthday problem has been generalized to consider an arbitrary number of types. In the simplest extension there are two types of people, say m men and n women, and the problem becomes characterizing the probability of a shared birthday between at least one man and one woman. (Shared birthdays between two men or two women do not count.) The probability of no shared birthdays here is
мұндағы және S2 – екінші тектегі Стерлинг сандары. Сәйкесінше, ізделінетін ықтималдық 1 − p0 тең. Туған күн мәселесінің бұл вариациясы қызығушылық тудырады, себебі m + n адамдардың жалпы саны үшін бірегей шешім жоқ. Мысалы, әдеттегі 50% ықтималдық мәні 16 ер және 16 әйелден тұратын 32 адамдық топ үшін де, 43 әйел және 6 ерден тұратын 49 адамдық топ үшін де орындалады.
where and S2 are Stirling numbers of the second kind. Consequently, the desired probability is 1 − p0. This variation of the birthday problem is interesting because there is not a unique solution for the total number of people m + n. For example, the usual 50% probability value is realized for both a 32 member group of 16 men and 16 women and a 49 member group of 43 women and 6 men.
Бірінші матч
Қатысты мәселе – адамдар бөлмеге біреуден біреулеп кіргенде, кімнің туған күні бөлмедегі басқа біреудің туған күнімен сәйкес келуі ең мүмкін? Яғни, qай n үшін p(n) – p(n – 1) мәні ең жоғары болады? Жауап – 20. Егер бірінші рет сәйкес келгені үшін сыйлық болса, кезектегі ең тиімді орын – 20-шы орын.
A related question is, as people enter a room one at a time, which one is most likely to be the first to have the same birthday as someone already in the room? That is, for what n is p(n) − p(n − 1) maximum? The answer is 20—if there is a prize for first match, the best position in line is 20th.
Бір туған күні бар адамдардың саны
n адамнан тұратын топтағы кез келген адамның туған күнін басқа біреумен бірдей болу ықтималдығы жоғарыда түсіндірілгендей . Ортақ (ерекше емес) туған күні бар адамдардың күтілетін санын осы ықтималдықты адамдар санына (n) көбейту арқылы оңай есептеуге болады, сондықтан ол:
For any one person in a group of n people the probability that he or she shares his birthday with someone else is , as explained above. The expected number of people with a shared (non unique) birthday can now be calculated easily by multiplying that probability by the number of people (n), so it is:
(Бұл көбейтуді индикаторлық айнымалылардың күтілетін мәнінің сызықтығына байланысты осылай жасауға болады). Бұл ерекше (бірден-бір) туған күні бар адамдардың күтілетін саны:
(This multiplication can be done this way because of the linearity of the expected value of indicator variables). This implies that the expected number of people with a non shared (unique) birthday is:
Үш, төрт және т.б. басқа адамдармен бірдей туған күні бар адамдардың күтілетін санын есептеу үшін ұқсас формулаларды шығаруға болады.
Similar formulas can be derived for the expected number of people who share with three, four, etc. other people.
Туған күнін тойлағанға дейінгі адамдардың саны
Барлық туған күндерді қамту үшін қажетті адамдардың күтілетін саны Купон жинағышының мәселесі деп аталады. Оны nHn арқылы есептеуге болады, мұнда Hn – n-ші гармониялық сан. 365 мүмкін күн болған жағдайда (туған күн мәселесі), жауабы – 2365.
The expected number of people needed until every birthday is achieved is called the Coupon collector's problem. It can be calculated by nHn, where Hn is the nth harmonic number. For 365 possible dates (the birthday problem), the answer is 2365.
Бөлімдеу мәселесі
Осыған байланысты мәселе – бөліс мәселесі, операциялық зерттеудегі рюкзак мәселесінің бір түрі. Кейбір салмақтар таразыға қойылады; әрбір салмақ бір грамм мен бір миллион грамм (бір тонна) аралығында кездейсоқ таңдалған граммдардың толық саны болып табылады. Сұрақ: таразыны теңестіру үшін, көбінесе (яғни, 1-ге жуық ықтималдықпен) сол және оң жаққа салмақтарды ауыстыру мүмкін бе? (Егер барлық салмақтардың қосындысы граммдардың тақ саны болса, бір граммдық қателікке рұқсат етіледі.) Егер тек екі немесе үш салмақ болса, жауап анық жоқ; кейбір комбинациялар жұмыс істесе де, кездейсоқ таңдалған үш салмақтың көпшілігі жұмыс істемейді. Егер салмақтар өте көп болса, жауап анық иә болады. Сұрақ: қаншасы жеткілікті? Яғни, оларды теңестіру мүмкін және мүмкін емес болуы бірдей ықтималдыққа ие болатындай салмақтардың саны қанша? Көптеген адамдардың сезімі бойынша, жауап 100000-нан жоғары. Көптеген адамдардың ойынша, бұл сан мыңдаған немесе он мыңдаған аралығында, ал басқалары кем дегенде жүздеген болуы керек деп санайды. Дұрыс жауап – 23. Себебі, дұрыс салыстыру салмақтарды сол және оң жаққа бөлу санымен жасалады. N салмақ үшін 2^(N − 1) әр түрлі бөліс бар, ал сол жақтағы сома мен оң жақтағы соманың айырмасы әр бөліс үшін жаңа кездейсоқ шама ретінде қарастырылуы мүмкін. Салмақтардың қосындысының таралуы шамамен Гаусс таралуына ұқсас, шыңы және ені , сондықтан 2^(N − 1) шамамен тең болғанда, өзгеру орын алады. 2^23 − 1 шамамен 4 миллионға тең, ал таралудың ені бар болғаны 5 миллион.
A related problem is the partition problem, a variant of the knapsack problem from operations research. Some weights are put on a balance scale; each weight is an integer number of grams randomly chosen between one gram and one million grams (one tonne). The question is whether one can usually (that is, with probability close to 1) transfer the weights between the left and right arms to balance the scale. (In case the sum of all the weights is an odd number of grams, a discrepancy of one gram is allowed.) If there are only two or three weights, the answer is very clearly no; although there are some combinations which work, the majority of randomly selected combinations of three weights do not. If there are very many weights, the answer is clearly yes. The question is, how many are just sufficient? That is, what is the number of weights such that it is equally likely for it to be possible to balance them as it is to be impossible? Often, people's intuition is that the answer is above 100000. Most people's intuition is that it is in the thousands or tens of thousands, while others feel it should at least be in the hundreds. The correct answer is 23. The reason is that the correct comparison is to the number of partitions of the weights into left and right. There are 2^(N − 1) different partitions for N weights, and the left sum minus the right sum can be thought of as a new random quantity for each partition. The distribution of the sum of weights is approximately Gaussian, with a peak at and width , so that when 2^(N − 1) is approximately equal to the transition occurs. 223 − 1 is about 4 million, while the width of the distribution is only 5 million.
Көркем шығармаларда
Артур Кларктың 1961 жылғы "Ай шаңырағының құлауы" романында, белгісіз мерзімге жер астында қалып қойған басты кейіпкерлердің туған күнді тойлау барысында туған күн проблемасының рас екендігі талқыланады. Физик жолаушының айтуынша: "Егер жиырма төрттен астам адам болса, екеуінің туған күні бірдей болу ықтималдығы жоғары." Соңында, қатысқан 22 адамның ішінде екі адамның туған күні 23 мамыр екені белгілі болды.
Arthur C. Clarke's 1961 novel A Fall of Moondust contains a section where the main characters, trapped underground for an indefinite amount of time, are celebrating a birthday and find themselves discussing the validity of the birthday problem. As stated by a physicist passenger: "If you have a group of more than twenty four people, the odds are better than even that two of them have the same birthday." Eventually, out of 22 present, it is revealed that two characters share the same birthday, May 23.