Ένα όμορφο όριο (6)

Συντονιστές: grigkost, Κοτρώνης Αναστάσιος

Άβαταρ μέλους
Κοτρώνης Αναστάσιος
Επιμελητής
Δημοσιεύσεις: 3203
Εγγραφή: Κυρ Φεβ 22, 2009 11:11 pm
Τοποθεσία: Μπροστά στο πισί...
Επικοινωνία:

Ένα όμορφο όριο (6)

#1

Μη αναγνωσμένη δημοσίευση από Κοτρώνης Αναστάσιος » Πέμ Νοέμ 11, 2010 1:48 pm

Ας υπολογισθεί, αν υπάρχει, το όριο

\displaystyle{\lim_{n\to\infty}\frac{1}{n}\sqrt[2^{n}]{n^{C_{n}^{0}}(n+1)^{C_{n}^{1}}\ldots (n+n)^{C_{n}^{n}}}}, όπου \displaystyle{C_{n}^{k}=\binom{n}{k}}.


Εσύ....; Θα γίνεις κανίβαλος....;

Λέξεις Κλειδιά:
Άβαταρ μέλους
erxmer
Δημοσιεύσεις: 1615
Εγγραφή: Δευ Σεπ 13, 2010 7:49 pm
Επικοινωνία:

Re: Ένα όμορφο όριο (6)

#2

Μη αναγνωσμένη δημοσίευση από erxmer » Πέμ Νοέμ 11, 2010 1:55 pm

Μέχρι χθές το βράδυ άλυτο ήταν στο mathlinks


Άβαταρ μέλους
Κοτρώνης Αναστάσιος
Επιμελητής
Δημοσιεύσεις: 3203
Εγγραφή: Κυρ Φεβ 22, 2009 11:11 pm
Τοποθεσία: Μπροστά στο πισί...
Επικοινωνία:

Re: Ένα όμορφο όριο (6)

#3

Μη αναγνωσμένη δημοσίευση από Κοτρώνης Αναστάσιος » Πέμ Νοέμ 11, 2010 2:24 pm



Εσύ....; Θα γίνεις κανίβαλος....;
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8569
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Ένα όμορφο όριο (6)

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Νοέμ 11, 2010 3:48 pm

Κοτρώνης Αναστάσιος έγραψε:
Συμφωνώ.


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8569
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Ένα όμορφο όριο (6)

#5

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Νοέμ 13, 2010 2:19 pm

Δίνω και μια απόδειξη.

Έχουμε \displaystyle{ \frac{1}{n} \left(\prod_{k=0}^n (n+k)^{\binom{n}{k}} \right)^{1/2^n} = \frac{1}{n}\exp\left(\frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} \log(n+k) \right) = \frac{1}{n}\exp\left(\frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} (\log(1+k/n) + \log{n}) \right)}

\displaystyle{ = \frac{1}{n}\exp\left(\frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} \log(1+k/n) \right)\exp\left(\frac{\log{n}}{2^n}\sum_{k=0}^n \binom{n}{k} \right) = \exp\left(\frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} \log(1+k/n) \right)}

Θα δείξω ότι \displaystyle{ \lim_{n \to \infty}\frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} \log(1+k/n) = \log(3/2)} από το οποίο έπεται ότι \displaystyle{ \lim_{n\to \infty} \frac{1}{n} \left(\prod_{k=0}^n (n+k)^{\binom{n}{k}} \right)^{1/2^n} = 3/2}

Η βασική ιδέα είναι ότι όλο τα "βάρος" του \displaystyle{ \sum_{k=0}^n \binom{n}{k}} είναι συγκεντρωμένο όταν το k είναι παίρνει τιμές κοντά στα n/2. (Αυτό ονομάζεται "concentration of measure phenomenon".) Πιο συγκεκριμένα ισχύει το ακόλουθο λήμμα:

Για κάθε \varepsilon > 0 ισχύει ότι \displaystyle{ \lim_{n \to \infty}\frac{1}{2^n}\sum_{k\leqslant (1/2 - \varepsilon)n} \binom{n}{k} = \lim_{n \to \infty}\frac{1}{2^n}\sum_{k\geqslant (1/2 + \varepsilon)n} \binom{n}{k} = 0 }

Επειδή \displaystyle{\sum_{k=0}^n \binom{n}{k} = 2^n} συμπεραίνουμε ακόμη ότι

\displaystyle{ \lim_{n \to \infty}\frac{1}{2^n}\sum_{k > (1/2 - \varepsilon)n} \binom{n}{k} = \lim_{n \to \infty}\frac{1}{2^n}\sum_{k < (1/2 + \varepsilon)n} \binom{n}{k} = 1 }

Με αυτό το λήμμα το πράγματα γίνονται εύκολα:

\displaystyle{ \lim_{n \to \infty}\frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} \log(1+k/n) = \lim_{n \to \infty}\frac{1}{2^n} \sum_{k > (1/2 - \varepsilon) n} \binom{n}{k} \log(1+k/n) \geqslant \lim_{n \to \infty}\frac{1}{2^n} \sum_{k > (1/2 - \varepsilon) n} \binom{n}{k} \log(3/2 - \varepsilon) = \log(3/2 - \varepsilon)}

Αφού το \varepsilon > 0 είναι αυθαίρετο, συμπεραίνουμε ότι

\displaystyle{ \lim_{n \to \infty}\frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} \log(1+k/n) \geqslant \log(3/2)}

Με παρόμοιο τρόπο αποδεικνύουμε ότι και το άνω φράγμα.


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8569
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Ένα όμορφο όριο (6)

#6

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Νοέμ 13, 2010 2:38 pm

Μένει να αποδειχθεί το λήμμα. Υπάρχουν και ποιο στοιχειώδεις αποδείξεις αλλά ίσως η πιο σύντομη είναι με χρήση του κεντρικού οριακού θεωρήματος.

Έστω X_1,\ldots,X_k ανεξάρτητες τυχαίες μεταβλητές Bernoulli με πιθανότητα 1/2. Τότε

\displaystyle{ \frac{1}{2^n} \sum_{k \leqslant (1/2 - \varepsilon)n} \binom{n}{k} = \Pr\left(X_1 + \cdots + X_n \leqslant \left(\frac{1}{2} - \varepsilon\right)n \right) = \Pr\left(\frac{(X_1 + \cdots + X_n) - n/2}{\sqrt{n}/2} \leqslant -2\varepsilon \sqrt{n}\right) }

Άρα για κάθε K > 0 και κάθε αρκετά μεγάλο n ισχύει ότι \displaystyle{ \frac{1}{2^n} \sum_{k \leqslant (1/2 - \varepsilon)n} \binom{n}{k}  \leqslant \Pr\left(\frac{(X_1 + \cdots + X_n) - n/2}{\sqrt{n}/2} \leqslant -K\right)}

Όμως από το κεντρικό οριακό θεώρημα οι τυχαίες μεταβλητές \displaystyle{ \frac{(X_1 + \cdots + X_n) - n/2}{\sqrt{n}/2} } τείνουν (in distribution) στην κανονική κατανομή N(0,1).

Άρα για κάθε K > 0 ισχύει ότι \displaystyle{ \lim_{n \to \infty} \frac{1}{2^n} \sum_{k \leqslant (1/2 - \varepsilon)n} \binom{n}{k} \leqslant \Pr(Z \leqslant -K)}, όπου Z τυχαία μεταβλητή με κανονική κατανομή και άρα (αφού το K είναι αυθαίρετο) \displaystyle{ \lim_{n \to \infty} \frac{1}{2^n} \sum_{k \leqslant (1/2 - \varepsilon)n} \binom{n}{k} = 0


Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 12988
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Ένα όμορφο όριο (6)

#7

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Σάβ Νοέμ 13, 2010 5:21 pm

Εκπληκτική απόδειξη, ιδίως για το βήμα \displaystyle{ \lim_{n \to \infty}\frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} \log(1+k/n) = \log(3/2)} (1) που είναι όλο το ζουμί (τα υπόλοιπα είναι, τρόπος του λέγειν, φυσιολογικά).

Την εκπληκτική τεχνική όπου μόνος ένας όρος του αθροίσματος συγκεντρώνει όλο το βάρος, την έμαθα εδώ στο φόρουμ από τον ίδιο τον Δημήτρη, σε παλαιότερο ποστ (άντε βρες το τώρα, που μπορεί να ήταν και στο παλιό mathematica).

Θα δώσω διαφορετική, και στοιχειώδη, απόδειξη. Υποθέτω ότι η ίδια τεχνική κάνει και ως αντικατάσταση του δεύτερου σκέλους της απόδειξης του Δημήτρη (το πιθανοθεωρητικό) αλλά δεν το έψαξα με προσοχή γιατί σήμερα έχω πάάάάάρα πολύ δουλειά.

Στο θέμα μας: Απόδειξη της (1).

Θα κάνω χρήση των ακόλουθων (όλα γνωστά ή απλά, και τα περισσότερα τα χρησιμοποίησε και ο Δημήτρης)

α) \binom{n}{k} = \binom{n}{n-k}

β) \sum_{k=0}^n \binom{n}{k}= 2^n, \,\,  \sum_{k=0}^n \binom{n}{k}k= 2^{n-1}n, \,\, \sum_{k=0}^n \binom{n}{k}k^2= 2^{n-2}(n+n^2), \,\, και άρα

\sum_{k=0}^n \binom{n}{k}(n^2-4kn+4k^2)= 2^nn , \,\,

γ) Αν y > x > 0 τότε (από ΘΜΤ) \log y - \log x < \frac {1}{x}(y-x). Ειδικά

\displaystyle{0 \le \log \frac {9}{4}- \log \left(2+\frac{k(n-k)}{n^2}\right) \le \frac{1}{2+\frac{k(n-k) }{n^2}}\left( \frac{9}{4}- 2-\frac{k(n-k)}{n^2}\right) \le \frac{1}{2} \left( \frac{9}{4}- 2-\frac{k(n-k)}{n^2}\right)= \frac{n^2-4kn+4k^2}{8n^2}}

Έχουμε τώρα , γράφοντας το άθροισμα ανάποδα,

\displaystyle{\sum_{k=0}^n \binom{n}{k} \log(1+ \frac{k}{n}) = \frac{1}{2}\sum_{k=0}^n \binom{n}{k} \log(1+\frac{k}{n}) + \frac{1}{2}\sum_{k=0}^n \binom{n}{n-k} \log(1+\frac{n-k}{n})=}

\displaystyle{=\frac{1}{2}\sum_{k=0}^n \binom{n}{k} \left( \log(1+\frac{k}{n}) +  \log(1+\frac{n-k}{n})\right)=\frac{1}{2}\sum_{k=0}^n \binom{n}{k} \log \left(2+\frac{k(n-k)}{n^2}\right)}

Άρα

\displaystyle{\log (3/2) - \frac{1}{2^n}\sum_{k=0}^n \binom{n}{k} \log(1+\frac{k}{n}) =  \frac {1}{2} \log \frac {9}{4}- \frac {1}{2} \cdot \frac{1}{2^n}  \sum_{k=0}^n \binom{n}{k} \log \left(2+\frac{k(n-k)}{n^2}\right)=}

\displaystyle{= \frac {1}{2} \cdot \frac{1}{2^n}  \sum_{k=0}^n \binom{n}{k}\left( \log \frac {9}{4}- \log \left(2+\frac{k(n-k)}{n^2}\right)\right)\le \frac {1}{2} \cdot \frac{1}{2^n}  \sum_{k=0}^n \binom{n}{k}\frac{n^2-4kn+4k^2}{8n^2} } =  }

\displaystyle {=\frac {1}{2} \cdot \frac{1}{2^n}\cdot\frac{2^nn}{8n^2}  =\frac{1}{16n} }

που τείνει στο 0, όπως θέλαμε.

Φιλικά,

Μιχάλης Λάμπρου


Άβαταρ μέλους
Κοτρώνης Αναστάσιος
Επιμελητής
Δημοσιεύσεις: 3203
Εγγραφή: Κυρ Φεβ 22, 2009 11:11 pm
Τοποθεσία: Μπροστά στο πισί...
Επικοινωνία:

Re: Ένα όμορφο όριο (6)

#8

Μη αναγνωσμένη δημοσίευση από Κοτρώνης Αναστάσιος » Κυρ Νοέμ 14, 2010 7:25 pm

Τι να πω για ό,τι προηγήθηκε..Ότι και να πω λίγο θα είναι! Πολύ όμορφα όλα!

Ας παραθέσω και το δικό μου σκεπτικό. Νομίζω ότι αναδεικνύει την αξία του θεωρήματος του οποίου γίνεται χρήση.

Κατ' αρχάς γράφουμε την ποσότητα της οποίας αναζητούμε το όριο ως εξής:

\displaystyle{\frac{1}{n}\sqrt[2^n]{n^{C_{n}^{0}}(n+1)^{C_{n}^{1}}\cdots(n+n)^{C_{n}^{n}}}=\frac{1}{n}\sqrt[2^n]{n^{C_{n}^{0}+\cdots+C_{n}^{n}}\left(1+\frac{0}{n}\right)^{C_{n}^{0}}\left(1+\frac{1}{n}\right)^{C_{n}^{1}}\cdots\left(1+\frac{n}{n}\right)^{C_{n}^{n}}}=}

\displaystyle{\frac{1}{n}\sqrt[2^n]{n^{2^n}\left(1+\frac{0}{n}\right)^{C_{n}^{0}}\left(1+\frac{1}{n}\right)^{C_{n}^{1}}\cdots\left(1+\frac{n}{n}\right)^{C_{n}^{n}}}=\exp\left(\frac{1}{2^n}\ln\prod_{k=0}^{n}\left(1+\frac{k}{n}\right)^{C_{n}^{k}}\right)=}

\displaystyle{\exp\left(\frac{1}{2^n}\sum_{k=0}^{n}\ln\left(1+\frac{k}{n}\right)^{C_{n}^{k}}\right):=\exp A_{n}}. Τώρα γράφουμε

\displaystyle{A_{1}=\sum_{k=0}^{1}\frac{C_{1}^{k}}{2^{1}}\ln\Big(1+\frac{k}{1}\Big)=\underbrace{\sum_{k=0}^{1}\frac{C_{1}^{k}}{2^{1}}\Big(\frac{k}{1}\Big)^{1}\frac{(-1)^{1-1}}{1}}_{a_{1,1}}+\cdots+\underbrace{\sum_{k=0}^{1}\frac{C_{1}^{k}}{2^{1}}\Big(\frac{k}{1}\Big)^{m}\frac{(-1)^{m-1}}{m}}_{a_{1,m}}+\cdots}


\displaystyle{A_{2}=\sum_{k=0}^{2}\frac{C_{2}^{k}}{2^{2}}\ln\Big(1+\frac{k}{2}\Big)=\underbrace{\sum_{k=0}^{2}\frac{C_{2}^{k}}{2^{2}}\Big(\frac{k}{2}\Big)^{1}\frac{(-1)^{1-1}}{1}}_{a_{2,1}}+\cdots+\underbrace{\sum_{k=0}^{2}\frac{C_{2}^{k}}{2^{2}}\Big(\frac{k}{2}\Big)^{m}\frac{(-1)^{m-1}}{m}}_{a_{2,m}}+\cdots}

\vdots

\displaystyle{A_{n}=\sum_{k=0}^{n}\frac{C_{n}^{k}}{2^{n}}\ln\Big(1+\frac{k}{n}\Big)=\underbrace{\sum_{k=0}^{n}\frac{C_{n}^{k}}{2^{n}}\Big(\frac{k}{n}\Big)^{1}\frac{(-1)^{1-1}}{1}}_{a_{n,1}}+\cdots+\underbrace{\sum_{k=0}^{n}\frac{C_{n}^{k}}{2^{n}}\Big(\frac{k}{n}\Big)^{m}\frac{(-1)^{m-1}}{m}}_{a_{n,m}}+\cdots}

\vdots

Όμως για \displaystyle{m\geq1} είναι \displaystyle{|a_{n,m}|\leq\frac{1}{m2^{n}n^{m}}\sum_{k=0}^{n}C_{n}^{k}k^{m}\stackrel{\boxed{*}}{=}\frac{2^{n-m}P(n)}{m2^{n}n^{m}}=\frac{1}{m2^{m}}\frac{P(n)}{n^{m}}}

όπου \displaystyle{P(x)} είναι μονικό πολυώνυμο με \displaystyle{\deg P(n)=m}, που σημαίνει ότι το

\displaystyle{\frac{1}{m2^{m}}\frac{P(n)}{n^{m}} τελικά (ως προς το \displaystyle{n}) κυριαρχείται από το \displaystyle{\frac{1}{m2^m}} με την \displaystyle{\sum_{m=1}^{+\infty}\frac{1}{m2^m}} να συγκλίνει.

Καθώς τώρα \displaystyle{\lim_{n\to+\infty}a_{n,m}=\lim_{n\to+\infty}\frac{(-1)^{m-1}}{m2^{n}n^{m}}\sum_{k=1}^{n}C_{n}^{k}k^{m}=\lim_{n\to+\infty}\frac{(-1)^{m-1}}{m2^{m}}\frac{P(n)}{n^{m}}=\frac{(-1)^{m-1}}{m2^m}}, από το θεώρημα κυριαρχημένης σύγκλισης για σειρές έχουμε


\displaystyle{\lim_{n\to+\infty}A_{n}=\lim_{n\to+\infty}\sum_{m=1}^{+\infty}a_{n,m}=\sum_{m=1}^{+\infty}\lim_{n\to+\infty}a_{n,m}=\sum_{m=1}^{+\infty}\frac{(-1)^{m-1}}{m2^m}\stackrel{\boxed{**}}{=}\ln\frac{3}{2}} και συνεπώς το ζητούμενο όριο είναι 3/2.

\displaystyle{\boxed{*}} Το ότι \displaystyle{\sum_{k=0}^{n}C_{n}^{k}k^{m}=2^{n-m}P(n)} όπου το P(x) έχει τις προαναφερθείσες ιδιότητες, μπορεί κανείς να το αποδείξει από την ισότητα \displaystyle{(1+x)^{n}=\sum_{k=0}^{n}\binom{n}{k}x^{k}} παραγωγίζοντας m φορές και θέτοντας x=1, ή με επαγωγή κάνοντας χρήση του τύπου \displaystyle{\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}}.

\displaystyle{\boxed{**}} Αυτό έπεται από το ότι \displaystyle{\ln(1+x)=\sum_{m=1}^{+\infty}\frac{(-1)^{m-1}x^{m}}{m}} για x=1/2.

****************************************************************************************************************************************************************************************************

Μια παρατήρηση

Στο το σημείο που θέτω \displaystyle{\frac{C_{n}^{k}}{2^n}\sum_{k=0}^{n}\ln\left(1+\frac{k}{n}\right)\right):= A_{n}}, επιχείρησα να χρησιμοποιήσω ότι \displaystyle{\ln(1+x)=x+\mathcal O(x^2)}.

Αυτό όμως δε βοηθάει διότι για k=n πιάνεται το άκρο της ακτίνας σύγκλισης της \ln(1+x)

και αυτό δεν επιτρέπει να γίνει καλή εκτίμηση του σφάλματος και να προχωρήσει αυτός ο τρόπος αφού, αθροίζοντας από 0 ως n, θα παίρνουμε \mathcal O(1)...

Έχω παρατηρήσει ότι σε τέτοιες περιπτώσεις, (π.χ. βλέπε εδώ) δουλεύει το θεώρημα κυριαρχημένης σύγκλισης για σειρές...τυχαίο....; (δε γνωρίζω...!)
τελευταία επεξεργασία από Κοτρώνης Αναστάσιος σε Τετ Μαρ 09, 2011 12:15 pm, έχει επεξεργασθεί 1 φορά συνολικά.


Εσύ....; Θα γίνεις κανίβαλος....;
Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 12988
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: Ένα όμορφο όριο (6)

#9

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Κυρ Νοέμ 14, 2010 8:20 pm

Κοτρώνης Αναστάσιος έγραψε: <...> από το θεώρημα κυριαρχημένης σύγκλισης για σειρές έχουμε <...>
Ενδιαφέρον εργαλείο. Πρέπει να το καταγράψει ο καθένας στα κιτάπια του των ... τεχνικών πασπαρτού... που δουλεύουν όταν όλα τα άλλα αποτυγχάνουν.
Κοτρώνης Αναστάσιος έγραψε: <...>
επιχείρησα να χρησιμοποιήσω ότι \displaystyle{\ln(1+x)=x+\mathcal O(x^2)}.
Αυτό όμως δε βοηθάει διότι για k=n πιάνεται το άκρο της ακτίνας σύγκλισης της \ln(1+x)
και αυτό δεν επιτρέπει να γίνει καλή εκτίμηση του σφάλματος <...>
Ακριβώς! Και εγώ όταν πάλευα την άσκηση συνάντησα αυτή την δυσκολία, οπότε το ερώτημα ήταν πώς θα παρακαμφθεί. Ας σημειώσω ότι ένα από τα κλειδιά
της λύσης του Δημήτρη, που παρακάμπτει αυτή την δυσκολία, είναι ακριβώς η παρατήρηση ότι η μέγιστη τιμή του \binom {n}{k} πιάνεται στη μέση (δηλαδή για k=n/2).
Το ίδιο ακριβώς συμβαίνeι και στην δική μου λύση, όπου εμφανίζεται ο όρος \binom {n}{k}\log \left( 2+ \frac{k(n-k)}{n^2} \right). Σε αυτή την περίπτωση, όχι μόνο το μέγιστο του \binom {n}{k} αλλά
και του \log \left( 2+ \frac{k(n-k)}{n^2} \right) (ισοδύναμα του k(n-k)) πιάνεται στο k = n/2.

Φιλικά,

Μιχάλης


Άβαταρ μέλους
Κοτρώνης Αναστάσιος
Επιμελητής
Δημοσιεύσεις: 3203
Εγγραφή: Κυρ Φεβ 22, 2009 11:11 pm
Τοποθεσία: Μπροστά στο πισί...
Επικοινωνία:

Re: Ένα όμορφο όριο (6)

#10

Μη αναγνωσμένη δημοσίευση από Κοτρώνης Αναστάσιος » Δευ Νοέμ 15, 2010 4:19 am

Demetres έγραψε:Αυτό ονομάζεται "concentration of measure phenomenon
Υπάρχει κάποια απλούστερη εκδοχή από αυτήν που παρουσιάζεται εδώ;


Εσύ....; Θα γίνεις κανίβαλος....;
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8569
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Ένα όμορφο όριο (6)

#11

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Νοέμ 15, 2010 4:59 pm

Κοτρώνης Αναστάσιος έγραψε: Υπάρχει κάποια απλούστερη εκδοχή από αυτήν που παρουσιάζεται εδώ;
Μια καλή παρουσίαση του "concentration of measure" στην ν-διάσταση σφαίρα βρίσκεται στο 14ο κεφάλαιο του βιβλίου "Lectures on discrete geometry" του Matousek.

Αυτό που λέει η βικιπαιδεία είναι το εξής: Έστω (X,d) ένας οποιοσδήποτε μετρικός χώρος και έστω \mu ένα μέτρο στο X με \mu(X) = 1. Για A \subseteq X ορίζουμε A_t = \{x \in X: d(x,A) \leqslant t. Έστω

\displaystyle{ \alpha(t) = \sup \{1 - \mu(A): A \subseteq X, \mu(A) = 1/2\}}

Με άλλα λόγια το \alpha(t) είναι η καλύτερη σταθερά ώστε για κάθε A \subseteq X να ισχύει ότι

\displaystyle{ \mu(A) \geqslant 1/2 \Rightarrow \mu(A_t) \geqslant 1 - \alpha(t)}

Όσο πιο μικρό είναι το \alpha(t) τόσο πιο καλή είναι η συγκέντρωση μέτρου που έχουμε. Συνήθως αυτό που μας ενδιαφέρει δεν είναι ένας μετρικός χώρος X αλλά μια ακολουθία μετρικών χώρων X_n. Αν συμβολίζουμε με \alpha_n(t) τις αντίστοιχες σταθερές και \alpha_n(t) \to 0 όταν n \to \infty (με t σταθερό) τότε έχουμε concentration of measure.

Το κλασικό παράδειγμα είναι το εμβαδόν επιφάνειας της σφαίρας. Δηλαδή X_n = S^{n-1} η n-διάστατη σφαίρα και \mu(A) είναι το εμβαδόν επιφάνειας του A (κανονικοποιημένο ώστε \mu(X_n) = 1). Τότε ισχύει ότι

\displaystyle{ \mu(A) \geqslant 1/2 \Rightarrow \mu(A_t) \geqslant 1 - e^{-nt^2/2}}

Για παράδειγμα αν πάρουμε όλα τα σημεία της σφαίρας που απέχουν το πολύ 10/\sqrt{n} από το βόρειο ημισφαίριο τότε η επιφάνεια της σφαίρας που δεν θα καλύψουμε θα έχει εμβαδόν το πολύ e^{-50} του συνολικού εμβαδού. (Σχεδόν όλη η επιφάνεια της σφαίρας βρίσκεται γύρω από τον ισημερινό. Γύρω από οποιονδήποτε ισημερινό!)


Άβαταρ μέλους
Κοτρώνης Αναστάσιος
Επιμελητής
Δημοσιεύσεις: 3203
Εγγραφή: Κυρ Φεβ 22, 2009 11:11 pm
Τοποθεσία: Μπροστά στο πισί...
Επικοινωνία:

Re: Ένα όμορφο όριο (6)

#12

Μη αναγνωσμένη δημοσίευση από Κοτρώνης Αναστάσιος » Κυρ Δεκ 12, 2010 4:31 pm



Εσύ....; Θα γίνεις κανίβαλος....;
Απάντηση

Επιστροφή σε “ΑΝΑΛΥΣΗ”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες