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

#1

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

$\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 · #2

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

#3

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

#4

Κοτρώνης Αναστάσιος έγραψε:
ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ
Βγάζω $\displaystyle{3/2}$ .

Συμφωνώ.

#5

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

Έχουμε $\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}}$ είναι συγκεντρωμένο όταν το

είναι παίρνει τιμές κοντά στα 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)}$

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

#6

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

Έστω $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

και κάθε αρκετά μεγάλο

ισχύει ότι $\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)}$ , όπου

τυχαία μεταβλητή με κανονική κατανομή και άρα (αφού το

είναι αυθαίρετο) $\displaystyle{ \lim_{n \to \infty} \frac{1}{2^n} \sum_{k \leqslant (1/2 - \varepsilon)n} \binom{n}{k} = 0$

#7

Εκπληκτική απόδειξη, ιδίως για το βήμα $\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, όπως θέλαμε.

Φιλικά,

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

#8

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

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

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

$\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}}$ παραγωγίζοντας

φορές και θέτοντας 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)$

και αυτό δεν επιτρέπει να γίνει καλή εκτίμηση του σφάλματος και να προχωρήσει αυτός ο τρόπος αφού, αθροίζοντας από

ως

, θα παίρνουμε $\mathcal O(1)$ ...

Έχω παρατηρήσει ότι σε τέτοιες περιπτώσεις, (π.χ. βλέπε εδώ) δουλεύει το θεώρημα κυριαρχημένης σύγκλισης για σειρές...τυχαίο....; (δε γνωρίζω...!)

#9

Κοτρώνης Αναστάσιος έγραψε: <...> από το θεώρημα κυριαρχημένης σύγκλισης για σειρές έχουμε <...>

Ενδιαφέρον εργαλείο. Πρέπει να το καταγράψει ο καθένας στα κιτάπια του των ... τεχνικών πασπαρτού... που δουλεύουν όταν όλα τα άλλα αποτυγχάνουν.

Κοτρώνης Αναστάσιος έγραψε: <...>
επιχείρησα να χρησιμοποιήσω ότι $\displaystyle{\ln(1+x)=x+\mathcal O(x^2)}$ .
Αυτό όμως δε βοηθάει διότι για πιάνεται το άκρο της ακτίνας σύγκλισης της $\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.

Φιλικά,

Μιχάλης

#10

Demetres έγραψε:Αυτό ονομάζεται "concentration of measure phenomenon

Υπάρχει κάποια απλούστερη εκδοχή από αυτήν που παρουσιάζεται εδώ;

#11

Κοτρώνης Αναστάσιος έγραψε: Υπάρχει κάποια απλούστερη εκδοχή από αυτήν που παρουσιάζεται εδώ;

Μια καλή παρουσίαση του "concentration of measure" στην ν-διάσταση σφαίρα βρίσκεται στο 14ο κεφάλαιο του βιβλίου "Lectures on discrete geometry" του Matousek.

Αυτό που λέει η βικιπαιδεία είναι το εξής: Έστω (X,d)

ένας οποιοσδήποτε μετρικός χώρος και έστω $\mu$ ένα μέτρο στο

με $\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_n

. Αν συμβολίζουμε με $\alpha_n(t)$ τις αντίστοιχες σταθερές και $\alpha_n(t) \to 0$ όταν $n \to \infty$ (με

σταθερό) τότε έχουμε concentration of measure.

Το κλασικό παράδειγμα είναι το εμβαδόν επιφάνειας της σφαίρας. Δηλαδή $X_n = S^{n-1}$ η

-διάστατη σφαίρα και $\mu(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}$ του συνολικού εμβαδού. (Σχεδόν όλη η επιφάνεια της σφαίρας βρίσκεται γύρω από τον ισημερινό. Γύρω από οποιονδήποτε ισημερινό!)

#12

viewtopic.php?f=9&t=2879&p=15602#p15602

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

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

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

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

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

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

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

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

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

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

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

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

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

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