Sachverhalt: Sachverhalt: A. Am 20. Januar 2003 erhob A._ Strafanzeige gegen X._. Sie beschuldigte ihn, Gelder und Vermögensgegenstände, die sie ihm anvertraut hatte, veruntreut und sie in Ausnutzung ihrer Notlage in die Prostitution eingeführt zu haben. Später bezichtigte sie ihn zusätzlich der Urkundenfälschung. Nach durchgeführten Ermittlungen stellte das Verhöramt Appenzell Ausserrhoden das Verfahren gegen X._ mit Verfügung vom 24. Juni 2005 mit der Begründung ein, dem Beschuldigten könne kein strafrechtlich relevantes Verschulden nachgewiesen werden. Es wurden keine Kosten erhoben. Die Staatsanwaltschaft Appenzell Ausserrhoden genehmigte diese Einstellungsverfügung am 28. Juni 2005. Mit Schreiben vom 30. Juni 2005 reichte der Anwalt von X._ dem Verhöramt seine Kostennote über Fr. 2'669.55 ein. Am 12. Juli 2005 erhob A._ gegen die Einstellungsverfügung Einsprache, worauf die Staatsanwaltschaft das Verhöramt am 20. September 2005 anwies, den Beschuldigten untersuchungsrichterlich zu befragen und die Strafuntersuchung durch weitere Beweiserhebungen zu ergänzen. Nach Abschluss der diesbezüglichen Untersuchung stellte das Verhöramt den Parteien den Erlass einer weiteren Einstellungsverfügung in Aussicht, worauf der Anwalt von X._ am 26. Januar 2006 eine weitere Kostennote über Fr. 1'984.10 einreichte und damit eine ausseramtliche Entschädigung von insgesamt Fr. 4'653.65 geltend machte. Mit Verfügung vom 27. März 2006 stellte das Verhöramt das Verfahren gegen X._ erneut ein. Es wurden keine Kosten erhoben, aber auch keine Entschädigung zugesprochen. Am 4. April 2006 genehmigte die Staatsanwaltschaft die Einstellungsverfügung. Am 12. Juli 2005 erhob A._ gegen die Einstellungsverfügung Einsprache, worauf die Staatsanwaltschaft das Verhöramt am 20. September 2005 anwies, den Beschuldigten untersuchungsrichterlich zu befragen und die Strafuntersuchung durch weitere Beweiserhebungen zu ergänzen. Nach Abschluss der diesbezüglichen Untersuchung stellte das Verhöramt den Parteien den Erlass einer weiteren Einstellungsverfügung in Aussicht, worauf der Anwalt von X._ am 26. Januar 2006 eine weitere Kostennote über Fr. 1'984.10 einreichte und damit eine ausseramtliche Entschädigung von insgesamt Fr. 4'653.65 geltend machte. Mit Verfügung vom 27. März 2006 stellte das Verhöramt das Verfahren gegen X._ erneut ein. Es wurden keine Kosten erhoben, aber auch keine Entschädigung zugesprochen. Am 4. April 2006 genehmigte die Staatsanwaltschaft die Einstellungsverfügung. B. Mit Rekurs an die Staatsanwaltschaft beantragte X._ die Aufhebung des Kostenentscheids der Einstellungsverfügung vom 27. März 2006 und Zusprechung einer Parteientschädigung von Fr. 4'653.65 an ihn. Die Staatsanwaltschaft wies mit Rekursentscheid vom 21. Juli 2006 den Rekurs ab, wobei sie den Verzicht auf Entschädigung mit einem zivilrechtlich vorwerfbaren Verhalten von X._ begründete. B. Mit Rekurs an die Staatsanwaltschaft beantragte X._ die Aufhebung des Kostenentscheids der Einstellungsverfügung vom 27. März 2006 und Zusprechung einer Parteientschädigung von Fr. 4'653.65 an ihn. Die Staatsanwaltschaft wies mit Rekursentscheid vom 21. Juli 2006 den Rekurs ab, wobei sie den Verzicht auf Entschädigung mit einem zivilrechtlich vorwerfbaren Verhalten von X._ begründete. C. Gegen diesen Rekursentscheid der Staatsanwaltschaft hat X._ am 6. September 2006 beim Bundesgericht staatsrechtliche Beschwerde wegen Verletzung der Unschuldsvermutung (Art. 32 Abs. 1 BV, Art. 6 Ziff. 2 EMRK) und des Willkürverbots (Art. 9 BV) erhoben. Er beantragt, der angefochtene Entscheid sei aufzuheben und an die Staatsanwaltschaft zurückzuweisen. C. Gegen diesen Rekursentscheid der Staatsanwaltschaft hat X._ am 6. September 2006 beim Bundesgericht staatsrechtliche Beschwerde wegen Verletzung der Unschuldsvermutung (Art. 32 Abs. 1 BV, Art. 6 Ziff. 2 EMRK) und des Willkürverbots (Art. 9 BV) erhoben. Er beantragt, der angefochtene Entscheid sei aufzuheben und an die Staatsanwaltschaft zurückzuweisen. D. Die Staatsanwaltschaft beantragt Abweisung der Beschwerde, soweit darauf einzutreten sei.